- Try it online!
- Computational results
- Available at http://vpsolver.fdabrandao.pt
- GitHub: https://github.com/fdabrandao/vpsolver
- The underlying model and algorithms were proposed in: “Bin packing and related problems: General arc-flow formulation with graph compression”.
- By means of reductions to vector packing, it can be used to solve several cutting and packing problems such as: bin Packing, cutting stock, bin packing with conflicts, cardinality constrained bin packing, cutting stock with binary patterns, and cutting stock with binary patterns and forbidden pairs.
- Awards: Orbel Wolsey Award 2016
- Industries using this software: the underlying model and algorithms are currently being used by a large multinational company in the the labeling & packaging industry.
General Arc-flow Formulation with Graph Compression
Brandão, F. and Pedroso, J. P. (2016). Bin packing and related problems: General arc-flow formulation with graph compression.
Computers & Operations Research, 69:56 – 67. doi: http://dx.doi.org/10.1016/j.cor.2015.11.009.
Accepted Manuscript (PDF) (the final publication is available at http://dx.doi.org/10.1016/j.cor.2015.11.009)
Technical Report (PDF) (also available at arXiv:1310.6887)
Poster (PDF)
Abstract
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.
BibTeX
@article{GeneralArcFlowPaper,
title = "Bin packing and related problems: General arc-flow formulation with graph compression",
journal = "Computers \& Operations Research",
volume = "69",
number = "",
pages = "56 - 67",
year = "2016",
note = "",
issn = "0305-0548",
doi = "http://dx.doi.org/10.1016/j.cor.2015.11.009",
url = "http://www.sciencedirect.com/science/article/pii/S0305054815002762",
author = "Brand\~ao, Filipe and Pedroso, J. P.",
keywords = "Bin packing",
keywords = "Cutting stock",
keywords = "Vector packing",
keywords = "Arc-flow formulation"
}
@TechReport{GeneralArcFlowReport,
author = {Brand\~ao, Filipe and Pedroso, J. P.},
title = {{Bin Packing and Related Problems: General Arc-flow Formulation with Graph Compression}},
type = {Technical Report},
number = {DCC-2013-08},
institution = {Faculdade de Ci\^encias da Universidade do Porto},
address = {Portugal},
year = {2013},
}
Results
Arc-flow Formulation (w/ Graph Compression) Results
See also
Cutting & Packing Problems: General Arc-flow Formulation with Graph Compression
Multiple-choice Vector Bin Packing: Arc-flow Formulation with Graph Compression
Cutting Stock with Binary Patterns: Arc-flow Formulation with Graph Compression