The p-dimensional vector bin 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. By means of reductions to vector packing, several cutting & packing problems, including the one-dimensional bin packing and cutting stock problems, can be solved.

### Instance

Currently in spreadsheet editing mode. Try the fallback plain text editor.

### Output

You can submit the .MPS models to the NEOS Server in order to check how quickly they can be solved using a commercial solver such as Gurobi even with default parameter settings. Nevertheless, non-commercial solvers are still effective on a large range of instances.

## Help

This $p$-dimensional vector packing solver accepts instances in the following format:
Format:
$\begin{matrix} p_{\ }^{\ } & & & \\ \mbox{W}^{1} & \ldots & \mbox{W}^{d} & \ldots & \mbox{W}^{p} \\ m_{\ }^{\ } & & & \\ w_{1}^{1} & \ldots & w_{1}^{d} & \ldots & w_{1}^{p} & b_1 \\ \vdots & & \vdots & & \vdots & \vdots\\ w_{i}^{1} & \ldots & w_{i}^{d} & \ldots & w_{i}^{p} & b_i \\ \vdots & & \vdots & & \vdots & \vdots \\ w_{m}^{1} & \ldots & w_{m}^{d} & \ldots & w_{m}^{p} & b_m \\ \end{matrix}$
Description & Limits in this online demo:
$p$ - number of dimensions $(1 \leq p \leq 1000, \mbox{integer})$
$\mbox{W}^{d}$ - capacity on dimension $d$ $(1 \leq \mbox{W}^{d} \leq 10^{5}, \mbox{integer})$
$m$ - number of different items $(1 \leq m \leq 1000, \mbox{integer})$
$b_i$ - demand for items of type $i$ $(1 \leq b_{i} \leq 10^{7}, \mbox{integer})$
$w_i^d$ - weight on dimension $d$ of items of type $i$ $(0 \leq w_{i}^{d} \leq \mbox{W}^{d}, \mbox{integer})$
- non-numeric values in the input are discarded;
- there are also time and memory limits that may not allow solving large instances;
- the limitations of this online demo do not correspond to the real limits of the software.

## Solution method

VPSolver is a multiple-choice vector packing solver based on an arc-flow formulation with graph compression [PhD Thesis] [Poster] [Paper] [BibTeX].

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]