A Study of Scalarisation Techniques for Multi-objective QUBO Solving

Mayowa Ayodele (), Richard Allmendinger (), Manuel López-Ibáñez () and Matthieu Parizy ()
Additional contact information
Mayowa Ayodele: Fujitsu Research of Europe
Richard Allmendinger: The University of Manchester
Manuel López-Ibáñez: The University of Manchester
Matthieu Parizy: Fujitsu Limited

Chapter Chapter 47 in Operations Research Proceedings 2022, 2023, pp 393-399 from Springer

Abstract: Abstract In recent years, there has been significant research interest in solving Quadratic Unconstrained Binary Optimisation (QUBO) problems. Physics-inspired optimisation algorithms have been proposed for deriving optimal or sub-optimal solutions to QUBOs. These methods are particularly attractive within the context of using specialised hardware, such as quantum computers, application specific CMOS and other high performance computing resources for solving optimisation problems. Examples of such solvers are D-wave’s Quantum Annealer and Fujitsu’s Digital Annealer. These solvers are then applied to QUBO formulations of combinatorial optimisation problems. Quantum and quantum-inspired optimisation algorithms have shown promising performance when applied to academic benchmarks as well as real-world problems. However, QUBO solvers are single objective solvers. To make them more efficient at solving problems with multiple objectives, a decision on how to convert such multi-objective problems to single-objective problems need to be made. In this study, we compare methods of deriving scalarisation weights when combining two objectives of the cardinality constrained mean-variance portfolio optimisation problem into one. We show significant performance improvement (measured in terms of hypervolume) when using a method that iteratively fills the largest space in the Pareto front compared to a naïve approach using uniformly generated weights.

Keywords: Digital Annealer; QUBO; Multi-objective optimisation (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnopch:978-3-031-24907-5_47

Ordering information: This item can be ordered from
http://www.springer.com/9783031249075

DOI: 10.1007/978-3-031-24907-5_47

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().