Multiple-choice Vector Packing


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).

The MIP models are being solved using COIN-OR CBC (an open-source MIP solver) on AWS Lambda. Much better run times can be achieved using Gurobi or CPLEX.

Instance

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 multiple-choice $p$-dimensional vector packing solver accepts instances in the following format:
Format:
$\begin{matrix} p_{\ }^{\ } & & & \\ q_{\ }^{\ } & & & \\ \mbox{W}_1^{1} & \ldots & \mbox{W}_1^{d} & \ldots & \mbox{W}_1^{p} & \mbox{C}_{1} & \mbox{Q}_{1} \\ \vdots & & \vdots & & \vdots & \vdots & \vdots &\\ \mbox{W}_{t}^{1} & \ldots & \mbox{W}_{t}^{d} & \ldots & \mbox{W}_{t}^{p} & \mbox{C}_{t} & \mbox{Q}_{t} \\ m_{\ }^{\ } & & & \\ t_1 & b_1 & & \\ w_{1,1}^{1} & \ldots & w_{1,1}^{d} & \ldots & w_{1,1}^{p} \\ \vdots & & \vdots & & \vdots & \\ w_{1,t_1}^{1} & \ldots & w_{1,t_1}^{d} & \ldots & w_{1, t_1}^{p} \\ & & & \\ t_i & b_i & & \\ w_{i,1}^{1} & \ldots & w_{i,1}^{d} & \ldots & w_{i,1}^{p} & \\ \vdots & & \vdots & & \vdots & \\ w_{i,t_i}^{1} & \ldots & w_{i,t_i}^{d} & \ldots & w_{i,t_i}^{p} & \\ & & & \\ t_m & b_m & & \\ w_{m,1}^{1} & \ldots & w_{m,1}^{d} & \ldots & w_{m,1}^{p} & \\ \vdots & & \vdots & & \vdots & \\ w_{m,t_m}^{1} & \ldots & w_{m,t_m}^{d} & \ldots & w_{m,t_m}^{p} & \\ \end{matrix}$
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:

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]

Online demos