Optimal carpet cutting

Andreas Schutt, Peter J. Stuckey, Andrew R. Verden

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

11 Citations (Scopus)

Abstract

In this paper we present a model for the carpet cutting problem in which carpet shapes are cut from a rectangular carpet roll with a fixed width and sufficiently long length. Our exact solution approaches decompose the problem into smaller parts and minimise the needed carpet roll length for each part separately. The customers requirements are to produce a cutting solution of the carpet within 3 minutes, in order to be usable during the quotation process for estimating the amount of carpet required. Our system can find and prove the optimal solution for 106 of the 150 real-world instances provided by the customer, and find high quality solutions to the remainder within this time limit. In contrast the existing solution developed some years ago finds (but does not prove) optimal solutions for 30 instances. Our solutions reduce the wastage by more than 35% on average compared to the existing approach.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming, CP 2011 - 17th International Conference, Proceedings
PublisherSpringer
Pages69-84
Number of pages16
ISBN (Print)9783642237850
DOIs
Publication statusPublished - 26 Sep 2011
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2011 - Perugia, Italy
Duration: 12 Sep 201116 Sep 2011
Conference number: 17th
http://www.dmi.unipg.it/cp2011/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6876 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2011
Abbreviated titleCP 2011
CountryItaly
CityPerugia
Period12/09/1116/09/11
Internet address

Cite this

Schutt, A., Stuckey, P. J., & Verden, A. R. (2011). Optimal carpet cutting. In Principles and Practice of Constraint Programming, CP 2011 - 17th International Conference, Proceedings (pp. 69-84). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6876 LNCS). Springer. https://doi.org/10.1007/978-3-642-23786-7_8