  We present a method that integrates any quantum algorithm capable of finding
solutions to integer linear programs into the Branch-and-Price algorithm, which
is regularly used to solve large-scale integer linear programs with a specific
structure. The role of the quantum algorithm is to find integer solutions to
subproblems appearing in Branch-and-Price. Obtaining optimal or near-optimal
integer solutions to these subproblems can increase the quality of solutions
and reduce the depth and branching factor of the Branch-and-Price algorithm and
hence reduce the overall running time. We investigate the viability of the
approach by considering the Tail Assignment problem and the Quantum Approximate
Optimization Algorithm (QAOA). Here, the master problem is the optimization
problem Set Partitioning or its decision version Exact Cover and can be
expressed as finding the ground state of an Ising spin glass Hamiltonian. For
Exact Cover, our numerical results indicate that the required algorithm depth
decreases with the number of feasible solutions for a given success probability
of finding a feasible solution. For Set Partitioning, on the other hand, we
find that for a given success probability of finding the optimal solution, the
required algorithm depth can increase with the number of feasible solutions if
the Hamiltonian is balanced poorly, which in the worst case is exponential in
the problem size. We therefore address the importance of properly balancing the
objective and constraint parts of the Hamiltonian. We empirically find that the
approach is viable with QAOA if polynomial algorithm depth can be realized on
quantum devices.
