Formulation symmetry in mixed-integer programming (MIP) can hinder solver performance by inducing redundant search, but detecting such symmetries is also a significant computational challenge. This paper explores the potential for quantum computing to handle symmetry detection. Quantum is a promising alternative to classical compute, but this emerging technology has limited hardware capacity in terms of input problem size. This paper explores the use of Quadratic Unconstrained Binary Optimization (QUBO) models for symmetry detection, as QUBO is the canonical format for quantum optimization platforms. To help address the input size bottleneck, we develop full, reduced, and decomposed QUBO as well as QUBO-Plus formulations for MIP symmetry detection. Computational experiments on the MIPLIB 2017 benchmark are used to estimate the quantum computing resources needed for practical problems.
Formulation symmetry in mixed-integer programming (MIP) can hinder solver performance by inducing redundant search, but detecting such symmetries is also a significant computational challenge. This paper explores the potential for quantum computing to handle symmetry detection. Quantum is a promising alternative to classical compute, but this emerging technology has limited hardware capacity in terms of input problem size. This paper explores the use of Quadratic Unconstrained Binary Optimization (QUBO) models for symmetry detection, as QUBO is the canonical format for quantum optimization platforms. To help address the input size bottleneck, we develop full, reduced, and decomposed QUBO as well as QUBO-Plus formulations for MIP symmetry detection. Computational experiments on the MIPLIB 2017 benchmark are used to estimate the quantum computing resources needed for practical problems.
Quantum optimization shows significant potential in tackling complex combinatorial challenges, prompting our research exploration into the domain of quantum computing to address the Bin Packing Problem (BPP) through Quadratic Unconstrained Binary Optimization (QUBO) formulations. This work-in-progress paper outlines our proposal for a thorough study that encompasses classical bin packing formulations, initiating with the Mixed Integer Linear Program, followed by a comparative analysis of the corresponding QUBO representations, and adopting a structured approach of Quantum Annealing on the D-Wave machine. While our work is still in progress, continuous comparative analyses are being conducted to evaluate various QUBO formulations, derived from diverse classical bin packing models, aiming to identify the most efficient QUBO for addressing the BPP. On another front, efforts are dedicated to refining the solution process further, with a focus on enhancing the precision of the selected QUBO formulation.
Recent advances in quantum computing and the increasing availability of quantum hardware have substantially enhanced the practical relevance of quantum approaches to discrete optimization. Among these, the Quadratic Unconstrained Binary Optimization (QUBO) formulation provides a unifying modeling framework for a broad class of NP-hard problems and is naturally suited to quantum computing and quantum-inspired algorithms. Location science, network design, and logistics represent core application domains of discrete optimization, combining high practical impact with substantial computational challenges. In this work, we develop QUBO formulations for several fundamental problems in these domains, including a nonlinear integer formulation of the Discrete Ordered Median Problem (DOMP). Beyond their modeling relevance, these QUBO formulations serve as representative benchmark problems for assessing quantum algorithms and quantum hardware. We further derive a tight bound for the penalty parameter ensuring equivalence between the QUBO formulation and its underlying integer program. Finally, we conduct a comprehensive computational study using QAOA, WS-QAOA, and classical heuristics for QUBO instances of the p-Median Problem and the Fixed-Charge Facility Location Problem (FCFLP), and introduce two effective warm-start strategies for WS-QAOA based on its linear programming relaxation.
Quantum computing (QC) is emerging as a new computing resource that could be superior to conventional computing (CC) for certain classes of optimization problems. However, in principle QC can only solve unconstrained binary programming problems, while mixed-integer linear programming (MIP) is of most interest in practice. We attempt to bridge the gap between the capability of QC and real-world applications by developing a new approach for MIP. The idea is decomposing the MIP into binary programming and linear programming (LP) problems, which are respectively solved by QC and conventional computing. We formalize a decomposition approach that ensures that with a sufficient number of back and forth iterations, the algorithm can reach the optimal solution of the original MIP problem. The algorithm is tested on a 2000Q D-Wave quantum processing units (QPU) and is shown to be effective for small-scaled test cases.
Quadratic Unconstrained Binary Optimization (QUBO) is a central formulation for combinatorial optimization and has gained increasing attention due to its compatibility with quantum, hybrid quantum-classical, and quantum-inspired solvers. However, translating natural-language problem descriptions into correct QUBO formulations remains difficult, requiring the identification of binary variables, constraints, objective functions, penalty terms, and suitable penalty weights. This process is time-consuming and often demands substantial domain expertise. To address this challenge, we propose an end-to-end multi-agent framework that automatically generates QUBO formulations from natural-language problem descriptions, supported by structured or unstructured test cases. To evaluate its performance, We also introduce QUBOBench, a benchmark containing 100 combinatorial optimization problems across 12 application domains, curated from peer-reviewed literature, competitions, and canonical NP-hard problems. Experimental results show that our framework achieves 68% accuracy on QUBOBench, outperforming a direct single-call baseline by 22%. Further analysis identifies iterative self-repair as the most important component contributing to improved performance. The data and code are open-sourced at https://quitttcat.github.io/QuantumQUBOAgent.
Quantum computing is widely discussed for its potential to solve challenging optimization problems much faster. However, real-world airline problem sizes currently exceed the capabilities of existing quantum hardware. Preparing for larger quantum hardware requires developing and benchmarking problem formulations most suitable for quantum implementation. In this study, we use the crew pairing problem from aviation as an use case to benchmark different problem formulations: a set partitioning model and two compact formulations, a constrained flow assignment problem and a satisfiability problem (SAT). For classical benchmarking we solve these formulations using mixed integer programming and SAT solvers. For quantum benchmarking we translate the formulations into quadratic unconstrained binary optimization and Ising formulations. Our benchmarking shows that the problem formulations lead to different classical and quantum properties. Among the formulations considered, the SAT formulation emerges as the most promising candidate for future implementation on quantum hardware with the lowest share of non-zero elements and highest spectral gap, despite its larger ratio of linear term coefficients.
The emergence of specialized hardware, such as quantum computers and Digital/CMOS annealers, and the slowing of performance growth of general-purpose hardware raises an important question for our community: how can the high-performance, specialized solvers be used for planning and scheduling problems? In this work, we focus on the job-shop scheduling problem (JSP) and Quadratic Unconstrained Binary Optimization (QUBO) models, the mathematical formulation shared by a number of novel hardware platforms. We study two direct QUBO models of JSP and propose a novel large neighborhood search (LNS) approach, that hybridizes a QUBO model with constraint programming (CP). Empirical results show that our LNS approach significantly outperforms classical CP-based LNS methods and a mixed integer programming model, while being competitive with CP for large problem instances. This work is the first approach that we are aware of that can solve non-trivial JSPs using QUBO hardware, albeit as part of a hybrid algorithm.