2024/04/04 by Oksana Pichugina, Pichugina, Oksana, Yingcong Tan +3
Computer Science · Decision Sciences · Engineering · #Constraint Satisfaction and Optimization #FOS: Mathematics #FOS: Physical sciences #Optimization and Control (math.OC) #Quantum Physics (quant-ph) #Scheduling and Timetabling Solutions #Traffic Prediction and Management Techniques
paper · pdf · doi:10.48550/arxiv.2404.03610
openalex publication_date 2024/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
With the advances in customized hardware for quantum annealing and digital/CMOS Annealing, Quadratic Unconstrained Binary Optimization (QUBO) models have received growing attention in the optimization literature. Motivated by an existing general-purpose approach that derives QUBO models from binary linear programs (BLP), we propose a novel Multilevel Constraint Transformation Scheme (MLCTS) that derives QUBO models with fewer ancillary binary variables. We formulate sufficient conditions for the existence of a compact QUBO formulation (i.e., in the original BLP decision space) in terms of constraint levelness and demonstrate the flexibility and applicability of MLCTS on synthetic examples and several well-known combinatorial optimization problems, i.e., the Maximum 2-Satisfiability Problem, the Linear Ordering Problem, the Community Detection Problem, and the Maximum Independence Set Problem. For a proof-of-concept, we compare the performance of two QUBO models for the latter problem on both a general-purpose software-based solver and a hardware-based QUBO solver. The MLCTS-derived models demonstrate significantly better performance for both solvers, in particular, solving up to seven times more instances with the hardware-based approach.