Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 69, Issue -, Pages 56-67Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2015.11.009
Keywords
Bin packing; Cutting stock; Vector packing; Arc-flow formulation
Categories
Funding
- Fundacao para a Ciancia e Tecnologia (FCT), Portugal [SFRH/BD/91538/2012]
- Fundação para a Ciência e a Tecnologia [SFRH/BD/91538/2012] Funding Source: FCT
Ask authors/readers for more resources
We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems-including multi-constraint variants-by simply representing all the patterns in a very compact graph. Our method includes a graph compression algorithm that usually reduces the size of the underlying graph substantially without weakening the model. Our formulation is equivalent to Gilmore and Gomory's, thus providing a very strong linear relaxation. However, instead of using column-generation in an iterative process, the method constructs a graph, where paths from the source to the target node represent every valid packing pattern. The same method, without any problem-specific parameterization, was used to solve a large variety of instances from several different cutting and packing problems. In this paper, we deal with vector packing, bin packing, cutting stock, cardinality constrained bin packing, cutting stock with cutting knife limitation, bin packing with conflicts, and other problems. We report computational results obtained with many benchmark test datasets, some of them showing a large advantage of this formulation with respect to the traditional ones. (C) 2015 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available