Annealing-Assisted Column Generation for Inequality-Constrained Combinatorial Optimization Problems

Abstract

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 CVRP is classified as ${\mathcal {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. Additionally, we introduced limited column generation, wherein we fixed the decision variables to eliminate the overlap between the generated columns. By reducing unnecessary variables, our proposed method can overcome the hardware limitations where a small number of variables is available on real devices. We parameterize the difficulty of the inequality constraints and demonstrate that our annealing-assisted column generation can converge to a better lower bound.

Keywords

• Capacitated vehicle routing problem
• column generation
• combinatorial optimization problem
• inequality constraints
• Ising machines
• simulated annealing