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.
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:
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]