Initializing help system before first use

Example problem: cutting stock

A paper mill produces rolls of paper of a fixed width MAXWIDTH that are subsequently cut into smaller rolls according to the customer orders. The rolls can be cut into NWIDTHS different sizes. The orders are given as demands for each width i (DEMANDi). The objective of the paper mill is to satisfy the demand with the smallest possible number of paper rolls in order to minimize the losses.

The objective of minimizing the total number of rolls can be expressed as choosing the best set of cutting patterns for the current set of demands. Since it may not be obvious how to calculate all possible cutting patterns by hand, we start off with a basic set of patterns (PATTERNS_1,..., PATTERNSNWIDTH), that consists of cutting small rolls all of the same width as many times as possible (and at most the demanded quantity) out of the large roll.

If we define variables usej to denote the number of times a cutting pattern j (j ∈ WIDTHS = {1,...,NWIDTH}) is used, then the objective becomes to minimize the sum of these variables, subject to the constraints that the demand for every size has to be met.

minimize
∑
j ∈ WIDTHS
usej
∑
j ∈ WIDTHS
PATTERNSij · usej ≥ DEMANDi
∀ j ∈ WIDTHS: usej ≤ ⌈DEMANDj / PATTERNSjj⌉ , usej ∈ ℕ

The paper mill can satisfy the demand with just the basic set of cutting patterns, but it is likely to incur significant losses through wasting more than necessary of every large roll and by cutting more small rolls than its customers have ordered. We therefore employ a column generation heuristic to find more suitable cutting patterns.

Our heuristic performs a column generation loop at the top node, before starting the MIP search. Every iteration of the column generation loop executes the following steps:

  1. solve the LP and save the basis
  2. get the solution values
  3. compute a more profitable cutting pattern based on the current solution
  4. generate a new column (= cutting pattern): add a term to the objective function and to the corresponding demand constraints
  5. load the modified problem and load the saved basis

Step 3 of this loop requires us to solve an integer knapsack problem of the form

maximize z =
∑
j ∈ WIDTHS
Ci · xj
∑
j ∈ WIDTHS
Aj · xj ≤ B
∀ j ∈ WIDTHS: xj integer

This second optimization problem is independent of the main, cutting stock problem since the two have no variables in common.

Parent Topic Column generation: solving different models in sequence

© 2001-2020 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.