Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Discrete Optimization

Penalty and partitioning techniques to improve performance of QUBO solvers

Amit Verma, Mark W. Lewis

Published Jun 29, 2020• 90 citations
Publisher
DOI
10.1016/j.disopt.2020.100594

Related papers

A Study of Scalarisation Techniques for Multi-objective QUBO Solving

Mayowa Ayodele, Richard Allmendinger, Manuel López‐Ibáñez +1 more

arXiv:2210.11321•Lecture notes in operations research•Jan 1, 2023•3 citations

Techniques to enhance a QUBO solver for permutation-based combinatorial optimization

Siong Thye Goh, Jianyuan Bo, Sabrish Gopalakrishnan +1 more

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.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 9, 2022•10 citations

QUBO solver for combinatorial optimization problems with constraints

Fumiyo Takano, Motoi Suzuki, Y. Kobayashi +1 more

IEICE Technical Report; IEICE Tech. Rep.•Nov 21, 2019•7 citations

Quantum Annealing for Customer Segmentation: A Proof-of-Concept QUBO Framework for Supply Chain Clustering

Raphaël Bouchet, Alena Puchkova

This article investigates the potential of quantum clustering, specifi cally through quantum annealing, to enhance supply chain segmentation compared with classical K-Means. Using a proof-of-concept framework, clustering is translated into a Quadratic Unconstrained Binary Optimisation formulation, tested on customer datasets via both classical Simulated Annealing and D-Wave’s Leap hybrid solver, with penalty parameter optimisation introduced to address solver sensitivity. Performance is benchmarked against K-Means on runtime, accuracy metrics, and scalability, across dataset sizes from 200 to 5,000 points. Results show that while K-Means maintains superior inertia and stability, the hybrid quantum approach achieves faster solver-reported runtimes and, on a simplifi ed 200-point, two-feature benchmark, delivers improved silhouette, Davies-Bouldin, Calinski-Harabasz, and Dunn scores once penalties are optimised — metrics which, it is noted, reward the balanced partitions structurally favoured by the pairwise QUBO objective. However, scalability remains constrained by current qubit capacity and solver access, limiting practical deployment beyond mid-sized datasets. The study concludes that classical methods remain dominant for industrial-scale segmentation; the demonstrated framework, penalty-optimisation pipeline, and objective-level analysis nonetheless provide a documented foundation, grounded in a customer segmentation case study, upon which future quantum-assisted supply chain clustering can build as hardware matures.

•Nov 11, 2026•0 citations

QROSS: QUBO Relaxation Parameter optimisation via Learning Solver Surrogates

Tian Huang, Siong Thye Goh, Sabrish Gopalakrishnan +3 more

A popular method for solving a constrained combinatorial optimisation problem is to first convert it into a quadratic unconstrained binary optimisation (QUBO) problem, and solve it using a standard QUBO solver. However, this relaxation introduces hyper-parameters that balance the objective and penalty terms for the constraints, and their chosen values significantly impact performance. Hence, hyper-parameters tuning is important. Existing generic hyper-parameter tuning methods require multiple expensive calls to a QUBO solver, making them inefficient for performance critical applications when repeated solutions of similar combinatorial optimisation problems are required. In this paper, we propose the QROSS method, in which we build surrogate models of QUBO solvers via learning from solver data on a collection of instances of a problem. In this way, we are able capture the common structure of the instances and their interactions with the solver, and produce promising hyper-parameters with fewer calls to the QUBO solver. We take the Traveling Salesman Problem (TSP) as a case study, where we demonstrate QROSS finds better solutions with fewer calls to QUBO solver, compared with conventional hyper-parameter tuning techniques. Moreover, with simple adaptation methods, QROSS is shown to generalise well to out-of-distribution datasets and different types of QUBO solvers.

arXiv:2103.10695•IEEE International Conference on Distributed Computing Systems Workshops (ICDCSW)•Jul 1, 2021•5 citations

Penalty Weights in QUBO Formulations: Permutation Problems

Mayowa Ayodele

arXiv:2206.11040•Lecture notes in computer science•Jan 1, 2022•68 citations
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 article investigates the potential of quantum clustering, specifi cally through quantum annealing, to enhance supply chain segmentation compared with classical K-Means. Using a proof-of-concept framework, clustering is translated into a Quadratic Unconstrained Binary Optimisation formulation, tested on customer datasets via both classical Simulated Annealing and D-Wave’s Leap hybrid solver, with penalty parameter optimisation introduced to address solver sensitivity. Performance is benchmarked against K-Means on runtime, accuracy metrics, and scalability, across dataset sizes from 200 to 5,000 points. Results show that while K-Means maintains superior inertia and stability, the hybrid quantum approach achieves faster solver-reported runtimes and, on a simplifi ed 200-point, two-feature benchmark, delivers improved silhouette, Davies-Bouldin, Calinski-Harabasz, and Dunn scores once penalties are optimised — metrics which, it is noted, reward the balanced partitions structurally favoured by the pairwise QUBO objective. However, scalability remains constrained by current qubit capacity and solver access, limiting practical deployment beyond mid-sized datasets. The study concludes that classical methods remain dominant for industrial-scale segmentation; the demonstrated framework, penalty-optimisation pipeline, and objective-level analysis nonetheless provide a documented foundation, grounded in a customer segmentation case study, upon which future quantum-assisted supply chain clustering can build as hardware matures.
A popular method for solving a constrained combinatorial optimisation problem is to first convert it into a quadratic unconstrained binary optimisation (QUBO) problem, and solve it using a standard QUBO solver. However, this relaxation introduces hyper-parameters that balance the objective and penalty terms for the constraints, and their chosen values significantly impact performance. Hence, hyper-parameters tuning is important. Existing generic hyper-parameter tuning methods require multiple expensive calls to a QUBO solver, making them inefficient for performance critical applications when repeated solutions of similar combinatorial optimisation problems are required. In this paper, we propose the QROSS method, in which we build surrogate models of QUBO solvers via learning from solver data on a collection of instances of a problem. In this way, we are able capture the common structure of the instances and their interactions with the solver, and produce promising hyper-parameters with fewer calls to the QUBO solver. We take the Traveling Salesman Problem (TSP) as a case study, where we demonstrate QROSS finds better solutions with fewer calls to QUBO solver, compared with conventional hyper-parameter tuning techniques. Moreover, with simple adaptation methods, QROSS is shown to generalise well to out-of-distribution datasets and different types of QUBO solvers.