Multi-stage Cutting Stock

The two-dimensional cutting stock problem consists of cutting rectangular pieces from stock sheets (possibly with several different sizes and costs) in such a way the cost is minimized. In the multi-stage version of the problem, the process is divided into several stages (usually two or three), and in each stage we are only allowed to perform either horizontal or vertical guillotine cuts. In the first stage we are only allowed to perform horizontal cuts, in the second stage we are only allowed to perform vertical cuts, and so on. Item rotation may or may not be allowed. Exact final cut of pieces may or may not be required at the last stage.

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

Clear Solve

Output

Download .LP model Download .MPS model Donwload Solution

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 multi-stage cutting stock solver accepts instances in the following format:

Format:
$\begin{matrix} s \\ q \\ W_1 & H_1 & C_1 \\ \vdots & \vdots & \vdots \\ W_t & H_t & C_t \\ m_{\ }^{\ } & r & e & \\ w_1 & h_1 & b_1 \\ \vdots & \vdots & \vdots \\ w_{i} & h_{i} & b_i \\ \vdots & & \vdots & \\ w_{m} & h_m & b_{m} \\ \end{matrix}$

Description & Limits in this online demo:
$s$ - number of stages $(s \in \{2\})$
$q$ - number of different sheet types $(1 \leq q \leq 2, \mbox{integer})$
$W_i$ - width of sheets of type $i$ $(1 \leq W_i \leq 1000, \mbox{integer})$
$H_i$ - height of sheets of type $i$ $(1 \leq H_i \leq 1000, \mbox{integer})$
$C_i$ - cost of sheets of type $i$ $(C_i \geq 0, \mbox{integer})$
$m$ - number of different item types $(1 \leq m \leq 150, \mbox{integer})$
$r$ - item rotation is allowed or not $(r \in \{0,1\})$
$e$ - exact final cut is required of not $(e \in \{0,1\})$
$w_{i}$ - width of items of type $i$ $(w_{i} \geq 0, \mbox{integer})$
$h_{i}$ - height of items of type $i$ $(h_{i} \geq 0, \mbox{integer})$
$b_{i}$ - demand for items of type $i$ $(1 \leq b_{i} \leq 100, \mbox{integer})$
   - 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.
[Computational results on several benchmark test data sets]

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]

Online demos

Vector Packing Multiple-choice Vector Packing Multi-stage Cutting Stock Cost-based Cutting Stock