Some linear programs have too many variables to list conveniently, even though each variable has a simple interpretation. In cutting stock, a variable describes how many times we use one feasible arrangement of items on a stock bar. There may be many arrangements, but a candidate solution normally uses only a few. Column generation starts with a small collection, solves that restricted problem, and asks a separate optimization problem whether a missing arrangement is worth adding. Its stopping certificate comes from duality, not from the mere failure to think of another arrangement.
We work with a finite pattern set and exact arithmetic; important limitations appear below.
Motivation
Suppose each available bar has length 10, and pieces have lengths 3 and 4. A bar can hold three pieces of the first type, two of the second, or two of the first and one of the second. A pattern lists the number of pieces of each type made from a single bar. Enumerating all patterns is possible here, but would become burdensome for many item types and a large stock length. We seek a rigorous way to select patterns without guessing in advance which will be useful.
Definitions
Let be a finite, nonempty set of patterns. Pattern produces the nonnegative vector and costs . For demand , consider the full master linear program
Here may be fractional. In a cutting-stock interpretation it is a relaxation of an integer count of bars. The inequalities allow overproduction. This modeling choice matters: requiring exact production would lead to different dual sign restrictions.
For a nonempty subset , the restricted master keeps only variables indexed by . Its feasible solutions extend to full-master solutions by setting omitted variables to zero. The dual of the restricted master is
For a candidate dual vector , the reduced cost of a pattern is . The pricing problem minimizes over all . It is a separate optimization problem: it is not enough to check the patterns already in .
Theorem/proposition
Theorem 17.1.1
(A global certificate from pricing)
Suppose the restricted master is feasible and has a finite attained optimum. Let and be optimal primal and dual solutions of the restricted master. If for every , then the zero-extended is optimal for (1), and is optimal for its full dual.
Proof sketch or proof idea
Proof
(Weak duality closes the gap left by the restricted problem)
Restricted dual feasibility gives . The pricing condition supplies every missing inequality , so is feasible for the full dual. For any full-master feasible , nonnegativity gives
This proves weak duality directly. By linear-programming strong duality on the feasible, finite restricted master, the objective of equals . Its zero extension is feasible for the full master and attains the lower bound just obtained, proving both claims. The condition certifies the entire full LP; it does not establish that the fractional solution is an integer solution.
Proof X-ray
What the pricing calculation actually proves
The restricted primal is feasible for the full problem, so its value is an upper bound on the full minimum. The restricted dual may fail to be feasible for the full dual: an omitted column can violate its inequality. Pricing checks exactly those missing inequalities. When none is violated, the same number is also a lower bound, and the bounds meet.
Proposition 17.1.2
(Finite column generation for a finite pattern set)
Assume is finite, every cost is nonnegative, the initial restricted master is feasible, and each restricted master is solved exactly. At each iteration choose an optimal restricted dual and solve pricing exactly. If its minimum reduced cost is negative, add a minimizing pattern; otherwise stop. The procedure stops after finitely many additions with an optimal solution and dual certificate for the full master.
Proof
(Distinct additions from a finite set)
Because satisfies all inequalities for , no pattern already in has negative reduced cost. Thus each addition is new, so there are at most additions. Every subsequent restricted master remains feasible: the old solution is still available. Its objective is bounded below by zero, since costs and variables are nonnegative. The linear-programming attainment theorem therefore gives a finite attained optimum at every iteration. Upon stopping, exact pricing checks all full-dual inequalities, and the preceding theorem applies.
The nonnegative-cost hypothesis ensures a finite optimum at every iteration. More general costs need a separate boundedness argument. Adding a negative-reduced-cost column need not strictly improve the next objective: degeneracy can leave the optimum unchanged. Finite termination here comes from adding distinct columns, not from a strictly decreasing objective.
Worked examples
Worked example 17.1.3
(Two item types and one useful missing pattern)
A length-10 bar costs 1. Pieces have lengths 3 and 4, with demands . A pattern has nonnegative integer coordinates and satisfies . Start with . The restricted master is
Its optimum is with value . Its dual optimum is , because and . The pricing problem maximizes subject to and integer . The only possible are 0, 1, 2. Their best values are respectively , , and . Thus has reduced cost and must be added.
With this column, take two bars in pattern , giving value 2 and exactly the demand. To certify optimality, use . For , the largest pattern values are . Every pattern therefore has value at most its unit cost, so is full-dual feasible. Its objective is , equal to the displayed primal value. The LP optimum is 2; because the displayed solution also uses whole bars, it is an integer optimum as well.
Worked example 17.1.4
(A fractional master value is not a bar count)
Keep the same stock and piece lengths, but require only one piece of each type. The fractional plan and meets both demands at cost . The dual vector remains feasible for every pattern and has objective , proving that this is the LP optimum. The integer optimum is instead 1: a single bar meets both demands, and any feasible integer solution uses at least one bar. Rounding each fractional variable separately happens to use two bars and is not optimal.
Worked example 17.1.5
(A zero demand and a non-unique restricted dual)
Keep the same stock and patterns, with demands , and start again from . The restricted master is subject to , , , with optimum and value 1. Its dual maximizes subject to , , , so every with is optimal: the zero demand leaves undetermined.
With , pricing maximizes over patterns; the maximum is 1 at , every reduced cost is nonnegative, and the full LP optimum is certified to be 1. With instead, pattern has reduced cost . Adding it does not lower the restricted optimum: using alone would need , costing , so the value stays 1. A negative reduced cost reflects the dual chosen, and an addition need not strictly improve the objective.
Common mistakes
Counterexample mode
A restricted optimum need not solve the full master
In the first example, is optimal using the two initial patterns, but the omitted pattern has negative reduced cost and a two-bar full solution exists. Solving the restricted problem to optimality does not by itself prove global optimality. Conversely, a negative reduced cost is a failure of the chosen dual certificate, not a promise that the next restricted objective will strictly decrease.
Common mistake
(Treating a failed pricing heuristic as a certificate)
A pricing heuristic may find a useful pattern; failure of a heuristic to find one does not prove that every reduced cost is nonnegative. Exact pricing, or a valid lower bound on the minimum reduced cost that is at least zero, supplies the required certificate. A negative reduced cost is computed against a particular dual optimum; a different dual optimum may give different reduced costs. The third worked example shows such a dependence.
Quick check
Quick check
(Why is the restricted objective an upper bound on the full minimum?)
Solution · Answer
Any restricted feasible plan remains feasible in the full master after all omitted variables are set to zero. Adding options cannot increase a minimization optimum.
Exercises
Quick check
(With the length-10 patterns above, determine whether is feasible for the full dual. Give an explicit violated inequality if it is not.)
Solution · Answer
It is not full-dual feasible. Pattern is feasible since , but its dual inequality would require .
Quick check
(For demands , verify both the fractional optimum and the integer optimum 1 without assuming that rounding solves the integer problem.)
Solution · Answer
The fractional solution and matching feasible dual in the second example prove the LP value . A single pattern meets demand, and the positive demand forbids zero bars; thus the integer value is 1.
Quick check
(Suppose a restricted optimum has value 9, and its dual vector has minimum reduced cost 0 over all patterns. What is the full LP optimum? Is the integer optimum necessarily 9?)
Solution · Answer
The full LP optimum is 9 by the pricing certificate and equality of restricted primal and dual objectives. No conclusion about the integer optimum follows without an integer feasible plan of cost 9 or further integer analysis; it may be larger, as the second worked example illustrates.
Quick check
(Suppose pricing is solved only approximately and finds a smallest sampled reduced cost of . Does this certify full LP optimality? Explain what additional fact would suffice.)
Solution · Answer
No. An unexamined pattern might have negative reduced cost. A rigorous lower bound of at least zero on the minimum over all patterns, or an exact global pricing solve with nonnegative minimum, would suffice.