Cost-based Cutting Stock

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) on AWS Lambda. Much better run times can be achieved using Gurobi or CPLEX.



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.


This cost-based cutting stock solver accepts instances in the following 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 [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