Due to its flexibility and effectiveness, the general arc-flow formulation is currently being used with success by a large multinational company in the the labeling & packaging industry to solve the following problem variant. In the cost-based cutting stock problem, instead of focusing on minimizing the number of rolls used (minimizing the waste if the demand is required to be satisfied exactly), we allow under- and/or over-production, weighing the cost of off-cut with the cost of holding stock for a number of days and/or the cost missing the production of some items. Stock limits for each day are allowed, and the total number of stock items produced may also be limited. Under- and over-production for the first day may be allowed under given tolerances with given costs per item. Miss-production out of tolerance of some items for the first day is allowed and penalized with a cost per item.

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

### 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 cost-based cutting stock solver accepts instances in the following format:
Format:
$\begin{matrix} n_d \\ p_{\ }^{\ } & & & \\ d_{o} & c_{o}\\ c_r & n_r & l_s\\ \mbox{W}^{1} & \ldots & \mbox{W}^{p} \\ m_{\ }^{\ } & & & \\ w_{1}^{1} & \ldots & w_{1}^{p} & b_1^1 & t_1^u & t_1^o & b_1^2 & \dots & b_1^{n_d} & cm_1 & cu_1 & co_1 & cp_1^{2} & \dots & cp_1^{n_d} \\ \vdots & & \vdots & \vdots & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots & \vdots & \vdots & & \vdots \\ w_{i}^{1} & \ldots & w_{i}^{p} & b_i^1 & t_i^u & t_i^o & b_i^2 & \dots & b_i^{n_d} & cm_i & cu_i & co_i & cp_i^{2} & \dots & cp_i^{n_d} \\ \vdots & & \vdots & \vdots & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots & \vdots & \vdots & & \vdots \\ w_{m}^{1} & \ldots & w_{m}^{p} & b_m^1 & t_m^u & t_m^o & b_m^2 & \dots & b_m^{n_d} & cm_m & cu_m & co_m & cp_m^{2} & \dots & cp_m^{n_d} \\ \end{matrix}$
Description & Limits in this online demo:
$n_d$- number of days $(1 \leq n_d \leq 7, \mbox{integer})$
$p_{\ }^{\ }$- number of dimensions $(1 \leq p \leq 1000, \mbox{integer})$
$d_{o}$- off-cut dimension $(1 \leq d_{o} \leq p, \mbox{integer})$
$c_{o}$- off-cut cost per unit $(c_{o} \geq 0, \mbox{real})$
$c_r$- cost per roll of material $(c_r \geq 0, \mbox{integer})$
$n_r$- number of rolls available $(n_r \geq 0, \mbox{integer}\ [\star])$
$l_s$- stock production limit $(l_s \geq 0, \mbox{integer}\ [\star])$
$\mbox{W}^{d}$- capacity on dimension $d$ $(1 \leq \mbox{W}^{d} \leq 10^{5}, \mbox{integer})$
$m_{\ }^{\ }$- number of different item types $(1 \leq m \leq 1000, \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})$
$b_i^j$- demands for items of type $i$ for day $j$ $(0 \leq b_{i}^1 \leq 10^{7}, \mbox{integer})$
$t_{i}^u$- under-production tolerance for items of type $i$ $(t_i^u \geq 0, \mbox{integer})$
$t_{i}^o$- over-production tolerance for items of type $i$ $(t_i^o \geq 0, \mbox{integer})$
$cm_i$- cost for under-producing out of tolerance an item of type $i$ for the first day $(cm_i \geq 0, \mbox{real}\ [\star])$
$cu_i$- cost for under-producing within tolerance an item of type $i$ for the first day $(cu_i \geq 0, \mbox{real}\ [\star])$
$co_i$- cost for over-producing within tolerance an item of type $i$ for the first day $(co_i \geq 0, \mbox{real}\ [\star])$
$cp_i^j$- cost for producing in advance an item of type $i$ for day $j$ $(cp_i^j \geq 0, \mbox{real}\ [\star])$
$\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 [Poster] [VPSolver 3 Report] [Paper].

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:

• 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]