Brandão, F. (2017). Cutting & Packing Problems: General Arc-flow Formulation with Graph Compression. PhD thesis, Faculdade de Ciências da Universidade do Porto, Portugal.
The research derived from this thesis resulted in the following papers:
- Bin Packing and Related 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
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 cutting and packing problems through reductions to multiple-choice vector packing. In this thesis, we deal with vector packing, bin packing, cutting stock, cardinality constrained bin packing, cutting stock with cutting knife limitation, bin packing with conflicts, and many other problems.
The set of applications is not limited to reductions to multiple-choice vector packing problems. The proposed method provides a simple way to represent every feasible pattern for any cutting or packing instance in an integer programming model. Therefore, we can use multiple arc-flow models in the same model in order to model, for instance, multi-stage variants. Given the flexibility of the proposed method, we introduced two new problem variants: the multi-stage vector packing problem and the generalized vector packing problem. Both variants were easily tackled by our method since it takes full advantage of the heuristics and cutting plane generators that come with state-of-the-art MIP solvers. This is particularly important when arc-flow models are used as part of more complex models that may benefit substantially from the cuts generated by MIP solvers.
One of the outcomes of this thesis is an open-source project called VPSolver, which is currently being used not only by other researchers but also in the industry. The arc-flow formulation with graph compression is currently being used by a large multinational company in the labeling & packaging sector in over 60 sites worldwide to solve daily hundreds of cutting stock instances with several industry-specific constraints.
BibTeX
@PhDThesis{PhDThesisBrandaoF,
author = {Brand\~ao, Filipe},
title = {{Cutting \& Packing Problems: General Arc-flow Formulation with Graph Compression}},
school = {Faculdade de Ci\^encias da Universidade do Porto},
address = {Portugal},
year = {2017},
}
Results
Arc-flow Formulation (w/ Graph Compression) Results
See also
Bin Packing and Related 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