The multiple-choice p-dimensional vector bin packing problem is a variant of vector packing 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).
Description & Limits in this online demo: $p$
- number of dimensions
$(1 \leq p \leq 1000, \mbox{integer})$ $q$
- number of different bin types
$(1 \leq q \leq 10, \mbox{integer})$ $\mbox{W}_{j}^{d}$
- capacity on dimension $d$ on bins of type $j$
$(0 \leq \mbox{W}_j^{d} \leq 10^{5}, \mbox{integer})$ $\mbox{C}_{j}$
- cost per bin of type $j$
$(\mbox{C}_j \geq 0, \mbox{integer})$ $\mbox{Q}_{j}$
- number of bins of type $j$ available
$(\mbox{Q}_j \geq 0, \mbox{integer}\ [\star])$ $m_{\ }^{\ }$
- number of different items
$(1 \leq m \leq 100, \mbox{integer})$ $b_{i}$
- demand for items of type $i$
$(1 \leq b_{i} \leq 10^{7}, \mbox{integer})$ $t_{i}$
- number of different incarnations of items of type $i$
$(1 \leq t_{i} \leq 10, \mbox{integer})$ $w_{i,j}^{d}$
- weight on dimension $d$ of incarnation $j$ of items of type $i$
$(\mbox{integer})$
$\star $- or any negative number (e.g., -1) if $\infty$
- 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.
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]