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

arXiv:2205.13399 · Genetic and Evolutionary Computation Conference (GECCO)

Multi-objective QUBO solver

Mayowa Ayodele, Richard Allmendinger, Manuel López‐Ibáñez, Matthieu Parizy

Published Jul 8, 2022• 13 citations
arXivHTMLPDF

Abstract

Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu's Digital Annealer (DA) and D-Wave's Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum. We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.

DOI
10.1145/3512290.3528698

Related papers

Multi-objective QUBO Solver: Bi-objective Quadratic Assignment Problem

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

Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu’s Digital Annealer (DA) and D-Wave’s Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum.We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.

•Mar 25, 2022•0 citations

Quantum and Digital Annealing for the Quadratic Assignment Problem

Philippe Codognet, Daniel Díaz, Salvador Pinto Abreu

The Quadratic Assignment Problem is a a classical constrained optimization problem used to model many real-life applications. We present experiments in solving the Quadratic Assignment Problem by means of Quantum Annealing and Quantum-inspired Annealing. We describe how to model this classical combinatorial problem in terms of QUBO (Quadratic Unconstrained Binary optimization) for implementing it on hardware solvers based on quantum or quantum-inspired annealing (D-Wave, Fujitsu Digital Annealing Unit and Fixstars Amplify Annealing Engine). We present performance result for these implementations and compare them with well established metaheuristic solvers on classical hardware, such as Robust Tabu Search and External Optimization.

IEEE International Conference on Quantum Software (QSW)•Jul 1, 2022•12 citations

Exact and sequential penalty weights in quadratic unconstrained binary optimisation with a digital annealer

MD Garcia (21941009), M Ayodele (21491936), A Moraglio (21844982)

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.

•Aug 1, 2025•0 citations

Multi-Objective Optimization Technique Based on QUBO and an Ising Machine

Hiroshi Ikeda, Takashi Yamazaki

With an increase in the complexity of society, solving multi-objective optimization problems (MOPs) has become crucial. In this study, we introduced a novel method called “quadratic unconstrained binary optimization based on the weighted normal” for solving MOPs using Ising machines, such as quantum annealing and digital annealer (DA), in the field of combinatorial optimization. The proposed method applies the penalty-based boundary intersection method to Ising machines under a setting limited to linear objective functions and maximizes the speed and performance of the DA, which is a quadratic unconstrained binary optimization-specific solver. We demonstrated the effectiveness of the proposed method by solving a real-world problem with a nonconvex shaped Pareto front (component combination problem). The results suggested that the proposed method could handle both convex- and nonconvex-shaped Pareto fronts, expanding the potential applications of Ising machines to solving complex MOPs. This development could significantly enhance decision-making processes, particularly in achieving sustainable development goals.

IEEE Access•Jan 1, 2024•5 citations

Comparing the Digital Annealer with Classical Evolutionary Algorithm

Mayowa Ayodele

In more recent years, there has been increasing research interest in exploiting the use of application specific hardware for solving optimisation problems. Examples of solvers that use specialised hardware are IBM's Quantum System One and D-wave's Quantum Annealer (QA) and Fujitsu's Digital Annealer (DA). These solvers have been developed to optimise problems faster than traditional meta-heuristics implemented on general purpose machines. Previous research has shown that these solvers (can optimise many problems much quicker than exact solvers such as GUROBI and CPLEX. Such conclusions have not been made when comparing hardware solvers with classical evolutionary algorithms. Making a fair comparison between traditional evolutionary algorithms, such as Genetic Algorithm (GA), and the DA (or other similar solvers) is challenging because the later benefits from the use of application specific hardware while evolutionary algorithms are often implemented on general-purpose machines. Moreover, quantum or quantum-inspired solvers are limited to solving problems in a specific format. A common formulation used is Quadratic Unconstrained Binary Optimisation (QUBO). Many optimisation problems are however constrained and have natural representations that are non-binary. Converting such problems to QUBO can lead to more problem difficulty and/or larger search space. The question addressed in this paper is whether quantum or quantum-inspired solvers can optimise QUBO transformations of combinatorial optimisation problems faster than classical evolutionary algorithms applied to the same problems in their natural representations. We show that the DA often present better average objective function values than GA on Travelling Salesman, Quadratic Assignment and Multi-dimensional Knapsack Problem instances.

arXiv:2205.13586•May 26, 2022•2 citations

Exact and sequential penalty weights in quadratic unconstrained binary optimisation with a digital annealer

Marcos Diez García, Mayowa Ayodele, Alberto Moraglio

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.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 9, 2022•24 citations
Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu's Digital Annealer (DA) and D-Wave's Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum. We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.
Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu’s Digital Annealer (DA) and D-Wave’s Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum.We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.
The Quadratic Assignment Problem is a a classical constrained optimization problem used to model many real-life applications. We present experiments in solving the Quadratic Assignment Problem by means of Quantum Annealing and Quantum-inspired Annealing. We describe how to model this classical combinatorial problem in terms of QUBO (Quadratic Unconstrained Binary optimization) for implementing it on hardware solvers based on quantum or quantum-inspired annealing (D-Wave, Fujitsu Digital Annealing Unit and Fixstars Amplify Annealing Engine). We present performance result for these implementations and compare them with well established metaheuristic solvers on classical hardware, such as Robust Tabu Search and External Optimization.
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.
With an increase in the complexity of society, solving multi-objective optimization problems (MOPs) has become crucial. In this study, we introduced a novel method called “quadratic unconstrained binary optimization based on the weighted normal” for solving MOPs using Ising machines, such as quantum annealing and digital annealer (DA), in the field of combinatorial optimization. The proposed method applies the penalty-based boundary intersection method to Ising machines under a setting limited to linear objective functions and maximizes the speed and performance of the DA, which is a quadratic unconstrained binary optimization-specific solver. We demonstrated the effectiveness of the proposed method by solving a real-world problem with a nonconvex shaped Pareto front (component combination problem). The results suggested that the proposed method could handle both convex- and nonconvex-shaped Pareto fronts, expanding the potential applications of Ising machines to solving complex MOPs. This development could significantly enhance decision-making processes, particularly in achieving sustainable development goals.
In more recent years, there has been increasing research interest in exploiting the use of application specific hardware for solving optimisation problems. Examples of solvers that use specialised hardware are IBM's Quantum System One and D-wave's Quantum Annealer (QA) and Fujitsu's Digital Annealer (DA). These solvers have been developed to optimise problems faster than traditional meta-heuristics implemented on general purpose machines. Previous research has shown that these solvers (can optimise many problems much quicker than exact solvers such as GUROBI and CPLEX. Such conclusions have not been made when comparing hardware solvers with classical evolutionary algorithms. Making a fair comparison between traditional evolutionary algorithms, such as Genetic Algorithm (GA), and the DA (or other similar solvers) is challenging because the later benefits from the use of application specific hardware while evolutionary algorithms are often implemented on general-purpose machines. Moreover, quantum or quantum-inspired solvers are limited to solving problems in a specific format. A common formulation used is Quadratic Unconstrained Binary Optimisation (QUBO). Many optimisation problems are however constrained and have natural representations that are non-binary. Converting such problems to QUBO can lead to more problem difficulty and/or larger search space. The question addressed in this paper is whether quantum or quantum-inspired solvers can optimise QUBO transformations of combinatorial optimisation problems faster than classical evolutionary algorithms applied to the same problems in their natural representations. We show that the DA often present better average objective function values than GA on Travelling Salesman, Quadratic Assignment and Multi-dimensional Knapsack Problem instances.
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.