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 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.

13 pages, 10 figures

References in corpus (7)

• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Quantum pricing-based column-generation framework for hard combinatorial problems
• Guiding Principle for Minor-Embedding in Simulated-Annealing-Based Ising Machines
• Efficient Algorithm for Binary Quadratic Problem by Column Generation and Quantum Annealing
• Toward Practical Benchmarks of Ising Machines: A Case Study on the Quadratic Knapsack Problem
• Hybrid Optimization Method Using Simulated-Annealing-Based Ising Machine and Quantum Annealer
• Dynamical process of a bit-width reduced Ising model with simulated annealing

Cited by in corpus (7)

• Advantages of fixing spins in quantum annealing
• Impact of Fixing Spins in a Quantum Annealer with Energy Rescaling
• SWIFT-FMQA: Enhancing Factorization Machine with Quadratic-Optimization Annealing via Sliding Window
• Evaluating the solution performance of the augmented Lagrangian function on Ising machines
• Efficient Construction of Feasible Solutions in Column Generation using Quantum Annealing
• Quantitative analysis of the effectiveness of mid-anneal measurement in quantum annealing
• Frustration-enhanced quantum annealing correction models with additional inter-replica interactions