The Cutting Stock Problem — Interactive Chapter

Problem

From rolls to patterns

The chapter’s example has 10-foot master rolls. Customers demand 23 rolls of length 2, 25 rolls of length 3, 30 rolls of length 4, and 11 rolls of length 5.

A pattern is a vector p=(a,b,c,d). It is feasible when 2a+3b+4c+5d≤10. Pattern (2,0,0,1), for example, cuts two 2-foot rolls and one 5-foot roll from a master roll, leaving one foot unused.

The decision variable x_p is the number of master rolls cut according to pattern p.

LP and dual

The compact formulation

(LP)   minimize   ∑p∈P xp
subject to   ∑p∈P pixp ≥ demandi   for every roll type i,
xp ≥ 0.

(D)   maximize   ∑i demandiyi
subject to   ∑i piyi ≤ 1   for every pattern p∈P,
yi ≥ 0.

The primal has many variables. The dual has one constraint for every possible pattern. That lets us search for missing constraints instead of writing every pattern in advance.

Interactive Pattern lab

Edit the roll length, item lengths, and demands. The page enumerates feasible patterns and turns each pattern into its corresponding dual constraint.

Instance data

Master roll length

Item lengths

Demands

—

Patterns

—

Total demand length

—

Length bound

—

Types

—

Selected pattern

—

Click a pattern in the table to see its constraint.

Feasible patterns

nonzero only

The table is sorted by waste, then by number of pieces. For the chapter instance there are 29 feasible nonzero patterns.

Separation

The missing constraint is a knapsack problem

Given a candidate dual solution ȳ, every pattern must satisfy p·ȳ≤1. The worst possible pattern is found by solving:

maximize   ȳ₁a + ȳ₂b + ȳ₃c + ȳ₄d
subject to   2a+3b+4c+5d≤10,
a,b,c,d ≥ 0 and integer.

If the optimum is larger than 1, the corresponding pattern gives a violated dual constraint. If it is at most 1, all dual constraints are satisfied.

Interpretation

Why this is column generation

The dual view finds a violated constraint. In the primal LP, the same object is a useful missing variable: a cutting pattern with negative reduced cost.

Dual separation and primal column generation are the same loop seen from opposite sides.

The page below solves the restricted dual exactly by enumerating basic feasible solutions. That is enough for the small teaching examples in this chapter.

Interactive Knapsack pricing oracle

Choose dual values. The oracle searches every feasible cutting pattern and reports the one with maximum p·y.

Dual values

chapter instance

—

Best priced pattern

—

The knapsack result will appear here.

Interactive Column generation / cutting-plane workbench

Start with only a few patterns, solve the restricted dual, price a new pattern by knapsack, add the violated pattern, and repeat.

Current columns

—

Dual objective

—

Best pricing value

—

Status

—

Controls

not solved

—

Current restricted dual solution

Solve the restricted dual to display y.

Iteration log

Chapter replay

D′₁ → D′₄

The buttons above load the same restricted duals used in the chapter. The final solution is y=(2/10,3/10,4/10,5/10), where the knapsack objective is at most 1 because it is one tenth of the roll-length constraint.

Current pattern constraints

p·y ≤ 1

Pricing output

—

Run pricing to find a missing pattern.

Interactive Recover the primal solution

Once no dual constraint is violated, strong duality gives the primal optimum. For the chapter data, the fractional LP optimum is 29.6 master rolls.

Restricted primal solve

—

This solves the current restricted primal LP by enumerating basic feasible solutions. It is designed for the small examples in the chapter.

—

Demand coverage

produced − demand

Solve the primal to display coverage.

The duality certificate will appear here.

Integer reality check

optional

The chapter assumes monthly repeated demand, so fractional roll counts are acceptable. If you force whole master rolls, the page can compute an exact small integer cover by dynamic programming.

—

Takeaway

The algorithmic pattern

When an LP has too many variables, solve a restricted version, use the dual solution to search for a missing useful variable, and add that variable only if it improves the model.

restricted master problem → dual prices → pricing problem → new column

In this chapter

Why knapsack appears

A cutting pattern is exactly a way of packing item lengths into one master roll. Therefore the pricing problem is a knapsack problem whose item values are the current dual prices.

This is the same idea used in much larger column-generation models, including industrial scheduling and routing models.