Translating Constraints into QUBOs for the Quadratic Knapsack Problem

Tariq Bontekoe; Frank Phillipson; Ward van der Schoot

doi:10.1007/978-3-031-36030-5_8

Translating Constraints into QUBOs for the Quadratic Knapsack Problem

Tariq Bontekoe
, Frank Phillipson^*
, Ward van der Schoot

^*Corresponding author for this work

Information Systems

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

6 Citations (Scopus)

670 Downloads (Pure)

Abstract

One of the first fields where quantum computing will likely show its use is optimisation. Many optimisation problems naturally arise in a quadratic manner, such as the quadratic knapsack problem. The current state of quantum computers requires these problems to be formulated as a quadratic unconstrained binary optimisation problem, or QUBO. Constrained quadratic binary optimisation can be translated into QUBOs by translating the constraint. However, this translation can be made in several ways, which can have a large impact on the performance when solving the QUBO. We show six different formulations for the quadratic knapsack problem and compare their performance using simulated annealing. The best performance is obtained by a formulation that uses no auxiliary variables for modelling the inequality constraint.

Original language	English
Title of host publication	Computational Science – ICCS 2023
Subtitle of host publication	23rd International Conference Prague, Czech Republic, July 3–5, 2023 Proceedings, Part V
Editors	Jiří Mikyška, Clélia de Mulatier, Maciej Paszynski, Valeria Krzhizhanovskaya, Jack Dongarra, Peter Sloot
Place of Publication	Cham
Publisher	Springer
Pages	90-107
Number of pages	18
ISBN (Print)	9783031360299, 9783031360305
DOIs	https://doi.org/10.1007/978-3-031-36030-5_8
Publication status	Published - 26-Jun-2023
Event	Computational Science – ICCS 2023: 23rd International Conference - Prague, Czech Republic Duration: 3-Jul-2023 → 5-Jul-2023

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	14077
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Computational Science – ICCS 2023
Country/Territory	Czech Republic
City	Prague
Period	03/07/2023 → 05/07/2023

Keywords

quadratic knapsack problem
quadratic unconstrained binary optimisation problem
quantum computing
simulated annealing

Access to Document

10.1007/978-3-031-36030-5_8

Translating Constraints into QUBOs for the Quadratic Knapsack ProblemFinal publisher's version, 65 MBLicence: Taverne

Handle.net

Persistent link

Cite this

Bontekoe, T., Phillipson, F., & Schoot, W. V. D. (2023). Translating Constraints into QUBOs for the Quadratic Knapsack Problem. In J. Mikyška, C. de Mulatier, M. Paszynski, V. Krzhizhanovskaya, J. Dongarra, & P. Sloot (Eds.), Computational Science – ICCS 2023: 23rd International Conference Prague, Czech Republic, July 3–5, 2023 Proceedings, Part V (pp. 90-107). (Lecture Notes in Computer Science; Vol. 14077). Springer. https://doi.org/10.1007/978-3-031-36030-5_8

Bontekoe, Tariq ; Phillipson, Frank ; Schoot, Ward van der. / Translating Constraints into QUBOs for the Quadratic Knapsack Problem. Computational Science – ICCS 2023: 23rd International Conference Prague, Czech Republic, July 3–5, 2023 Proceedings, Part V. editor / Jiří Mikyška ; Clélia de Mulatier ; Maciej Paszynski ; Valeria Krzhizhanovskaya ; Jack Dongarra ; Peter Sloot. Cham : Springer, 2023. pp. 90-107 (Lecture Notes in Computer Science).

@inproceedings{101af018f75147d0bd1698a0897251aa,

title = "Translating Constraints into QUBOs for the Quadratic Knapsack Problem",

abstract = "One of the first fields where quantum computing will likely show its use is optimisation. Many optimisation problems naturally arise in a quadratic manner, such as the quadratic knapsack problem. The current state of quantum computers requires these problems to be formulated as a quadratic unconstrained binary optimisation problem, or QUBO. Constrained quadratic binary optimisation can be translated into QUBOs by translating the constraint. However, this translation can be made in several ways, which can have a large impact on the performance when solving the QUBO. We show six different formulations for the quadratic knapsack problem and compare their performance using simulated annealing. The best performance is obtained by a formulation that uses no auxiliary variables for modelling the inequality constraint.",

keywords = "quadratic knapsack problem, quadratic unconstrained binary optimisation problem, quantum computing, simulated annealing",

author = "Tariq Bontekoe and Frank Phillipson and Schoot, \{Ward van der\}",

year = "2023",

month = jun,

day = "26",

doi = "10.1007/978-3-031-36030-5\_8",

language = "English",

isbn = "9783031360299",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "90--107",

editor = "Ji{\v r}{\'i} Miky{\v s}ka and \{de Mulatier\}, Cl{\'e}lia and Maciej Paszynski and Valeria Krzhizhanovskaya and Jack Dongarra and Peter Sloot",

booktitle = "Computational Science – ICCS 2023",

note = "Computational<br/>Science – ICCS 2023 : 23rd International Conference ; Conference date: 03-07-2023 Through 05-07-2023",

}

Bontekoe, T, Phillipson, F & Schoot, WVD 2023, Translating Constraints into QUBOs for the Quadratic Knapsack Problem. in J Mikyška, C de Mulatier, M Paszynski, V Krzhizhanovskaya, J Dongarra & P Sloot (eds), Computational Science – ICCS 2023: 23rd International Conference Prague, Czech Republic, July 3–5, 2023 Proceedings, Part V. Lecture Notes in Computer Science, vol. 14077, Springer, Cham, pp. 90-107, Computational
Science – ICCS 2023, Prague, Czech Republic, 03/07/2023. https://doi.org/10.1007/978-3-031-36030-5_8

Translating Constraints into QUBOs for the Quadratic Knapsack Problem. / Bontekoe, Tariq; Phillipson, Frank; Schoot, Ward van der.
Computational Science – ICCS 2023: 23rd International Conference Prague, Czech Republic, July 3–5, 2023 Proceedings, Part V. ed. / Jiří Mikyška; Clélia de Mulatier; Maciej Paszynski; Valeria Krzhizhanovskaya; Jack Dongarra; Peter Sloot. Cham: Springer, 2023. p. 90-107 (Lecture Notes in Computer Science; Vol. 14077).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Translating Constraints into QUBOs for the Quadratic Knapsack Problem

AU - Bontekoe, Tariq

AU - Phillipson, Frank

AU - Schoot, Ward van der

PY - 2023/6/26

Y1 - 2023/6/26

N2 - One of the first fields where quantum computing will likely show its use is optimisation. Many optimisation problems naturally arise in a quadratic manner, such as the quadratic knapsack problem. The current state of quantum computers requires these problems to be formulated as a quadratic unconstrained binary optimisation problem, or QUBO. Constrained quadratic binary optimisation can be translated into QUBOs by translating the constraint. However, this translation can be made in several ways, which can have a large impact on the performance when solving the QUBO. We show six different formulations for the quadratic knapsack problem and compare their performance using simulated annealing. The best performance is obtained by a formulation that uses no auxiliary variables for modelling the inequality constraint.

AB - One of the first fields where quantum computing will likely show its use is optimisation. Many optimisation problems naturally arise in a quadratic manner, such as the quadratic knapsack problem. The current state of quantum computers requires these problems to be formulated as a quadratic unconstrained binary optimisation problem, or QUBO. Constrained quadratic binary optimisation can be translated into QUBOs by translating the constraint. However, this translation can be made in several ways, which can have a large impact on the performance when solving the QUBO. We show six different formulations for the quadratic knapsack problem and compare their performance using simulated annealing. The best performance is obtained by a formulation that uses no auxiliary variables for modelling the inequality constraint.

KW - quadratic knapsack problem

KW - quadratic unconstrained binary optimisation problem

KW - quantum computing

KW - simulated annealing

U2 - 10.1007/978-3-031-36030-5_8

DO - 10.1007/978-3-031-36030-5_8

M3 - Conference contribution

SN - 9783031360299

SN - 9783031360305

T3 - Lecture Notes in Computer Science

SP - 90

EP - 107

BT - Computational Science – ICCS 2023

A2 - Mikyška, Jiří

A2 - de Mulatier, Clélia

A2 - Paszynski, Maciej

A2 - Krzhizhanovskaya, Valeria

A2 - Dongarra, Jack

A2 - Sloot, Peter

PB - Springer

CY - Cham

T2 - Computational<br/>Science – ICCS 2023

Y2 - 3 July 2023 through 5 July 2023

ER -

Bontekoe T, Phillipson F, Schoot WVD. Translating Constraints into QUBOs for the Quadratic Knapsack Problem. In Mikyška J, de Mulatier C, Paszynski M, Krzhizhanovskaya V, Dongarra J, Sloot P, editors, Computational Science – ICCS 2023: 23rd International Conference Prague, Czech Republic, July 3–5, 2023 Proceedings, Part V. Cham: Springer. 2023. p. 90-107. (Lecture Notes in Computer Science). doi: 10.1007/978-3-031-36030-5_8