Rod Cutting, in depth: the DP as the pricing engine of cutting stock column generation

The DP, restated for pricing

Let r[j] be the best value obtainable from a rod of length j. Either the rod wastes its last unit (r[j-1]) or its last piece has some length l_i with price v_i, giving v_i + r[j - l_i]. Allowing waste matters here: in cutting stock, leftover material is normal, and forcing an exact fit would make many rods unusable. Because any piece may be used repeatedly, this is the unbounded knapsack problem, and it runs in O(m W) time for m piece types and stock length W.

def price_pattern(W, lengths, values):
    """Rod cutting / unbounded knapsack. Returns (best value, pattern),
    where pattern[i] = number of pieces of type i cut from one rod."""
    best = [0.0] * (W + 1)
    choice = [-1] * (W + 1)              # -1 = waste one unit of length
    for j in range(1, W + 1):
        best[j], choice[j] = best[j - 1], -1
        for i, (l, v) in enumerate(zip(lengths, values)):
            if l <= j and best[j - l] + v > best[j] + 1e-12:
                best[j], choice[j] = best[j - l] + v, i
    pattern, j = [0] * len(lengths), W
    while j > 0:
        i = choice[j]
        if i < 0:
            j -= 1
        else:
            pattern[i] += 1
            j -= lengths[i]
    return best[W], pattern

The tolerance in the comparison matters once the values are floating-point duals from an LP solver; without it, ties flip on rounding noise and the loop can cycle between equivalent patterns.

From one rod to many: patterns and dual prices

A pattern is a way to cut one stock rod: a vector a where a_i is the number of pieces of length l_i, with the sum of a_i times l_i at most W. If x_p rods are cut with pattern p, cutting stock is the integer program: minimise the sum of x_p subject to, for every piece type i, the sum over patterns of a_ip times x_p being at least the demand d_i.

The trouble is the number of patterns, which grows exponentially with the number of piece types and the ratio of W to the piece lengths. Column generation never lists them. It solves the LP relaxation over a small restricted master set of patterns, then asks whether any unlisted pattern would improve it.

LP duality answers that question. The master LP has one dual value y_i per demand row, and y_i is the marginal cost, in rolls, of one more piece of type i. A pattern a has reduced cost 1 - sum of y_i a_i: the roll it costs minus the value of the pieces it yields. If some pattern has negative reduced cost, adding it can lower the objective. Finding the pattern with the most negative reduced cost means maximising the sum of y_i a_i subject to the rod length, which is exactly rod cutting with prices y. If the best value is at most 1, no pattern can improve the LP, and the current solution is optimal for the full LP, over every pattern that exists. The simplex method article explains why pricing works: column generation is the simplex entering-variable rule with the columns computed on demand.

The column generation loop

With SciPy's HiGHS backend the master is a few lines. linprog minimises with less-than-or-equal constraints, so the covering rows are negated, and the duals come back as res.ineqlin.marginals, the sensitivity of the objective to each right-hand side. Those are zero or negative here, so the piece prices are their negatives. Check this sign on your solver with a two-piece instance you can solve by hand; a sign error turns the pricing step into nonsense that still runs.

import numpy as np
from scipy.optimize import linprog

def solve_master(patterns, demand):
    A = np.array(patterns, dtype=float).T          # rows = piece types
    res = linprog(np.ones(A.shape[1]), A_ub=-A, b_ub=-np.array(demand, float),
                  bounds=(0, None), method="highs")
    return res, -res.ineqlin.marginals              # duals y >= 0

def column_generation(W, lengths, demand):
    patterns = []
    for i, l in enumerate(lengths):                 # start: one homogeneous
        p = [0] * len(lengths); p[i] = W // l       # pattern per piece type
        patterns.append(p)
    while True:
        res, y = solve_master(patterns, demand)
        value, pat = price_pattern(W, lengths, y)
        if value <= 1 + 1e-9:                       # no negative reduced cost
            return patterns, res
        patterns.append(pat)

Worked example: rolls of width 100

The classic instance from the cutting-stock literature uses rolls of width 100 and demands of 97 pieces of 45, 610 of 36, 395 of 31 and 211 of 14. Running the code:

Read the first row as prices. The homogeneous pattern for 14s fits seven pieces, so a 14 costs a seventh of a roll. At those prices two 36s and two 14s, which fill the roll exactly, are worth 1.2857 rolls, so that pattern enters. In the third round the best pattern is worth exactly 1, so the LP is optimal: 452.25 rolls, using 48.5 rolls of two 45s (10 waste), 206.25 rolls of two 36s plus two 14s (no waste) and 197.5 rolls of one 36 plus two 31s (2 waste).

The dual for the 14s falling to zero is informative. The zero-waste pattern overproduces 14s, so at the margin they are free, and the solver will happily make more than were ordered.

Now make it integer. Rounding every fractional x up gives 454 rolls. Solving the master as an integer program over the six generated patterns, with scipy.optimize.milp, gives 453: 49, 206 and 198 rolls of the three patterns. Since the LP bound is 452.25 and rolls are whole, 453 is provably optimal. The material bound, total piece length divided by 100, is only 415.24, so the LP bound is far tighter than the naive one.

Each iteration also yields a lower bound before the loop ends. When every roll costs 1, dividing the restricted master's value by the best pattern value gives a valid bound on the full LP (Farley's bound). Here that is 515.31 / 1.2857 = 400.8 after the first round and 485.17 / 1.1667 = 415.9 after the second, against an eventual 452.25. On large instances, where hundreds of rounds are common, this bound lets you stop as soon as its rounded-up value meets the rounded-up master value, because further rounds cannot change the number of whole rolls.

From the LP bound to whole rolls

This instance had a lucky property: solving the integer program over the columns generated for the LP reached the LP bound rounded up. That is common in practice. Instances whose integer optimum equals the rounded-up LP value are said to have the integer round-up property, and most real instances have it. It is not guaranteed. Instances with a gap greater than one roll exist but are rare, and the conjecture that the gap is always below two remains open.

So there are three levels of rigour. Rounding plus a repair heuristic is fast and usually within a roll or two. Price-and-branch, a MIP over the generated columns as above, is better, but it can miss the optimum because the columns that the integer solution needs may never have been priced. Branch-and-price runs column generation at every node of the branch-and-bound tree, with branching rules that keep the pricing problem a knapsack, and is exact. Always report the LP bound alongside your answer, because the gap tells you how much rigour you still need.

Operational guidance

Real cutting floors add constraints, and most of them land in the pricing DP, which is where the rod-cutting variants earn their keep:

• Kerf. If every cut destroys k units, add k to every piece length and to the stock length. The last piece needs no cut after it, and the extra k on the stock pays for exactly that.
• Units. The DP is pseudo-polynomial in W. Express lengths in the machine's real resolution (millimetres, not micrometres) and divide out any common factor; a W of 12,000 is trivial, a W of 12,000,000 is not.
• Limited knives or pieces per pattern. Add a piece count to the DP state, as in the bounded variants on the textbook page.
• Overproduction. Covering constraints allow surplus. If surplus costs money, bound a_i by d_i in the pricing step (a bounded knapsack), use equality rows, or price surplus explicitly.
• Multiple stock lengths. Run one pricing DP per stock length with that stock's cost in place of 1, and add the best column overall.
• Setups. Each distinct pattern costs a machine changeover. The LP ignores this; limit distinct patterns in the integer stage or merge similar patterns afterwards.

The same family of problems appears in machine learning infrastructure: packing variable-length sequences into fixed-length training contexts, or jobs into GPU memory, is one-dimensional bin packing, and the pattern-and-price view is useful whenever the item lengths repeat many times.

Failure modes

Where implementations go wrong:

• Dual sign or scale errors. The loop runs but adds useless patterns or stops at once. Check duals on a hand-solvable case, and assert that the stop condition holds with the final duals.
• Missing tolerance. Stopping on value greater than 1 exactly cycles on degenerate LPs; use a small epsilon in both the DP comparison and the stop test.
• Tailing off. On large instances the LP bound improves slowly over many iterations. Stop when the rounded-up bound can no longer change, or use the Lagrangian bound, LP value divided by the best pattern value, to stop early with a guarantee.
• An infeasible start. Every piece type needs a starting column. A piece longer than the stock makes the whole problem infeasible; check it before solving.
• Trusting rounding. Rounding can be several rolls worse than optimal on instances with many low-demand items. Report the bound and the gap.

What to do next

1. Read the textbook rod cutting article and run its brute-force test against the waste-allowing DP above.
2. Reproduce the 452.25 and 453 results with SciPy, and print the duals at each iteration.
3. Add kerf and a maximum of five pieces per pattern, and watch which patterns change.
4. Compare rounding, price-and-branch and the LP bound on 20 random instances with demands between 1 and 20, where rounding hurts most.
5. Study the 0/1 knapsack DP for the bounded pricing variant, and the dynamic programming overview for how state design drives these extensions.
6. When instances exceed a few hundred piece types, move to a dedicated branch-and-price framework and keep this loop as a test oracle.