dc.contributor.author | Garcia, MD | |
dc.contributor.author | Ayodele, M | |
dc.contributor.author | Moraglio, A | |
dc.date.accessioned | 2022-04-05T09:33:04Z | |
dc.date.issued | 2022-07-19 | |
dc.date.updated | 2022-04-05T08:23:09Z | |
dc.description.abstract | 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. | en_GB |
dc.description.sponsorship | Fujitsu Laboratories of Europe Limited | en_GB |
dc.identifier.citation | GECCO 2022: Genetic and Evolutionary Computation Conference, 9 - 13 July 2022, Boston, US, pp. 184 - 187 | en_GB |
dc.identifier.doi | 10.1145/3520304.3528925 | |
dc.identifier.uri | http://hdl.handle.net/10871/129275 | |
dc.identifier | ORCID: 0000-0003-4782-6590 (Moraglio, Alberto) | |
dc.language.iso | en | en_GB |
dc.publisher | Association for Computing Machinery (ACM) | en_GB |
dc.rights | © 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM. | en_GB |
dc.subject | Quadratic unconstrained binary optimisation | en_GB |
dc.subject | constraint handling | en_GB |
dc.subject | penalty weight | en_GB |
dc.subject | simulated annealing | en_GB |
dc.subject | Digital Annealer | en_GB |
dc.title | Exact and sequential penalty weights in quadratic unconstrained binary optimisation with a digital annealer | en_GB |
dc.type | Conference paper | en_GB |
dc.date.available | 2022-04-05T09:33:04Z | |
dc.identifier.isbn | 978-1-4503-9268-6 | |
dc.description | This is the author accepted manuscript. The final version is available from ACM via the DOI in this record | en_GB |
dc.rights.uri | http://www.rioxx.net/licenses/all-rights-reserved | en_GB |
dcterms.dateAccepted | 2022-03-25 | |
rioxxterms.version | AM | en_GB |
rioxxterms.licenseref.startdate | 2022-03-25 | |
rioxxterms.type | Conference Paper/Proceeding/Abstract | en_GB |
refterms.dateFCD | 2022-04-05T08:23:13Z | |
refterms.versionFCD | AM | |
refterms.dateFOA | 2022-07-29T08:55:36Z | |
refterms.panel | B | en_GB |