A branch-and-price algorithm for the two-stage guillotine cutting stock problem

M Mrad, I Meftahi and M Haouari
Additional contact information
M Mrad: King Saud University, Riyadh, Saudi Arabia
I Meftahi: University of Carthage, Tunis, Tunisia
M Haouari: Department of Mechanical and Industrial Engineering, College of Engineering, Qatar University, Doha, Qatar

Journal of the Operational Research Society, 2013, vol. 64, issue 5, 629-637

Abstract: We investigate the two-stage guillotine two-dimensional cutting stock problem. This problem commonly arises in the industry when small rectangular items need to be cut out of large stock sheets. We propose an integer programming formulation that extends the well-known Gilmore and Gomory model by explicitly considering solutions that are obtained by both slitting some stock sheets down their widths and others down their heights. To solve this model, we propose an exact branch-and-price algorithm. To the best of our knowledge, this is the first contribution with regard to obtaining integer optimal solutions to Gilmore and Gomory model. Extensive results, on a set of real-world problems, indicate that the proposed algorithm delivers optimal solutions for instances with up to 809 items and that the hybrid cutting strategy often yields improved solutions. Furthermore, our computational study reveals that the proposed modelling and algorithmic strategy outperforms a recently proposed arc-flow model-based solution strategy.

Date: 2013
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.palgrave-journals.com/jors/journal/v64/n5/pdf/jors201270a.pdf Link to full text PDF (application/pdf)
http://www.palgrave-journals.com/jors/journal/v64/n5/full/jors201270a.html Link to full text HTML (text/html)
Access to full text is restricted to subscribers.

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:pal:jorsoc:v:64:y:2013:i:5:p:629-637

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().