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.
%0 Generic
%1 ayodele2022multiobjective
%A Ayodele, Mayowa
%A Allmendinger, Richard
%A López-Ibáñez, Manuel
%A Parizy, Matthieu
%D 2022
%K quantumcomputing
%R 10.1145/3512290.3528698
%T Multi-objective QUBO Solver: Bi-objective Quadratic Assignment
%U http://arxiv.org/abs/2205.13399
%X 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.
@misc{ayodele2022multiobjective,
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.},
added-at = {2023-06-21T18:44:58.000+0200},
author = {Ayodele, Mayowa and Allmendinger, Richard and López-Ibáñez, Manuel and Parizy, Matthieu},
biburl = {https://www.bibsonomy.org/bibtex/202572f11e5b2f552393b7bd57a7fdd4b/cmcneile},
description = {Multi-objective QUBO Solver: Bi-objective Quadratic Assignment},
doi = {10.1145/3512290.3528698},
interhash = {3c01689580b550484b761be0c5878d0c},
intrahash = {02572f11e5b2f552393b7bd57a7fdd4b},
keywords = {quantumcomputing},
note = {cite arxiv:2205.13399Comment: The Genetic and Evolutionary Computation Conference 2022 (GECCO22)},
timestamp = {2023-06-21T18:44:58.000+0200},
title = {Multi-objective QUBO Solver: Bi-objective Quadratic Assignment},
url = {http://arxiv.org/abs/2205.13399},
year = 2022
}