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.
Quantum computing has emerged as a new tool for solving combinatorial optimization problems. Quantum optimization approaches usually operate on the subclass of Quadratic Unconstrained Binary Optimization (QUBO) problems. Many optimization problems can be reformulated in this form, though there are often multiple ways to do so. The choice of formulation can considerably affect the performance of QUBO solvers in practice. In this work, we study QUBO formulations of the Knapsack problem, a canonical example of a problem with inequality constraints. In the standard formulation these constraints are converted into penalty terms, which requires additional slack variables. Here, we investigate three more resource-efficient approaches for formulating the Knapsack as a QUBO. The first two modify the standard formulation, either by deriving a smaller penalty constant or by reducing the number of slack variables. The third approach is a wholly different method, which avoids the use of slack variables entirely. All three approaches increase the probability of finding the optimal solution, both in simulations of the linear ramp Quantum Approximate Optimization Algorithm (LR-QAOA) and on a D-Wave quantum annealer. The slackless method performs best, increasing success probabilities by several orders of magnitude even for relatively small problem sizes.
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.