VPSolver is a multiple-choice vector packing solver based on an arc-flow formulation with graph compression [Thesis] [Poster] [Paper] [VPSolver 3 Report] [BibTeX]. VPSolver generates very strong models (equivalent to Gilmore and Gomory’s) that can be solved using general-purpose mixed-integer programming solvers such as Gurobi and GLPK.
Awards: this open-source project won the 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.
The p-dimensional vector packing problem, also called general assignment problem, is a generalization of bin packing with multiple constraints. In this problem, we are required to pack n items of m different types, represented by p-dimensional vectors, into as few bins as possible. In practice, this problem models, for example, static resource allocation problems where the minimum number of servers with known capacities is used to satisfy a set of services with known demands. The multiple-choice vector bin packing problem is a variant of the vector packing problem in which bins have several types (i.e., sizes and costs) and items have several incarnations (i.e., will take one of several possible sizes).
By means of reductions to vector packing, VPSolver can be used to solve several problems such as:
By means of reductions to multiple-choice vector packing, VPSolver can be used to solve several problems such as:
VPSolver includes a python interface that allows modeling other problems easily. Using the python interface, VPSolver can be used to solve problems such as:
Note: Suggestions of other cutting & packing problems (including industrial applications) are welcome! [Contact]
MIP solver: Gurobi, CPLEX, GLPK, COIN-OR, SCIP, lp_solve, …
UNIX-like operating system or a UNIX-like environment such as Cygwin
g++ >= 4.8;
make >= 3.0;
bash >= 3.0
It has been successfully compiled and run on the following platforms:
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.
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. [PDF]
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. [PDF]
Brandão, F. and Pedroso, J. P. (2013). Bin Packing and Related Problems: General Arc-flow Formulation with Graph Compression.
Technical Report DCC-2013-08, Faculdade de Ciências da Universidade do Porto, Portugal. arXiv:1310.6887. [PDF]
Brandão, F. and Pedroso, J. P. (2013). Multiple-choice Vector Bin Packing: Arc-flow Formulation with Graph Compression.
Technical Report DCC-2013-13, Faculdade de Ciências da Universidade do Porto, Universidade do Porto, Portugal. arXiv:1312.3836. [PDF]
Brandão, F. and Pedroso, J. P. (2013). Cutting Stock with Binary Patterns: Arc-flow Formulation with Graph Compression.
Technical Report DCC-2013-09, Faculdade de Ciências da Universidade do Porto, Universidade do Porto, Portugal. arXiv:1502.02899. [PDF]
Brandão, F. (2012). Bin Packing and Related Problems: Pattern-Based Approaches.
Master’s thesis, Faculdade de Ciências da Universidade do Porto, Portugal. [PDF]