VPSolver is a multiple-choice vector packing solver based on an arc-flow formulation with graph compression [Poster] [Paper] [VPSolver 3 Report]. 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.

Online demos

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:

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]

Requirements

Mandatory

Optional (Python API)

Platforms

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

Solution method

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.
graph
[Poster] [Report] [Computational Results] [BibTeX]

References: