Quadratic unconstrained binary optimization (QUBO) provides problem formulations for various computational problems that can be solved with dedicated QUBO solvers, which can be based on classical or quantum computation. A common approach to constrained combinatorial optimization problems is to enforce the constraints in the QUBO formulation by adding penalization terms. Penalization introduces an additional hyperparameter that significantly affects the solver's efficacy: the relative weight between the objective terms and the penalization terms. We develop a pre-computation strategy for determining penalization weights with provable guarantees for Gibbs solvers and polynomial complexity for broad problem classes. Experiments across diverse problems and solver architectures, including large-scale instances on Fujitsu's Digital Annealer, show robust performance and order-of-magnitude speedups over existing heuristics.
Quadratic unconstrained binary optimization (QUBO) provides problem formulations for various computational problems that can be solved with dedicated QUBO solvers, which can be based on classical or quantum computation. A common approach to constrained combinatorial optimization problems is to enforce the constraints in the QUBO formulation by adding penalization terms. Penalization introduces an additional hyperparameter that significantly affects the solver's efficacy: the relative weight between the objective terms and the penalization terms. We develop a pre-computation strategy for determining penalization weights with provable guarantees for Gibbs solvers and polynomial complexity for broad problem classes. Experiments across diverse problems and solver architectures, including large-scale instances on Fujitsu's Digital Annealer, show robust performance and order-of-magnitude speedups over existing heuristics.
Quadratic unconstrained binary optimization (QUBO) provides problem formulations for various computational problems that can be solved with dedicated QUBO solvers, based on classical or quantum computation. A common approach to constrained combinatorial optimization problems is to enforce the constraints in the QUBO formulation by adding penalization terms. Penalization introduces an additional hyperparameter that significantly affects the solver's efficacy: the relative weight between the objective terms and the penalization terms. Here we study the problem of a priori determining suitable penalization weights from a foundational and practical perspective. We formally establish that finding its optimal value for Gibbs solvers is NP-hard even approximately and #P-hard exactly. This serves us as a motivation to develop a widely applicable heuristic strategy for determining suitable penalization weights, with provable guarantees for Gibbs solvers, and polynomial complexity for broad problem classes. Experiments across diverse problems and solver architectures, including large-scale instances on Fujitsu's Digital Annealer, show robust performance and order-of-magnitude speedups over existing heuristics. We further extend the strategy to quantum approximate optimization and demonstrate its performance on Quantinuum's H2-2 trapped-ion processor.
Quadratic unconstrained binary optimisation (QUBO) problems is a general class of combinatorial optimisation problems, which regained popularity after recent advances in quantum computing. Quantum-inspired technologies like Fujitsu's Digital Annealer (DA), based on simulated annealing, can solve QUBO problems much faster than traditional computers. Penalty methods can convert constrained optimisation problems into QUBO problems. However, existing exact methods of determining penalty weights are limited to specific QUBO problems and require manual analysis by experts in QUBO. Empirical methods are general but become computationally prohibitive for large problem sizes and do not guarantee that penalty weights preserve the feasibility of global optima. We present a simple, efficient, general method applicable to any QUBO to determine exact penalty weights. Such weights are simple upper-bounds of the smallest penalty weight guaranteeing that unconstrained global optima are the same as the feasible global optima. These bounds can be iteratively improved by sequential penalty methods which we also present. Experimental results with the DA on minimum cut, travelling salesman and multi-dimensional knapsack problems show the viability of the novel methodology hybridising exact and sequential methods. This work contributes towards general, automatic and scalable penalty methods in QUBO.
Quadratic unconstrained binary optimisation (QUBO) problems is a general class of combinatorial optimisation problems, which regained popularity after recent advances in quantum computing. Quantum-inspired technologies like Fujitsu’s Digital Annealer (DA), based on simulated annealing, can solve QUBO problems much faster than traditional computers. Penalty methods can convert constrained optimisation problems into QUBO problems. However, existing exact methods of determining penalty weights are limited to specific QUBO problems and require manual analysis by experts in QUBO. Empirical methods are general but become computationally prohibitive for large problem sizes and do not guarantee that penalty weights preserve the feasibility of global optima. We present a simple, efficient, general method applicable to any QUBO to determine exact penalty weights. Such weights are simple upper-bounds of the smallest penalty weight guaranteeing that unconstrained global optima are the same as the feasible global optima. These bounds can be iteratively improved by sequential penalty methods which we also present. Experimental results with the DA on minimum cut, travelling salesman and multi-dimensional knapsack problems show the viability of the novel methodology hybridising exact and sequential methods. This work contributes towards general, automatic and scalable penalty methods in QUBO.
Quantum computing has emerged as a promising alternative for solving combinatorial optimization problems. The standard approach for encoding optimization problems on quantum processing units (QPUs) involves transforming them into their Quadratic Unconstrained Binary Optimization (QUBO) representation. However, encoding constraints of optimization problems, particularly inequality constraints, into QUBO requires additional variables, which results in more qubits. Considering the limited availability of qubits in NISQ machines, existing encoding methods fail to scale due to their reliance on large numbers of qubits. We propose a generalized exponential penalty framework for QUBO inequality constraints inspired by a class of exponential functions, which we call exponential penalization. This paper presents an encoding strategy for inequality constraints in combinatorial optimization problems, inspired by a class of exponential functions, which we call exponential penalization. The initial idea of using exponential penalties for QUBO formulation was introduced by Montanez-Barrera et al. by applying a specific exponential function to reduce qubit requirements. In this work, we extend that approach by conducting a comprehensive study on a broader class of exponential functions, analyzing their theoretical properties and empirical performance. Our experimental results demonstrate that an exponential penalization achieves 57%, 83% qubit number reduction for Bin Packing Problem (BPP) and Traveling Salesman Problem (TSP), respectively. And we demonstrate comparable solution quality to classical with a probability of 6% and 21% accuracy for BPP with 8 and TSP with 12 qubits, respectively.
Many combinatorial optimization problems can be formulated as a problem to determine the order of sequence or to find a corresponding mapping of the objects. We call such problems permutation-based optimization problems. Many such problems can be formulated as a quadratic unconstrained binary optimization (QUBO) or Ising model by introducing a penalty coefficient to the permutation constraint terms. While classical and quantum annealing approaches have been proposed to solve QUBOs to date, they face issues with optimality and feasibility. Here we treat a given QUBO solver as a black box and propose techniques to enhance its performance. First, to ensure an effective search for good quality solutions, a smooth energy landscape is needed; we propose a data scaling approach that reduces the amplitudes of the input without compromising optimality. Second, we need to tune the penalty coefficient. In this paper, we illustrate that for certain problems, it suffices to tune the parameter by performing random sampling on the penalty coefficients to achieve good performance. Finally, to handle possible infeasibility of the solution, we introduce a polynomial-time projection algorithm. We apply these techniques along with a divide-and-conquer strategy to solve some large-scale permutation-based problems and present results for TSP and QAP.
This paper proposes a novel framework for automatically setting penalty weights in the Quadratic Unconstrained Binary Optimization (QUBO) to handle problems with multiple constraints. Quantum computing and quantum-inspired methods have gained prominence, with QUBO models widely used for their unified representation of optimization problems. However, QUBO performance is highly sensitive to penalty weight settings, especially in multiple constraints scenarios, where setting different penalty weights to different constraints may further affect performance. Existing methods for setting common penalty weights for all constraints in QUBO can be generally categorized into manual methods based on expert experience, exact methods based on the objective function values, and sequential methods based on searching within an upper bound. This study introduces a novel framework for multiple constraints optimization that utilizes exact and sequential binary search methods to determine common penalty weight while integrating constraint sensitivity analysis to adjust each penalty weight dynamically. This approach enhances the efficiency and quality of QUBO solutions. Experimental results on the Travelling Salesman Problem show that the proposed framework achieves superior solution quality and feasibility on both the D-Wave quantum annealer and classical simulated annealing solvers, outperforming traditional methods and demonstrating strong adaptability.