Cutting Stock Problem with Multiple Master Rolls

This demo provides an overview of the Gurobi Optimization Application Demo by showing the optimization process to solve the cutting stock problem wich consists of two fundamental steps: an algorithm to generate all the possible cutting patterns and a Mixed Integer Programming (MIP) formulation to solve the problem considering all the possible cutting patterns.

Introduction to the Cutting Stock Problem with Multiple Master Rolls

Let’s look at a simple example of a paper mill that needs to minimize operating costs while facing certain constraints. The mill supplies paper rolls or “final rolls” to customers that are cut from several master rolls of different widths. The width of a master roll defines a master roll type. The need is to generate a master roll cutting plan that minimizes the cost of cutting and procuring master rolls consumed to satisfy all the demands of the final rolls.

For each master roll type, there is a per-unit cutting cost and an initial inventory available at the beginning of the planning horizon. Extra master rolls of each type can be bought at a procurement cost. There is aggregate demand for smaller rolls (final rolls) cut from a master roll. The width of a final roll defines a demand type. Master rolls are then cut into final rolls in order to meet demand. We assume that there is a single machine that cuts the different types of master rolls to satisfy the aggregate demand of final rolls.

The machine has a specific number of usable knives to cut the master roll. The number of knives in the machine limits the possible cutting configurations. After a master roll is cut, the left-over (spare) roll may be re-usable if the spare roll width is larger than a specified threshold width.

Cutting Patterns of Master rolls to fill the demand of Final rolls:

Business Goals

A slitter rewinder machine, as shown below, can cut a large master roll of material into narrower final rolls. The master roll is unwound and run through the machine, passing through knives, before being rewound on one or more shafts to form narrower final rolls.

The width of a master roll defines a master roll type. For each master roll type, there is a per-unit cutting cost, and an initial inventory available at the beginning of the planning horizon. Extra master rolls of each type can be bought at a procurement cost.

The width of a final roll defines a demand type. Master rolls are then cut into final rolls in order to meet the demand. We assume that there is a single machine that cuts the different types of master rolls to satisfy the aggregate demand of final rolls. The machine has a specific number of usable knives to cut the master roll. The number of knives in the machine limits the possible cutting configurations. After a master roll is cut, the left-over (spare) roll may be reusable if the spare roll width is larger than a specified threshold width. Otherwise, the spare roll is considered as scrap.

The goal of the optimization is to generate a master roll-cutting plan that minimizes the cost of cutting and procuring master rolls while satisfying the demand for final rolls.

Machine Learning vs Mathematical Optimization

This cutting stock problem is an example of combinatorial optimization problems that cannot be attacked with machine learning techniques due to the astronomical number of possibilities in the solution space. Also, open-source optimization solvers do not scale to real size cutting stock problems. When Gurobi and machine learning join forces, the possibilities for data scientists are endless. Leading companies around the world use Gurobi to set schedules, evenly distribute resources, and generally save a lot of time, money, and headaches.

Access the Cutting Stock Problem with Multiple Master Rolls

To access the Cutting Stock Problem demo application and create your scenario using your own data from a blank template or to play with existing default scenarios, you must first register for a Gurobi website account and then view the demo.