Solving a hard cutting stock problem by machine learning and optimisation

Steven D. Prestwich; Adejuyigbe O. Fajemisin; Laura Climent; Barry O’Sullivan

doi:10.1007/978-3-319-23528-8_21

Solving a hard cutting stock problem by machine learning and optimisation

Steven D. Prestwich
, Adejuyigbe O. Fajemisin
, Laura Climent
, Barry O’Sullivan

University College Cork

Research output: Chapter in Book/Report/Conference proceedings › Conference proceeding › peer-review

Abstract

We are working with a company on a hard industrial optimisation problem: a version of the well-known Cutting Stock Problem in which a paper mill must cut rolls of paper following certain cutting patterns to meet customer demands. In our problem each roll to be cut may have a different size, the cutting patterns are semi-automated so that we have only indirect control over them via a list of continuous parameters called a request, and there are multiple mills each able to use only one request. We solve the problem using a combination of machine learning and optimisation techniques. First we approximate the distribution of cutting patterns via Monte Carlo simulation. Secondly we cover the distribution by applying a k-medoids algorithm. Thirdly we use the results to build an ILP model which is then solved.

Original language	English
Title of host publication	Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2015, Proceedings
Editors	Annalisa Appice, João Gama, Vitor Santos Costa, João Gama, Alípio Jorge, Annalisa Appice, Annalisa Appice, Vitor Santos Costa, Alípio Jorge, Annalisa Appice, Pedro Pereira Rodrigues, Pedro Pereira Rodrigues, João Gama, Vitor Santos Costa, Soares Soares, Pedro Pereira Rodrigues, Soares Soares, Soares Soares, João Gama, Soares Soares, Alípio Jorge, Alípio Jorge, Pedro Pereira Rodrigues, Vitor Santos Costa
Publisher	Springer Verlag
Pages	335-347
Number of pages	13
ISBN (Print)	9783319235271, 9783319235271, 9783319235271, 9783319235271
DOIs	https://doi.org/10.1007/978-3-319-23528-8_21
Publication status	Published - 2015
Event	European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2015 - Porto, Portugal Duration: 7 Sep 2015 → 11 Sep 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9284
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2015
Country/Territory	Portugal
City	Porto
Period	7/09/15 → 11/09/15

Access to Document

10.1007/978-3-319-23528-8_21

Cite this

Prestwich, S. D., Fajemisin, A. O., Climent, L., & O’Sullivan, B. (2015). Solving a hard cutting stock problem by machine learning and optimisation. In A. Appice, J. Gama, V. S. Costa, J. Gama, A. Jorge, A. Appice, A. Appice, V. S. Costa, A. Jorge, A. Appice, P. P. Rodrigues, P. P. Rodrigues, J. Gama, V. S. Costa, S. Soares, P. P. Rodrigues, S. Soares, S. Soares, J. Gama, S. Soares, A. Jorge, A. Jorge, P. P. Rodrigues, ... V. S. Costa (Eds.), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2015, Proceedings (pp. 335-347). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9284). Springer Verlag. https://doi.org/10.1007/978-3-319-23528-8_21

Prestwich, Steven D. ; Fajemisin, Adejuyigbe O. ; Climent, Laura et al. / Solving a hard cutting stock problem by machine learning and optimisation. Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2015, Proceedings. editor / Annalisa Appice ; João Gama ; Vitor Santos Costa ; João Gama ; Alípio Jorge ; Annalisa Appice ; Annalisa Appice ; Vitor Santos Costa ; Alípio Jorge ; Annalisa Appice ; Pedro Pereira Rodrigues ; Pedro Pereira Rodrigues ; João Gama ; Vitor Santos Costa ; Soares Soares ; Pedro Pereira Rodrigues ; Soares Soares ; Soares Soares ; João Gama ; Soares Soares ; Alípio Jorge ; Alípio Jorge ; Pedro Pereira Rodrigues ; Vitor Santos Costa. Springer Verlag, 2015. pp. 335-347 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{405997b8f735443a9f0b612a3d6d8957,

title = "Solving a hard cutting stock problem by machine learning and optimisation",

abstract = "We are working with a company on a hard industrial optimisation problem: a version of the well-known Cutting Stock Problem in which a paper mill must cut rolls of paper following certain cutting patterns to meet customer demands. In our problem each roll to be cut may have a different size, the cutting patterns are semi-automated so that we have only indirect control over them via a list of continuous parameters called a request, and there are multiple mills each able to use only one request. We solve the problem using a combination of machine learning and optimisation techniques. First we approximate the distribution of cutting patterns via Monte Carlo simulation. Secondly we cover the distribution by applying a k-medoids algorithm. Thirdly we use the results to build an ILP model which is then solved.",

author = "Prestwich, \{Steven D.\} and Fajemisin, \{Adejuyigbe O.\} and Laura Climent and Barry O{\textquoteright}Sullivan",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2015 ; Conference date: 07-09-2015 Through 11-09-2015",

year = "2015",

doi = "10.1007/978-3-319-23528-8\_21",

language = "English",

isbn = "9783319235271",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "335--347",

editor = "Annalisa Appice and Jo{\~a}o Gama and Costa, \{Vitor Santos\} and Jo{\~a}o Gama and Al{\'i}pio Jorge and Annalisa Appice and Annalisa Appice and Costa, \{Vitor Santos\} and Al{\'i}pio Jorge and Annalisa Appice and Rodrigues, \{Pedro Pereira\} and Rodrigues, \{Pedro Pereira\} and Jo{\~a}o Gama and Costa, \{Vitor Santos\} and Soares Soares and Rodrigues, \{Pedro Pereira\} and Soares Soares and Soares Soares and Jo{\~a}o Gama and Soares Soares and Al{\'i}pio Jorge and Al{\'i}pio Jorge and Rodrigues, \{Pedro Pereira\} and Costa, \{Vitor Santos\}",

booktitle = "Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2015, Proceedings",

address = "Germany",

}

Prestwich, SD, Fajemisin, AO, Climent, L & O’Sullivan, B 2015, Solving a hard cutting stock problem by machine learning and optimisation. in A Appice, J Gama, VS Costa, J Gama, A Jorge, A Appice, A Appice, VS Costa, A Jorge, A Appice, PP Rodrigues, PP Rodrigues, J Gama, VS Costa, S Soares, PP Rodrigues, S Soares, S Soares, J Gama, S Soares, A Jorge, A Jorge, PP Rodrigues & VS Costa (eds), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9284, Springer Verlag, pp. 335-347, European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2015, Porto, Portugal, 7/09/15. https://doi.org/10.1007/978-3-319-23528-8_21

Solving a hard cutting stock problem by machine learning and optimisation. / Prestwich, Steven D.; Fajemisin, Adejuyigbe O.; Climent, Laura et al.
Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2015, Proceedings. ed. / Annalisa Appice; João Gama; Vitor Santos Costa; João Gama; Alípio Jorge; Annalisa Appice; Annalisa Appice; Vitor Santos Costa; Alípio Jorge; Annalisa Appice; Pedro Pereira Rodrigues; Pedro Pereira Rodrigues; João Gama; Vitor Santos Costa; Soares Soares; Pedro Pereira Rodrigues; Soares Soares; Soares Soares; João Gama; Soares Soares; Alípio Jorge; Alípio Jorge; Pedro Pereira Rodrigues; Vitor Santos Costa. Springer Verlag, 2015. p. 335-347 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9284).

Research output: Chapter in Book/Report/Conference proceedings › Conference proceeding › peer-review

TY - GEN

T1 - Solving a hard cutting stock problem by machine learning and optimisation

AU - Prestwich, Steven D.

AU - Fajemisin, Adejuyigbe O.

AU - Climent, Laura

AU - O’Sullivan, Barry

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

N2 - We are working with a company on a hard industrial optimisation problem: a version of the well-known Cutting Stock Problem in which a paper mill must cut rolls of paper following certain cutting patterns to meet customer demands. In our problem each roll to be cut may have a different size, the cutting patterns are semi-automated so that we have only indirect control over them via a list of continuous parameters called a request, and there are multiple mills each able to use only one request. We solve the problem using a combination of machine learning and optimisation techniques. First we approximate the distribution of cutting patterns via Monte Carlo simulation. Secondly we cover the distribution by applying a k-medoids algorithm. Thirdly we use the results to build an ILP model which is then solved.

AB - We are working with a company on a hard industrial optimisation problem: a version of the well-known Cutting Stock Problem in which a paper mill must cut rolls of paper following certain cutting patterns to meet customer demands. In our problem each roll to be cut may have a different size, the cutting patterns are semi-automated so that we have only indirect control over them via a list of continuous parameters called a request, and there are multiple mills each able to use only one request. We solve the problem using a combination of machine learning and optimisation techniques. First we approximate the distribution of cutting patterns via Monte Carlo simulation. Secondly we cover the distribution by applying a k-medoids algorithm. Thirdly we use the results to build an ILP model which is then solved.

UR - https://www.scopus.com/pages/publications/84984621331

U2 - 10.1007/978-3-319-23528-8_21

DO - 10.1007/978-3-319-23528-8_21

M3 - Conference proceeding

AN - SCOPUS:84984621331

SN - 9783319235271

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 335

EP - 347

BT - Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2015, Proceedings

A2 - Appice, Annalisa

A2 - Gama, João

A2 - Costa, Vitor Santos

A2 - Gama, João

A2 - Jorge, Alípio

A2 - Appice, Annalisa

A2 - Costa, Vitor Santos

A2 - Jorge, Alípio

A2 - Appice, Annalisa

A2 - Rodrigues, Pedro Pereira

A2 - Gama, João

A2 - Costa, Vitor Santos

A2 - Soares, Soares

A2 - Rodrigues, Pedro Pereira

A2 - Soares, Soares

A2 - Gama, João

A2 - Soares, Soares

A2 - Jorge, Alípio

A2 - Rodrigues, Pedro Pereira

A2 - Costa, Vitor Santos

PB - Springer Verlag

T2 - European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2015

Y2 - 7 September 2015 through 11 September 2015

ER -

Prestwich SD, Fajemisin AO, Climent L, O’Sullivan B. Solving a hard cutting stock problem by machine learning and optimisation. In Appice A, Gama J, Costa VS, Gama J, Jorge A, Appice A, Appice A, Costa VS, Jorge A, Appice A, Rodrigues PP, Rodrigues PP, Gama J, Costa VS, Soares S, Rodrigues PP, Soares S, Soares S, Gama J, Soares S, Jorge A, Jorge A, Rodrigues PP, Costa VS, editors, Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2015, Proceedings. Springer Verlag. 2015. p. 335-347. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-23528-8_21

Solving a hard cutting stock problem by machine learning and optimisation

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this