A Heuristic Column Generation Approach for the Stochastic Bin Packing Problem

John Martinovic (), Nico Strasdat (), Jean-François Côté () and Vinícius Loti Lima ()
Additional contact information
John Martinovic: Technische Universität Dresden
Nico Strasdat: Technische Universität Dresden
Jean-François Côté: Université Laval
Vinícius Loti Lima: Amazon.com

Chapter Chapter 16 in Operations Research Proceedings 2022, 2023, pp 131-138 from Springer

Abstract: Abstract The stochastic bin packing problem (SBPP) is an extension of the well-studied classical bin packing problem with respect to imperfect information on the item sizes. From a practical point of view, the latter are typically represented by (stochastically independent) normally distributed random variables with given means and variances. In this scenario, the SBPP requires to determine the minimum number of bins needed to pack all the items, with the risk of overloading a bin not exceeding a certain tolerable limit. Such computations are of high relevance in server consolidation applications, where decisions have to be made before witnessing the true item characteristics. The resulting integer optimization problems are generally nonlinear and therefore difficult to solve. For this reason, previous approaches from the literature can only handle small instance sizes exactly. In this work, we present a column generation algorithm using heuristic information and near-optimal solutions of the associated (challenging) pricing problems. Based on numerical tests, we show that in most cases this heuristic approach already leads to an optimal solution, so that much larger instance sizes can now be dealt with in reasonable time.

Keywords: Cutting and packing; Stochastic bin packing problem; Normal distribution; Column generation; Heuristics (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:lnopch:978-3-031-24907-5_16

Ordering information: This item can be ordered from
http://www.springer.com/9783031249075

DOI: 10.1007/978-3-031-24907-5_16

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().