Approximate and Exact Algorithms for Constrained (Un) Weighted Two-dimensional Two-staged Cutting Stock Problems

Mhand Hifi () and Catherine Roucairol ()
Additional contact information
Mhand Hifi: Université Paris
Catherine Roucairol: Université de Versailles-Saint Quentin en Yvelines

Journal of Combinatorial Optimization, 2001, vol. 5, issue 4, No 6, 465-494

Abstract: Abstract In this paper we propose two algorithms for solving both unweighted and weighted constrained two-dimensional two-staged cutting stock problems. The problem is called two-staged cutting problem because each produced (sub)optimal cutting pattern is realized by using two cut-phases. In the first cut-phase, the current stock rectangle is slit down its width (resp. length) into a set of vertical (resp. horizontal) strips and, in the second cut-phase, each of these strips is taken individually and chopped across its length (resp. width). First, we develop an approximate algorithm for the problem. The original problem is reduced to a series of single bounded knapsack problems and solved by applying a dynamic programming procedure. Second, we propose an exact algorithm tailored especially for the constrained two-staged cutting problem. The algorithm starts with an initial (feasible) lower bound computed by applying the proposed approximate algorithm. Then, by exploiting dynamic programming properties, we obtain good lower and upper bounds which lead to significant branching cuts. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approximate and exact approaches.

Keywords: combinatorial optimization; cutting problems; dynamic programming; single knapsack problem; optimality (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://link.springer.com/10.1023/A:1011628809603 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:5:y:2001:i:4:d:10.1023_a:1011628809603

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1011628809603

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().