Algorithms for the bin packing problem with scenarios

Yulle G. F. Borges, Vinícius L. Lima, Flávio K. Miyazawa, Lehilton L. C. Pedrosa, Thiago A. Queiroz and Rafael C. S. Schouery ()
Additional contact information
Yulle G. F. Borges: University of Campinas
Vinícius L. Lima: University of Campinas
Flávio K. Miyazawa: University of Campinas
Lehilton L. C. Pedrosa: University of Campinas
Thiago A. Queiroz: Federal University of Catalão
Rafael C. S. Schouery: University of Campinas

Journal of Combinatorial Optimization, 2024, vol. 48, issue 4, No 7, 28 pages

Abstract: Abstract This paper presents theoretical and practical results for the bin packing problem with scenarios, a generalization of the classical bin packing problem which considers the presence of uncertain scenarios, of which only one is realized. For this problem, we propose approximation algorithms whose ratios are bounded by the square root of the number of scenarios times the approximation ratio for an algorithm for the vector bin packing problem. We also show how an asymptotic polynomial-time approximation scheme is derived when the number of scenarios is constant, that is, not a part of the input. As a practical study of the problem, we present a branch-and-price algorithm to solve an exponential set-cover model and a variable neighborhood search heuristic. Experiments show the competence of the branch-and-price in obtaining optimal solutions for about 59% of the instances considered, while the combined heuristic and branch-and-price optimally solved 62% of the instances considered.

Keywords: Bin packing problem; Scenarios; Approximation algorithm; Variable neighborhood search; Branch-and-price algorithm (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01221-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:48:y:2024:i:4:d:10.1007_s10878-024-01221-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01221-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().