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.
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.
The bin packing is a well-known NP-Hard problem in the domain of artificial intelligence, posing significant challenges in finding efficient solutions. Conversely, recent advancements in quantum technologies have shown promising potential for achieving substantial computational speedup, particularly in certain problem classes, such as combinatorial optimization. In this study, we introduce QAL-BP, a novel Quadratic Unconstrained Binary Optimization (QUBO) formulation designed specifically for bin packing and suitable for quantum computation. QAL-BP utilizes the Augmented Lagrangian method to incorporate the bin packing constraints into the objective function while also facilitating an analytical estimation of heuristic, but empirically robust, penalty multipliers. This approach leads to a more versatile and generalizable model that eliminates the need for empirically calculating instance-dependent Lagrangian coefficients, a requirement commonly encountered in alternative QUBO formulations for similar problems. To assess the effectiveness of our proposed approach, we conduct experiments on a set of bin packing instances using a real Quantum Annealing device. Additionally, we compare the results with those obtained from two different classical solvers, namely simulated annealing and Gurobi. The experimental findings not only confirm the correctness of the proposed formulation, but also demonstrate the potential of quantum computation in effectively solving the bin packing problem, particularly as more reliable quantum technology becomes available.
Quantum computing approaches, such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), have emerged as promising candidates for solving combinatorial optimization problems. Since these approaches typically work with Quadratic Unconstrained Binary Optimization (QUBO) problems, constraints, when present, are commonly encoded as penalty terms. Conventional approaches to incorporate inequality constraints into QUBO formulations additionally require the introduction of slack variables, increasing the required number of qubits. The Knapsack and Bin Packing problems are optimization problems with such inequality constraints. We show that the number of slack variables required to formulate the Knapsack problem as a QUBO problem can be reduced using certain properties specific to this problem. Moreover, we present two separate strategies for the Knapsack and Bin Packing problems that avoid using the costly slack variables altogether. Instead, both strategies solve several QUBO problems, with varying penalty constants, such that at least one of them is a good representation of the given optimization problem. Numerical simulations of QAOA, as well as experiments on a D-Wave quantum annealer, show that these slack-less approaches can improve performance compared to the conventional slack variable method (in terms of success probability), even when the latter is allowed to vary penalty constants too.
Combinatorial problems pose significant challenges, especially for large-scale instances. A promising approach to addressing these challenges involves quadratic unconstrained binary optimization (QUBO) models, a key framework in quantum computing. QUBO formulations require tailored approaches owing to their unique characteristics and the hardware constraints of quantum systems. This paper focuses on the QUBO formulations of the Hamiltonian cycle problem (HCP). We analyse three QUBO formulations for the HCP, including two inspired by Lagrangian relaxation techniques, where penalties may result in negative costs for certain solutions but are balanced within the model. A preprocessing methodology is also introduced. To evaluate these models, we employ D-Wave quantum annealers, which feature a fixed qubit topology and impose strict resource constraints. The mapping of QUBOs on to this architecture highlights the importance of efficient model design. Through experimental studies, we analyse the performance of the proposed QUBOs with and without preprocessing. This article is part of the theme issue 'Quantum theory and topology in models of decision making (Part 2)'.
This paper explores the application of Quantum Annealing (QA) to the field of combinatorial optimization. The core idea is to leverage the principles of quantum mechanics, specifically quantum tunneling, to efficiently solve complex optimization problems. We present a framework for utilizing QA to tackle problems represented as quadratic unconstrained binary optimization (QUBO) models. The methodology focuses on mapping the problem's constraints and objective function into a form suitable for QA hardware. We discuss the challenges involved in this mapping process, including the limitations of current QA devices and the need for careful problem formulation. Furthermore, we analyze the potential advantages of QA over classical optimization techniques, particularly concerning the exploration of a wider solution space. The research highlights the promise of QACO as a viable approach for tackling computationally demanding combinatorial optimization tasks, offering a novel method to enhance optimization efficiency.
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.
In recent years, the Flow shop Scheduling Problem (FSP) has gained significant attention, prompting researchers to develop various methods, from conventional to hybrid optimization algorithms. Driven by the rapid growth of quantum computing capabilities, quantum approaches applied to optimization problems have attracted an increasing research effort. This work attempts to solve the permutation flow shop scheduling problem using quantum annealing by formulating the problem as a Quadratic Unconstrained Binary Optimization model (QUBO). Two QUBO formulations tailored to address the FSP are used. The first formulation is based on the position-based modelling while the second is based on five approximations of FSP as a Traveling Salesman Problem (TSP). The QUBO formulations are tested, using D-Wave's quantum annealers, on the well-known Taillard FSP benchmark and compared against each other. Results show that the proposed position-based QUBO reaches better solutions than the TSP-based QUBOs. This work is an attempt to highlight the increasing effectiveness of quantum annealers in addressing complex optimization problems and their limitations compared to conventional classical methods.