  Ising machines are expected to solve combinatorial optimization problems
faster than the existing integer programming solvers. These problems,
particularly those encountered in practical situations, typically involve
inequality constraints. However, owing to the hardware limitations of the
current Ising machines, solving combinatorial optimization problems with
inequality constraints remains challenging. The Capacitated Vehicle Routing
Problem (CVRP) is a typical example of a problem with inequality constraints.
The objective function of the CVRP is to minimize the total distance traveled
by each vehicle while limiting the total demand of customers served by a single
vehicle to the vehicle's capacity. The CVRP is classified as NP-hard and, thus,
is commonly solved using heuristic algorithms, such as column generation.
Column generation attempts to iteratively generate only the promising routes,
as the number of feasible routes increases exponentially. Within this
framework, the CVRP is formulated as a set cover problem. The corresponding
dual solutions are used to define the pricing subproblem, which is intended to
create a new route. By applying Ising machines to this pricing subproblem, the
overall computation time can be reduced. This study aims to solve combinatorial
optimization problems with inequality constraints using a hybrid algorithm that
combines column generation and Ising machines, thereby extending the
applications of the latter. We parameterize the difficulty of the inequality
constraints and demonstrate that our annealing-assisted column generation can
converge to a better lower bound.
