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.

Latest release: VPSolver v3.1.2, released on June 28th, 2016. [Donwload] [GitHub] [Project Wiki]
- This version includes a Web App, a Python API (VBP Example, MVP Example), a modelling toolbox (PyMPL), and supports Gurobi, CPLEX, COIN-OR, GLPK, SCIP, and lp_solve.

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.

Overview

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:

• Bin packing;
• Cutting stock;
• Cardinality constrained bin packing;
• Cutting stock with cutting knife limitation;
• Bin packing with conflicts;
• Cutting stock with binary patterns;
• Cutting stock with binary patterns and forbidden pairs.
• [Computational results on several benchmark test data sets]

By means of reductions to multiple-choice vector packing, VPSolver can be used to solve several problems such as:

• Variants of the problems from the list above that consider multiple bin types;
• Variable-sized bin packing (as an one-dimensional multiple-choice vector bin packing problem).

VPSolver includes a python interface that allows modeling other problems easily. Using the python interface, VPSolver can be used to solve problems such as:

• Many variants that happen in the industry that include cutting and packing problems as subproblems of a larger production planning problem;
• Multi-stage variants (e.g, two- and three-stage two-dimensional cutting stock problems);
• Multi-period variants (e.g., plan the production for several days with the possibility of delaying or anticipating the production of some items).

Note: Suggestions of other cutting & packing problems (including industrial applications) are welcome! [Contact]

Requirements

Mandatory

• 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

Optional (Python API)

• python-2.7 or python-3.x
• python-pip
• python-dev
• glpk-utils

Platforms

It has been successfully compiled and run on the following platforms:

• Linux
• Mac OS X
• On a large variety of platforms including Windows using a Docker container
• It also runs on Windows using Cygwin (a Unix-like environment and command-line interface)

Solution method

• Brandão, F. (2017). Cutting & Packing Problems: 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.
• 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. Available at http://arxiv.org/abs/1310.6887.

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.
[PhD Thesis] [Poster] [Computational Results] [BibTeX]

References:

• Brandão, F. (2017). Cutting & Packing Problems: General Arc-flow Formulation with Graph Compression.