Black Box Optimization Using QUBO and the Cross Entropy Method

Jonas Nüßlein; Christoph Roch; Thomas Gabor; Jonas Stein; Claudia Linnhoff-Popien; Sebastian Feld

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

Black Box Optimization Using QUBO and the Cross Entropy Method

Jonas Nüßlein^*, Christoph Roch, Thomas Gabor, Jonas Stein, Claudia Linnhoff-Popien, Sebastian Feld

^*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

Abstract

Black-box optimization (BBO) can be used to optimize functions whose analytic form is unknown. A common approach to realising BBO is to learn a surrogate model which approximates the target black-box function which can then be solved via white-box optimization methods. In this paper, we present our approach BOX-QUBO, where the surrogate model is a QUBO matrix. However, unlike in previous state-of-the-art approaches, this matrix is not trained entirely by regression, but mostly by classification between “good” and “bad” solutions. This better accounts for the low capacity of the QUBO matrix, resulting in significantly better solutions overall. We tested our approach against the state-of-the-art on four domains and in all of them BOX-QUBO showed better results. A second contribution of this paper is the idea to also solve white-box problems, i.e. problems which could be directly formulated as QUBO, by means of black-box optimization in order to reduce the size of the QUBOs to the information-theoretic minimum. Experiments show that this significantly improves the results for MAX-k-SAT.

Original language	English
Title of host publication	Computational Science – ICCS 2023 - 23rd International Conference, Proceedings
Editors	Jiří Mikyška, Clélia de Mulatier, Valeria V. Krzhizhanovskaya, Peter M. A. Sloot, Maciej Paszynski, Jack J. Dongarra
Publisher	Springer
Pages	48-55
Number of pages	8
ISBN (Print)	9783031360299
DOIs	https://doi.org/10.1007/978-3-031-36030-5_4
Publication status	Published - 2023
Event	23rd International Conference on Computational Science, ICCS 2023 - Prague, Czech Republic Duration: 3 Jul 2023 → 5 Jul 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14077 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	23rd International Conference on Computational Science, ICCS 2023
Country/Territory	Czech Republic
City	Prague
Period	3/07/23 → 5/07/23

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

Black-Box
Ising
Quantum Annealing
QUBO
SAT

Access to Document

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

978-3-031-36030-5_4Final published version, 232 KB

Cite this

Nüßlein, J., Roch, C., Gabor, T., Stein, J., Linnhoff-Popien, C., & Feld, S. (2023). Black Box Optimization Using QUBO and the Cross Entropy Method. In J. Mikyška, C. de Mulatier, V. V. Krzhizhanovskaya, P. M. A. Sloot, M. Paszynski, & J. J. Dongarra (Eds.), Computational Science – ICCS 2023 - 23rd International Conference, Proceedings (pp. 48-55). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14077 LNCS). Springer. https://doi.org/10.1007/978-3-031-36030-5_4

Nüßlein, Jonas ; Roch, Christoph ; Gabor, Thomas et al. / Black Box Optimization Using QUBO and the Cross Entropy Method. Computational Science – ICCS 2023 - 23rd International Conference, Proceedings. editor / Jiří Mikyška ; Clélia de Mulatier ; Valeria V. Krzhizhanovskaya ; Peter M. A. Sloot ; Maciej Paszynski ; Jack J. Dongarra. Springer, 2023. pp. 48-55 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{46418c357f0e4c33965c82bc3e5cf89b,

title = "Black Box Optimization Using QUBO and the Cross Entropy Method",

abstract = " Black-box optimization (BBO) can be used to optimize functions whose analytic form is unknown. A common approach to realising BBO is to learn a surrogate model which approximates the target black-box function which can then be solved via white-box optimization methods. In this paper, we present our approach BOX-QUBO, where the surrogate model is a QUBO matrix. However, unlike in previous state-of-the-art approaches, this matrix is not trained entirely by regression, but mostly by classification between “good” and “bad” solutions. This better accounts for the low capacity of the QUBO matrix, resulting in significantly better solutions overall. We tested our approach against the state-of-the-art on four domains and in all of them BOX-QUBO showed better results. A second contribution of this paper is the idea to also solve white-box problems, i.e. problems which could be directly formulated as QUBO, by means of black-box optimization in order to reduce the size of the QUBOs to the information-theoretic minimum. Experiments show that this significantly improves the results for MAX-k-SAT.",

keywords = "Black-Box, Ising, Quantum Annealing, QUBO, SAT",

author = "Jonas N{\"u}{\ss}lein and Christoph Roch and Thomas Gabor and Jonas Stein and Claudia Linnhoff-Popien and Sebastian Feld",

note = "Green Open Access added to TU Delft Institutional Repository {\textquoteleft}You share, we take care!{\textquoteright} – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public. ; 23rd International Conference on Computational Science, ICCS 2023 ; Conference date: 03-07-2023 Through 05-07-2023",

year = "2023",

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

language = "English",

isbn = "9783031360299",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "48--55",

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

booktitle = "Computational Science – ICCS 2023 - 23rd International Conference, Proceedings",

}

Nüßlein, J, Roch, C, Gabor, T, Stein, J, Linnhoff-Popien, C & Feld, S 2023, Black Box Optimization Using QUBO and the Cross Entropy Method. in J Mikyška, C de Mulatier, VV Krzhizhanovskaya, PMA Sloot, M Paszynski & JJ Dongarra (eds), Computational Science – ICCS 2023 - 23rd International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14077 LNCS, Springer, pp. 48-55, 23rd International Conference on Computational Science, ICCS 2023, Prague, Czech Republic, 3/07/23. https://doi.org/10.1007/978-3-031-36030-5_4

Black Box Optimization Using QUBO and the Cross Entropy Method. / Nüßlein, Jonas; Roch, Christoph; Gabor, Thomas et al.
Computational Science – ICCS 2023 - 23rd International Conference, Proceedings. ed. / Jiří Mikyška; Clélia de Mulatier; Valeria V. Krzhizhanovskaya; Peter M. A. Sloot; Maciej Paszynski; Jack J. Dongarra. Springer, 2023. p. 48-55 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14077 LNCS).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Black Box Optimization Using QUBO and the Cross Entropy Method

AU - Nüßlein, Jonas

AU - Roch, Christoph

AU - Gabor, Thomas

AU - Stein, Jonas

AU - Linnhoff-Popien, Claudia

AU - Feld, Sebastian

N1 - Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

PY - 2023

Y1 - 2023

N2 - Black-box optimization (BBO) can be used to optimize functions whose analytic form is unknown. A common approach to realising BBO is to learn a surrogate model which approximates the target black-box function which can then be solved via white-box optimization methods. In this paper, we present our approach BOX-QUBO, where the surrogate model is a QUBO matrix. However, unlike in previous state-of-the-art approaches, this matrix is not trained entirely by regression, but mostly by classification between “good” and “bad” solutions. This better accounts for the low capacity of the QUBO matrix, resulting in significantly better solutions overall. We tested our approach against the state-of-the-art on four domains and in all of them BOX-QUBO showed better results. A second contribution of this paper is the idea to also solve white-box problems, i.e. problems which could be directly formulated as QUBO, by means of black-box optimization in order to reduce the size of the QUBOs to the information-theoretic minimum. Experiments show that this significantly improves the results for MAX-k-SAT.

AB - Black-box optimization (BBO) can be used to optimize functions whose analytic form is unknown. A common approach to realising BBO is to learn a surrogate model which approximates the target black-box function which can then be solved via white-box optimization methods. In this paper, we present our approach BOX-QUBO, where the surrogate model is a QUBO matrix. However, unlike in previous state-of-the-art approaches, this matrix is not trained entirely by regression, but mostly by classification between “good” and “bad” solutions. This better accounts for the low capacity of the QUBO matrix, resulting in significantly better solutions overall. We tested our approach against the state-of-the-art on four domains and in all of them BOX-QUBO showed better results. A second contribution of this paper is the idea to also solve white-box problems, i.e. problems which could be directly formulated as QUBO, by means of black-box optimization in order to reduce the size of the QUBOs to the information-theoretic minimum. Experiments show that this significantly improves the results for MAX-k-SAT.

KW - Black-Box

KW - Ising

KW - Quantum Annealing

KW - QUBO

KW - SAT

UR - http://www.scopus.com/inward/record.url?scp=85200772595&partnerID=8YFLogxK

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

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

M3 - Conference contribution

AN - SCOPUS:85200772595

SN - 9783031360299

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 48

EP - 55

BT - Computational Science – ICCS 2023 - 23rd International Conference, Proceedings

A2 - Mikyška, Jiří

A2 - de Mulatier, Clélia

A2 - Krzhizhanovskaya, Valeria V.

A2 - Sloot, Peter M. A.

A2 - Paszynski, Maciej

A2 - Dongarra, Jack J.

PB - Springer

T2 - 23rd International Conference on Computational Science, ICCS 2023

Y2 - 3 July 2023 through 5 July 2023

ER -

Nüßlein J, Roch C, Gabor T, Stein J, Linnhoff-Popien C, Feld S. Black Box Optimization Using QUBO and the Cross Entropy Method. In Mikyška J, de Mulatier C, Krzhizhanovskaya VV, Sloot PMA, Paszynski M, Dongarra JJ, editors, Computational Science – ICCS 2023 - 23rd International Conference, Proceedings. Springer. 2023. p. 48-55. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-36030-5_4