Exact Algorithm for Minimising the Number of Setups in the One-Dimensional Cutting Stock Problem

François Vanderbeck ()
Additional contact information
François Vanderbeck: Mathématiques Appliquées Bordeaux (MAB), Université Bordeaux 1, 351 Cours de la Libération, F-33405 Talence Cedex, France

Operations Research, 2000, vol. 48, issue 6, 915-926

Abstract: The cutting stock problem is that of finding a cutting of stock material to meet demands for small pieces of prescribed dimensions while minimising the amount of waste. Because changing over from one cutting pattern to another involves significant setups, an auxiliary problem is to minimise the number of different patterns that are used. The pattern minimisation problem is significantly more complex, but it is of great practical importance. In this paper, we propose an integer programming formulation for the problem that involves an exponential number of binary variables and associated columns, each of which corresponds to selecting a fixed number of copies of a specific cutting pattern. The integer program is solved using a column generation approach where the subproblem is a nonlinear integer program that can be decomposed into multiple bounded integer knapsack problems. At each node of the branch-and-bound tree, the linear programming relaxation of our formulation is made tighter by adding super-additive inequalities. Branching rules are presented that yield a balanced tree. Incumbent solutions are obtained using a rounding heuristic. The resulting branch-and-price-and-cut procedure is used to produce optimal or approximately optimal solutions for a set of real-life problems.

Keywords: Integer programming algorithms: decomposition; branch-and-bound; branch-and-price; column generation; cutting plane; heuristic; relaxation; Production/scheduling: cutting stock/trim (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (28)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.48.6.915.12391 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:48:y:2000:i:6:p:915-926

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().