QC-CCG: Quantum-Classical Algorithm for Two-stage Adaptive Robust Optimization

Abstract

Quantum optimization provides a promising approach for solving large-scale combinatorial problems through quadratic unconstrained binary optimization (QUBO) formulations. However, integrating QUBO-based solvers into structured optimization frameworks while preserving solution guarantees remains a fundamental challenge. This paper develops a hybrid quantum-classical column-and-constraint generation (QCCG) framework for solving two-stage adaptive robust optimization problems with binary first-stage decisions and linear recourse under polyhedral uncertainty. The proposed approach reformulates the restricted master problem as a QUBO and solves it approximately using a quantum optimizer, while retaining a classical adversarial subproblem to compute worst-case recourse and certify solution quality. We construct a constraint-preserving QUBO encoding for inequality-constrained master problems using slack variables and penalty terms, enabling general mixed-integer structures to be mapped to quantum-compatible representations. To address inexactness arising from discretization, penalty modeling, and quantum optimization, we introduce a bound-adjustment mechanism that yields valid lower and upper bounds and provides a certified stopping criterion. We show that the proposed framework generalizes classical column-and-constraint generation and retains its convergence properties when the master problem is solved exactly. Numerical experiments on two-stage robust location-transportation problems demonstrate that the proposed hybrid approach achieves solution quality comparable to classical methods while reducing the computational burden associated with solving mixed-integer master problems, highlighting the potential of hybrid quantum-classical optimization for scalable decision-making under uncertainty.

12 pages