Cutting stock problems

Describes examples that involve cutting larger-sized objects such as sheets, rolls, or boards, into smaller ones to meet a demand.

Cutting stock problems are a typical application of integer programming (IP). They involve cutting larger-sized objects such as sheets, rolls, or boards, into smaller ones to meet a demand.

A set of board-cutting examples

The problem consists of cutting big wooden boards into small shelves to meet customer demands while minimizing the number of boards used. A given instance specifies the length of the boards (an integer), the length of the shelves (integers), and the demand for each shelf type (integers as well).

The examples are:

  • A possible main problem formulation with a fixed number of patterns. This problem is then used by column generation models: examples/opl/cutstock.mod. This example is accessed using the default run configuration Fixed number of patterns.

  • A possible main formulation in the project: examples/opl/cutstock/cutstock_change.mod. This example is accessed using the run configuration Alternate formulation of fixed number of patterns.

  • A flow-control scripting example based on column generation that solves the full relaxed problem in the project: examples/opl/cutstock/cutstock_main.mod. This example is accessed using the run configuration Full relaxed problem using column generation. Instead of using a separate .dat file for the submodel, the data used by the submodel is created using IloOplDataElements initialized with data from the master model.

    The subproblem can also be solved by using IBM ILOG Script external functions to call an external knapsack algorithm implemented in Java. See javaknapsack.mod.

  • A flow-control scripting example based on column generation that solves the full integer problem in the project: examples/opl/cutstock/cutstock_int_main.mod. This example is accessed using the run configuration Full integer problem using column generation.

See also Advanced feature: External functions in the Language User’s Manual.