Lower bounds for a bin packing problem with linear usage cost

Roland Braune

European Journal of Operational Research, 2019, vol. 274, issue 1, 49-64

Abstract: 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.

Keywords: Packing; Combinatorial optimization; Lower bounds; Performance ratio; Branch and bound (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718308555
Full text for ScienceDirect subscribers only

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:eee:ejores:v:274:y:2019:i:1:p:49-64

DOI: 10.1016/j.ejor.2018.10.004

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().