Lower bounds for a bin packing problem with linear usage cost
- Autor(en)
- Roland Braune
- Abstrakt
In this paper, we address a one-dimensional bin packing problem with bin-specific usage cost. The cost coefficients have a direct linear relationship to the bin index, favoring packings with higher loads in “earlier” bins. We show how lower bounding schemes known from standard bin packing can be adapted to fit this objective function and conduct a worst-case performance analysis. The contribution also covers a conceptually new lower bound for the problem at hand. Computational experience based on randomly generated instances and benchmark libraries provides strong evidence for high quality bounds achievable with low computational effort. This observation is further underpinned by a successful embedding of the lower bounds into a branch-and-bound approach as a computational framework. Clear advantages over a state-of-the-art mixed-integer programming formulation can be obtained for particular problem settings.
- Organisation(en)
- Institut für Business Decisions and Analytics
- Journal
- European Journal of Operational Research
- Band
- 274
- Seiten
- 49-64
- Anzahl der Seiten
- 16
- ISSN
- 0377-2217
- DOI
- https://doi.org/10.1016/j.ejor.2018.10.004
- Publikationsdatum
- 10-2018
- Peer-reviewed
- Ja
- ÖFOS 2012
- 101016 Optimierung, 101015 Operations Research
- Schlagwörter
- ASJC Scopus Sachgebiete
- Information Systems and Management, Computer Science(all), Modelling and Simulation, Management Science and Operations Research
- Link zum Portal
- https://ucris.univie.ac.at/portal/de/publications/lower-bounds-for-a-bin-packing-problem-with-linear-usage-cost(3a4415d5-029d-4116-9fad-8ae37cea11da).html