Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem

Mikel Garcia De Andoin; Izaskun Oregi; Esther Villar-Rodriguez; Eneko Osaba; Mikel Sanz

doi:10.1109/SSCI51031.2022.10022156

Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem

Mikel Garcia De Andoin^*, Izaskun Oregi, Esther Villar-Rodriguez, Eneko Osaba, Mikel Sanz^*

^*Corresponding author for this work

Quantum

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

4 Citations (Scopus)

Abstract

The Bin Packing Problem (BPP) stands out as a paradigmatic combinatorial optimization problem in logistics. Quantum and hybrid quantum-classical algorithms are expected to show an advantage over their classical counterparts in obtaining approximate solutions for optimization problems. We have recently proposed a hybrid approach to the one dimensional BPP in which a quantum annealing subroutine is employed to sample feasible solutions for single containers. From this reduced search space, a classical optimization subroutine can find the solution to the problem. With the aim of going a step further in the evaluation of our subroutine, in this paper we compare the performance of our procedure with other classical approaches. Concretely we test a random sampling and a random-walk-based heuristic. Employing a benchmark comprising 18 instances, we show that the quantum approach lacks the stagnation behaviour that slows down the classical algorithms. Based on this, we conclude that the quantum strategy can be employed jointly with the random walk to obtain a full sample of feasible solutions in fewer iterations. This work improves our intuition about the benefits of employing the scarce quantum resources to improve the results of a diminishingly efficient classical strategy.

Original language	English
Title of host publication	Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022
Editors	Hisao Ishibuchi, Chee-Keong Kwoh, Ah-Hwee Tan, Dipti Srinivasan, Chunyan Miao, Anupam Trivedi, Keeley Crockett
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	930-937
Number of pages	8
ISBN (Electronic)	9781665487689
DOIs	https://doi.org/10.1109/SSCI51031.2022.10022156
Publication status	Published - 2022
Event	2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022 - Singapore, Singapore Duration: 4 Dec 2022 → 7 Dec 2022

Publication series

Name	Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022

Conference

Conference	2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022
Country/Territory	Singapore
City	Singapore
Period	4/12/22 → 7/12/22

Keywords

Bin Packing Problem
Combinatorial optimization
Quantum Annealing
Quantum computation

Access to Document

10.1109/SSCI51031.2022.10022156

Cite this

De Andoin, M. G., Oregi, I., Villar-Rodriguez, E., Osaba, E., & Sanz, M. (2022). Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem. In H. Ishibuchi, C.-K. Kwoh, A.-H. Tan, D. Srinivasan, C. Miao, A. Trivedi, & K. Crockett (Eds.), Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022 (pp. 930-937). (Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SSCI51031.2022.10022156

De Andoin, Mikel Garcia ; Oregi, Izaskun ; Villar-Rodriguez, Esther et al. / Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem. Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022. editor / Hisao Ishibuchi ; Chee-Keong Kwoh ; Ah-Hwee Tan ; Dipti Srinivasan ; Chunyan Miao ; Anupam Trivedi ; Keeley Crockett. Institute of Electrical and Electronics Engineers Inc., 2022. pp. 930-937 (Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022).

@inproceedings{76b2fee7bb344fcebcf81293147b0025,

title = "Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem",

abstract = "The Bin Packing Problem (BPP) stands out as a paradigmatic combinatorial optimization problem in logistics. Quantum and hybrid quantum-classical algorithms are expected to show an advantage over their classical counterparts in obtaining approximate solutions for optimization problems. We have recently proposed a hybrid approach to the one dimensional BPP in which a quantum annealing subroutine is employed to sample feasible solutions for single containers. From this reduced search space, a classical optimization subroutine can find the solution to the problem. With the aim of going a step further in the evaluation of our subroutine, in this paper we compare the performance of our procedure with other classical approaches. Concretely we test a random sampling and a random-walk-based heuristic. Employing a benchmark comprising 18 instances, we show that the quantum approach lacks the stagnation behaviour that slows down the classical algorithms. Based on this, we conclude that the quantum strategy can be employed jointly with the random walk to obtain a full sample of feasible solutions in fewer iterations. This work improves our intuition about the benefits of employing the scarce quantum resources to improve the results of a diminishingly efficient classical strategy.",

keywords = "Bin Packing Problem, Combinatorial optimization, Quantum Annealing, Quantum computation",

author = "{De Andoin}, {Mikel Garcia} and Izaskun Oregi and Esther Villar-Rodriguez and Eneko Osaba and Mikel Sanz",

note = "Publisher Copyright: {\textcopyright} 2022 IEEE.; 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022 ; Conference date: 04-12-2022 Through 07-12-2022",

year = "2022",

doi = "10.1109/SSCI51031.2022.10022156",

language = "English",

series = "Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "930--937",

editor = "Hisao Ishibuchi and Chee-Keong Kwoh and Ah-Hwee Tan and Dipti Srinivasan and Chunyan Miao and Anupam Trivedi and Keeley Crockett",

booktitle = "Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022",

address = "United States",

}

De Andoin, MG, Oregi, I , Villar-Rodriguez, E , Osaba, E & Sanz, M 2022, Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem. in H Ishibuchi, C-K Kwoh, A-H Tan, D Srinivasan, C Miao, A Trivedi & K Crockett (eds), Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022. Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022, Institute of Electrical and Electronics Engineers Inc., pp. 930-937, 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022, Singapore, Singapore, 4/12/22. https://doi.org/10.1109/SSCI51031.2022.10022156

Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem. / De Andoin, Mikel Garcia; Oregi, Izaskun ; Villar-Rodriguez, Esther et al.
Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022. ed. / Hisao Ishibuchi; Chee-Keong Kwoh; Ah-Hwee Tan; Dipti Srinivasan; Chunyan Miao; Anupam Trivedi; Keeley Crockett. Institute of Electrical and Electronics Engineers Inc., 2022. p. 930-937 (Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022).

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

TY - GEN

T1 - Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem

AU - De Andoin, Mikel Garcia

AU - Oregi, Izaskun

AU - Villar-Rodriguez, Esther

AU - Osaba, Eneko

AU - Sanz, Mikel

PY - 2022

Y1 - 2022

N2 - The Bin Packing Problem (BPP) stands out as a paradigmatic combinatorial optimization problem in logistics. Quantum and hybrid quantum-classical algorithms are expected to show an advantage over their classical counterparts in obtaining approximate solutions for optimization problems. We have recently proposed a hybrid approach to the one dimensional BPP in which a quantum annealing subroutine is employed to sample feasible solutions for single containers. From this reduced search space, a classical optimization subroutine can find the solution to the problem. With the aim of going a step further in the evaluation of our subroutine, in this paper we compare the performance of our procedure with other classical approaches. Concretely we test a random sampling and a random-walk-based heuristic. Employing a benchmark comprising 18 instances, we show that the quantum approach lacks the stagnation behaviour that slows down the classical algorithms. Based on this, we conclude that the quantum strategy can be employed jointly with the random walk to obtain a full sample of feasible solutions in fewer iterations. This work improves our intuition about the benefits of employing the scarce quantum resources to improve the results of a diminishingly efficient classical strategy.

AB - The Bin Packing Problem (BPP) stands out as a paradigmatic combinatorial optimization problem in logistics. Quantum and hybrid quantum-classical algorithms are expected to show an advantage over their classical counterparts in obtaining approximate solutions for optimization problems. We have recently proposed a hybrid approach to the one dimensional BPP in which a quantum annealing subroutine is employed to sample feasible solutions for single containers. From this reduced search space, a classical optimization subroutine can find the solution to the problem. With the aim of going a step further in the evaluation of our subroutine, in this paper we compare the performance of our procedure with other classical approaches. Concretely we test a random sampling and a random-walk-based heuristic. Employing a benchmark comprising 18 instances, we show that the quantum approach lacks the stagnation behaviour that slows down the classical algorithms. Based on this, we conclude that the quantum strategy can be employed jointly with the random walk to obtain a full sample of feasible solutions in fewer iterations. This work improves our intuition about the benefits of employing the scarce quantum resources to improve the results of a diminishingly efficient classical strategy.

KW - Bin Packing Problem

KW - Combinatorial optimization

KW - Quantum Annealing

KW - Quantum computation

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

U2 - 10.1109/SSCI51031.2022.10022156

DO - 10.1109/SSCI51031.2022.10022156

M3 - Conference contribution

AN - SCOPUS:85147797521

T3 - Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022

SP - 930

EP - 937

BT - Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022

A2 - Ishibuchi, Hisao

A2 - Kwoh, Chee-Keong

A2 - Tan, Ah-Hwee

A2 - Srinivasan, Dipti

A2 - Miao, Chunyan

A2 - Trivedi, Anupam

A2 - Crockett, Keeley

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022

Y2 - 4 December 2022 through 7 December 2022

ER -

De Andoin MG, Oregi I , Villar-Rodriguez E , Osaba E, Sanz M. Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem. In Ishibuchi H, Kwoh CK, Tan AH, Srinivasan D, Miao C, Trivedi A, Crockett K, editors, Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022. Institute of Electrical and Electronics Engineers Inc. 2022. p. 930-937. (Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence, SSCI 2022). doi: 10.1109/SSCI51031.2022.10022156

Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this