QAL-BP: an augmented Lagrangian quantum approach for bin packing.

Journal

Scientific reports

ISSN: 2045-2322

Titre abrégé: Sci Rep

Pays: England

ID NLM: 101563288

Informations de publication

Date de publication:
01 Mar 2024

Historique:

received: 27 09 2023

accepted: 21 12 2023

medline: 2 3 2024

pubmed: 2 3 2024

entrez: 1 3 2024

Statut: epublish

Résumé

The bin packing is a well-known NP-Hard problem in the domain of artificial intelligence, posing significant challenges in finding efficient solutions. Conversely, recent advancements in quantum technologies have shown promising potential for achieving substantial computational speedup, particularly in certain problem classes, such as combinatorial optimization. In this study, we introduce QAL-BP, a novel Quadratic Unconstrained Binary Optimization (QUBO) formulation designed specifically for bin packing and suitable for quantum computation. QAL-BP utilizes the Augmented Lagrangian method to incorporate the bin packing constraints into the objective function while also facilitating an analytical estimation of heuristic, but empirically robust, penalty multipliers. This approach leads to a more versatile and generalizable model that eliminates the need for empirically calculating instance-dependent Lagrangian coefficients, a requirement commonly encountered in alternative QUBO formulations for similar problems. To assess the effectiveness of our proposed approach, we conduct experiments on a set of bin packing instances using a real Quantum Annealing device. Additionally, we compare the results with those obtained from two different classical solvers, namely simulated annealing and Gurobi. The experimental findings not only confirm the correctness of the proposed formulation, but also demonstrate the potential of quantum computation in effectively solving the bin packing problem, particularly as more reliable quantum technology becomes available.

Identifiants

DOI: 10.1038/s41598-023-50540-3 PMID: 38429296

pubmed: 38429296

doi: 10.1038/s41598-023-50540-3

pii: 10.1038/s41598-023-50540-3

doi:

Types de publication

Journal Article

Langues

eng

Sous-ensembles de citation

Pagination

5142

Subventions

Organisme : Bundesministerium für Bildung und Forschung

ID : 13N15586

Organisme : Horizon 2020 Framework Programme,European Union

ID : 952215

Informations de copyright

Références

Garey, M. R. & Johnson, D. S. “Strong’’ np-completeness results: Motivation, examples, and implications. J. ACM 25, 499–508. https://doi.org/10.1145/322077.322090 (1978).

doi: 10.1145/322077.322090

Delorme, M., Iori, M. & Martello, S. Bin packing and cutting stock problems: Mathematical models and exact algorithms. Eur. J. Oper. Res. 255, 1–20. https://doi.org/10.1016/j.ejor.2016.04.030 (2016).

doi: 10.1016/j.ejor.2016.04.030

Venkatesh, S. M., Macaluso, A. & Klusch, M. Gcs-q: Quantum graph coalition structure generation, in International Conference on Computational Science, 138–152 (Springer, 2023).

Venkatesh, S. M., Macaluso, A. & Klusch, M. Bilp-q: Quantum coalition structure generation, in Proceedings of the 19th ACM International Conference on Computing Frontiers, 189–192 (2022).

Venkatesh, S. M., Macaluso, A. & Klusch, M. Quacs: Variational quantum algorithm for coalition structure generation in induced subgraph games. Preprint at arXiv:2304.07218 (2023).

Macaluso, A., Klusch, M., Lodi, S. & Sartori, C. MAQA: A quantum framework for supervised learning. Quantum Inf. Process. 22, 159 (2023).

doi: 10.1007/s11128-023-03901-w

Macaluso, A., Orazi, F., Klusch, M., Lodi, S. & Sartori, C. A variational algorithm for quantum single layer perceptron, in International Conference on Machine Learning, Optimization, and Data Science, 341–356 (Springer, 2022).

Farhi, E., Goldstone, J. & Gutmann, S. A quantum approximate optimization algorithm. Preprint at arXiv:1411.4028 (2014).

Hestenes, M. R. Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303–320. https://doi.org/10.1007/BF00927673 (1969).

doi: 10.1007/BF00927673

Martello, S. & Toth, P. Knapsack Problems: Algorithms and Computer Implementations (Wiley, 1990).

Eisemann, K. The trim problem. Manag. Sci. 3, 279–284 (1957).

doi: 10.1287/mnsc.3.3.279

Gilmore, R. & Gomory, R. A linear programming approach to the cutting stock problem I. Oper. Res. https://doi.org/10.1287/opre.9.6.849 (1961).

doi: 10.1287/opre.9.6.849

Kampke, T. Simulated annealing: Use of new tool in bin packing. Ann. Oper. Res. 16, 327–332. https://doi.org/10.1007/BF02283751 (1988).

doi: 10.1007/BF02283751

Loh, K.-H., Golden, B. & Wasil, E. Solving the one-dimensional bin packing problem with a weight annealing heuristic. Comput. Oper. Res. 35, 2283–2291. https://doi.org/10.1016/j.cor.2006.10.021 (2008) (art Special Issue: Includes selected papers presented at the ECCO '04 European Conference on combinatorial Optimization).

doi: 10.1016/j.cor.2006.10.021

Scholl, A., Klein, R. & Jürgens, C. Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Comput. Oper. Res. 24, 627–645 (1997).

doi: 10.1016/S0305-0548(96)00082-2

Vahrenkamp, R. Random search in the one-dimensional cutting stock problem. Eur. J. Oper. Res. 95, 191–200. https://doi.org/10.1016/0377-2217(95)00198-0 (1996).

doi: 10.1016/0377-2217(95)00198-0

Burke, E., Hyde, M. & Kendall, G. Evolving bin packing heuristics with genetic programming. 860–869. https://doi.org/10.1007/11844297_87 (2006).

Falkenauer, E. A hybrid grouping genetic algorithm for bin packing. J. Heuristics https://doi.org/10.1007/BF00226291 (1996).

doi: 10.1007/BF00226291

Falkenauer, E. & Delchambre, A. A genetic algorithm for bin packing and line balancing, in Proceedings 1992 IEEE International Conference on Robotics and Automation, vol. 2, 1186–1192. https://doi.org/10.1109/ROBOT.1992.220088 (1992).

Quiroz, M. et al. A grouping genetic algorithm with controlled gene transmission for the bin packing problem. Comput. Oper. Res. 55, 52–64. https://doi.org/10.1016/j.cor.2014.10.010 (2014).

doi: 10.1016/j.cor.2014.10.010

Sim, K. & Hart, E. Generating single and multiple cooperative heuristics for the one dimensional bin packing problem using a single node genetic programming island model. https://doi.org/10.1145/2463372.2463555 (2013).

Bai, R., Blazewicz, J., Burke, E., Kendall, G. & Mccollum, B. B. A simulated annealing hyper-heuristic methodology for flexible decision support. 4OR https://doi.org/10.1007/s10288-011-0182-8 (2012).

doi: 10.1007/s10288-011-0182-8

Lopez-Camacho, E., Terashima-Marin, H. & Ross, P. A hyper-heuristic for solving one and two-dimensional bin packing problems, in Proceedings of the 13th Annual Conference Companion on Genetic and Evolutionary Computation (2011).

Sosa, A., Terashima-Marín, H., Ortiz-Bayliss, J. C. & Conant-Pablos, S. Grammar-based selection hyper-heuristics for solving irregular bin packing problems. 111–112. https://doi.org/10.1145/2908961.2908970 (2016).

Sim, K., Hart, E. & Paechter, B. A hyper-heuristic classifier for one dimensional bin packing problems: Improving classification accuracy by attribute evolution. In Parallel Problem Solving from Nature - PPSN XII (ed Coello, C. A. C. et al.) 348–357 (Springer, Berlin Heidelberg, 2012).

Gomez-Meneses, P. & Randall, M. A hybrid extremal optimisation approach for the bin packing problem. vol. 5865. https://doi.org/10.1007/978-3-642-10427-5_24 (2009).

Eilon, S. & Christofides, N. The loading problem. Manag. Sci. 17, 259–268. https://doi.org/10.1287/mnsc.17.5.259 (1971).

doi: 10.1287/mnsc.17.5.259

Gupta, J. N. D. & Ho, J. C. A new heuristic algorithm for the one-dimensional bin-packing problem. Product. Plan. Control 10, 598–603. https://doi.org/10.1080/095372899232894 (1999).

doi: 10.1080/095372899232894

Lewis, R. A general-purpose hill-climbing method for order independent minimum grouping problems: A case study in graph colouring and bin packing. Comput. Oper. Res. 36, 2295–2310. https://doi.org/10.1016/j.cor.2008.09.004 (2009).

doi: 10.1016/j.cor.2008.09.004

Rao, M. R. On the cutting stock problem. J. Comput. Soc. India (1976).

Dyckhoff, H. A new linear programming approach to the cutting stock problem. Oper. Res. 29, 1092–1104. https://doi.org/10.1287/opre.29.6.1092 (1981).

doi: 10.1287/opre.29.6.1092

Stadtler, H. A comparison of two optimization procedures for 1- and 1 1/2-dimensional cutting stock problems. OR Spektrum 10, 97–111. https://doi.org/10.1007/BF01720208 (1988).

doi: 10.1007/BF01720208

Lodewijks, B. Mapping np-hard and np-complete optimisation problems to quadratic unconstrained binary optimisation problems. https://doi.org/10.48550/ARXIV.1911.08043 (2019).

Montanez-Barrera, A., Willsch, D., Maldonado-Romo, A. & Michielsen, K. Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms. https://doi.org/10.48550/ARXIV.2211.13914 (2022).

Garcia-de Andoin, M., Oregi, I., Villar-Rodriguez, E., Osaba, E. & Sanz, M. Comparative benchmark of a quantum algorithm for the bin packing problem. https://doi.org/10.48550/ARXIV.2207.07460 (2022).

Kuramata, M., Katsuki, R. & Nakata, K. Larger sparse quadratic assignment problem optimization using quantum annealing and a bit-flip heuristic algorithm, in 2021 IEEE 8th International Conference on Industrial Engineering and Applications (ICIEA). https://doi.org/10.1109/iciea52957.2021.9436749 (IEEE, 2021).

Bertsekas, D. P. Constrained Optimization and Lagrange Multiplier Methods (Academic Press, New York, 1982).

Lucas, A. Ising formulations of many NP problems. Front. Phys. https://doi.org/10.3389/fphy.2014.00005 (2014).

doi: 10.3389/fphy.2014.00005

Martello, S. & Toth, P. Lower bounds and reduction procedures for the bin packing problem. Discrete Appl. Math. 28, 59–70. https://doi.org/10.1016/0166-218X(90)90094-S (1990).

doi: 10.1016/0166-218X(90)90094-S

D-wave documentation. https://docs.dwavesys.com/docs/latest/c_qpu_timing.html .

Gurobi optimization. Website. Accessed: 22/07/2023.

Programming the D-wave QPU: Setting the chain strength. Website. Accessed: 10/11/2023.

Carugno, C., Ferrari Dacrema, M. & Cremonesi, P. Evaluating the job shop scheduling problem on a d-wave quantum annealer. Sci. Rep. 12, 6539. https://doi.org/10.1038/s41598-022-10169-0 (2022).

doi: 10.1038/s41598-022-10169-0 pubmed: 35449435 pmcid: 9023457

Morrison, D. R., Jacobson, S. H., Sauppe, J. J. & Sewell, E. C. Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optim. 19, 79–102. https://doi.org/10.1016/j.disopt.2016.01.005 (2016).

doi: 10.1016/j.disopt.2016.01.005

Venkatesh, S. M., Macaluso, A., Nuske, M., Klusch, M. & Dengel, A. Q-seg: Quantum annealing-based unsupervised image segmentation. Preprint at arXiv:2311.12912 (2023).