Groupe d’études et de recherche en analyse des décisions


Cutting Stock Problems


Linear relaxations are solved by column generation. Stabilization techniques such as dual-optimal inequalities and stabilized column generation algorithms that have been proposed to improve the efficiency of this process are briefly discussed. Integer solutions are obtained by combining heuristics and branch-and-price schemes. We survey the basic models proposed for cutting stock and the corresponding solution approaches. Extended Dantzig-Wolfe decomposition is surveyed and applied to these models in order to show the links to Gilmore–Gomory model. Branching schemes discussion is based on the subproblem formulation corresponding to each model.

, 30 pages