Lower bounds and algorithms for the minimum cardinality bin covering problem

Rico Walter and Alexander Lawrinenko

European Journal of Operational Research, 2017, vol. 256, issue 2, 392-403

Abstract: This paper introduces the minimum cardinality bin covering problem where we are given m identical bins with capacity C and n indivisible items with integer weights wj(j=1,…,n). The objective is to minimize the number of items packed into the m bins so that the total weight of each bin is at least equal to C. We discuss reduction criteria, derive several lower bound arguments and propose construction heuristics as well as a powerful subset sum-based improvement algorithm that is even optimal when m=2. Moreover, we present a tailored branch-and-bound method which is able to solve instances with up to 20 bins and several hundreds of items within a reasonable amount of time. In a comprehensive computational study on a wide range of randomly generated instances, our algorithmic approach proved to be much more effective than a commercial solver.

Keywords: Bin covering; Minimum cardinality; Lower bounds; Heuristics; Branch-and-bound (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716305288
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:256:y:2017:i:2:p:392-403

DOI: 10.1016/j.ejor.2016.06.068

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 ().