Lower bounds and algorithms for the minimum cardinality bin covering problem
详细信息 查看全文
- 作者：Rico Walter ; rico.walter@uni-jena.de" class="auth_mail" title="E-mail the corresponding author ; Alexander Lawrinenko alexander.lawrinenko@uni-jena.de" class="auth_mail" title="E-mail the corresponding author
- 关键词：Bin covering ; Minimum cardinality ; Lower bounds ; Heuristics ; Branch-and-bound
- 刊名：European Journal of Operational Research
- 出版年：2017
- 出版时间：16 January 2017
- 年：2017
- 卷：256
- 期：2
- 页码：392-403
- 全文大小：545 K
文摘
- •
We study the dual version of the minimum cardinality bin packing problem.
- •
We develop strong lower bounds and analyze their worst-case performances.
- •
We suggest constructive heuristics and a subset sum-based improvement heuristic.
- •
We propose a branch-and-bound algorithm to determine an optimal solution.
- •
Our algorithms proved to be effective on a wide range of randomly generated instances.