Improving Performance in Combinatorial Optimization Problems with
Inequality Constraints: An Evaluation of the Unbalanced Penalization Method
on D-Wave Advantage
- URL: http://arxiv.org/abs/2305.18757v1
- Date: Tue, 30 May 2023 05:40:50 GMT
- Title: Improving Performance in Combinatorial Optimization Problems with
Inequality Constraints: An Evaluation of the Unbalanced Penalization Method
on D-Wave Advantage
- Authors: J. A. Montanez-Barrera, Pim van den Heuvel, Dennis Willsch, Kristel
Michielsen
- Abstract summary: A new method known as unbalanced penalization has been presented to avoid using slack variables.
This work tests the unbalanced penalization method using real quantum hardware on D-Wave Advantage for the traveling salesman problem (TSP)
The results show that the unbalanced penalization method outperforms the solutions found using slack variables.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Combinatorial optimization problems are one of the target applications of
current quantum technology, mainly because of their industrial relevance, the
difficulty of solving large instances of them classically, and their
equivalence to Ising Hamiltonians using the quadratic unconstrained binary
optimization (QUBO) formulation. Many of these applications have inequality
constraints, usually encoded as penalization terms in the QUBO formulation
using additional variables known as slack variables. The slack variables have
two disadvantages: (i) these variables extend the search space of optimal and
suboptimal solutions, and (ii) the variables add extra qubits and connections
to the quantum algorithm. Recently, a new method known as unbalanced
penalization has been presented to avoid using slack variables. This method
offers a trade-off between additional slack variables to ensure that the
optimal solution is given by the ground state of the Ising Hamiltonian, and
using an unbalanced heuristic function to penalize the region where the
inequality constraint is violated with the only certainty that the optimal
solution will be in the vicinity of the ground state. This work tests the
unbalanced penalization method using real quantum hardware on D-Wave Advantage
for the traveling salesman problem (TSP). The results show that the unbalanced
penalization method outperforms the solutions found using slack variables and
sets a new record for the largest TSP solved with quantum technology.
Related papers
- Inequality constraints in variational quantum circuits with qudits [1.0923877073891446]
Quantum optimization is emerging as a prominent candidate for exploiting the capabilities of near-term quantum devices.
Here, we study an alternative direct implementation of inequality constraints within the QAOA algorithm, achieved using qudit-SUM gates.
We find that the direct implementation of the inequality penalties vastly outperforms the slack variables method, especially when studying real-world inspired problems with many constraints.
arXiv Detail & Related papers (2024-10-10T07:32:38Z) - Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
We show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario.
We follow by submitting instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios.
arXiv Detail & Related papers (2024-06-11T19:59:05Z) - Neural Time-Reversed Generalized Riccati Equation [60.92253836775246]
Hamiltonian equations offer an interpretation of optimality through auxiliary variables known as costates.
This paper introduces a novel neural-based approach to optimal control, with the aim of working forward-in-time.
arXiv Detail & Related papers (2023-12-14T19:29:37Z) - QSlack: A slack-variable approach for variational quantum semi-definite
programming [5.0579795245991495]
Quantum computers could provide a speedup over the best known classical algorithms.
We show how to solve optimization problems involving semi-definite and linear programs.
We show that our implementations of both the primal and dual for these problems approach the ground truth.
arXiv Detail & Related papers (2023-12-06T19:00:01Z) - Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
We present an alternative method that does not require extra slack variables.
We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem.
This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
arXiv Detail & Related papers (2022-11-25T06:05:18Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
Constrained optimization problems abound in industry, from portfolio optimization to logistics.
One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space.
In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
arXiv Detail & Related papers (2022-11-16T18:59:54Z) - Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
In this paper, we develop a simple yet efficient approach for the problem of comparing uncertain quantities.
We recast inner optimization in the Lagrangian as a learning problem for surrogate approximation, which bypasses apparent intractability.
The proposed light-SD demonstrates superior performance on several representative problems ranging from finance to supply chain management.
arXiv Detail & Related papers (2022-11-14T21:54:31Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem.
Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
arXiv Detail & Related papers (2022-11-01T07:52:47Z) - Modeling Linear Inequality Constraints in Quadratic Binary Optimization
for Variational Quantum Eigensolver [0.0]
This paper introduces the use of tailored variational forms for variational quantum eigensolver.
Four constraints that usually appear in several optimization problems are modeled.
The main advantage of the proposed methodology is that the number of parameters on the variational form remain constant.
arXiv Detail & Related papers (2020-07-26T23:36:22Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications.
Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem.
In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
arXiv Detail & Related papers (2020-03-11T13:52:41Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.