Gilmore and Gomory: generate useful cutting patterns instead of listing them all

What is recorded here?

Gilmore and Gomory solve the linear relaxation of a cutting-stock model by generating profitable cutting patterns through a knapsack pricing problem, keeping only a small working basis rather than enumerating every possible pattern. A factory cutting standard lengths into ordered pieces can have an enormous number of possible cutting patterns. Listing every pattern before optimizing may be impractical. Gilmore and Gomory let the current linear solution assign a value to each ordered piece, then ask a smaller knapsack problem to construct a pattern worth more than its stock cost. A profitable pattern enters the working basis; if exact pricing finds none for every stock length, the linear solution is optimal. Fast ad hoc searches can find improvements, but their failure must be checked by the more complete pricing calculation. The paper solves a worked example costing 170 and notes that its whole-number answer is fortuitous. In general the master solution can be fractional: rounding produces a feasible or repaired integer plan, but does not establish the cheapest integer plan.

Source-linked catalogue note. A detailed explanatory guide has not yet been prepared for this entry.

Scientific scope

matrix/formula glyphs are damaged, not certified transcriptions. Unlimited stock of specified lengths and costs; one-dimensional cutting patterns and order demands. Page 851 explicitly restricts this report to the continuous LP relaxation; integer pattern counts can remain fractional and rounding may be suboptimal. An integer knapsack pricing subproblem does not make the LP master integer. Heuristic pricing can find useful columns; failure requires the complete dynamic-programming check across stock types before claiming LP optimality. Degeneracy/anti-cycling treatment is discussed, not ignored. The worked example has stock lengths 5,6,9 costs 6,7,10 and demands 20,10,20 for lengths 2,3,4; its integer cost 170 is explicitly called fortuitous. This example is not a general benchmark. Ford/Fulkerson, Dantzig/Wolfe and knapsack/dynamic-programming predecessors retain credit. Part II 1963 and later integer/branch-and-price/multidimensional methods are separate. Original reprint says November 1961; Crossref deposits December 1961; only year and issue are used, without silently resolving the discrepancy. The editorial account uses the publication year and does not assert a manuscript receipt date. The complete implementation and cost-model results have not been independently certified here.

Read the original work

• Gilmore and Gomory: generate useful cutting patterns instead of listing them all; exact original technical paper
• Publisher-deposited identity for gilmore-gomory-pattern-column-generation-1961

This English explanation is an editorial reading view. It does not replace the complete original work or certify its science.

People and systems

P. C. Gilmore; R. E. Gomory

Source-listed contributors to this scoped work. Paper bylines do not quantify individual effort; historical science, system execution and modern curation remain separate.