Efficient Construction of Feasible Solutions in Column Generation using Quantum Annealing
arXiv:2503.24107 · doi:10.7566/JPSJ.94.094005
Abstract
Column generation (CG) has been used to solve constrained 0-1 quadratic programming problems. The pricing problem, which is iteratively solved in CG, can be reduced to an unconstrained 0-1 quadratic programming problem, allowing for the efficient application of quantum annealing (QA). The solutions obtained by CG are continuous relaxations, which cannot be practically used as feasible 0-1 solutions. In this paper, we propose a postprocessing method for constructing feasible 0-1 solutions from the continuous relaxations obtained through CG. The proposed technique consists of two phases: (i) mapping the continuous CG solution to a feasible 0-1 solution and (ii) applying a constraint-aware local search to improve that solution's quality. Numerical experiments on randomly generated problems demonstrate that CG with the proposed postprocessing yields solutions comparable to commercial solvers with significantly reduced computation time. Consequently, the postprocessing enables CG with QA to obtain high-quality approximate solutions faster.
14 pages, 4 figures
References in corpus (21)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- Quantum Boltzmann Machine
- Reverse Quantum Annealing Approach to Portfolio Optimization Problems
- Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
- Nonnegative/binary matrix factorization with a D-Wave quantum annealer
- Optimal Control of Traffic Signals using Quantum Annealing
- Travel time optimization on multi-AGV routing by reverse annealing
- Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
- Fair Sampling by Simulated Annealing on Quantum Annealer
- Quantum pricing-based column-generation framework for hard combinatorial problems
- Comparing the effects of Boltzmann machines as associative memory in Generative Adversarial Networks between classical and quantum sampling
- Teacher-student learning for a binary perceptron with quantum fluctuations
- Efficient Algorithm for Binary Quadratic Problem by Column Generation and Quantum Annealing
- Annealing-Assisted Column Generation for Inequality-Constrained Combinatorial Optimization Problems
- Toward Practical Benchmarks of Ising Machines: A Case Study on the Quadratic Knapsack Problem
- Post-processing variationally scheduled quantum algorithm for constrained combinatorial optimization problems
- Individual subject evaluated difficulty of adjustable mazes generated using quantum annealing
- Online calibration scheme for training restricted Boltzmann machines with quantum annealing
- Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems
- Subgradient Method using Quantum Annealing for Inequality-Constrained Binary Optimization Problems