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.
Cite
Text
Prestwich et al. "Solving a Hard Cutting Stock Problem by Machine Learning and Optimisation." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2015. doi:10.1007/978-3-319-23528-8_21Markdown
[Prestwich et al. "Solving a Hard Cutting Stock Problem by Machine Learning and Optimisation." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2015.](https://mlanthology.org/ecmlpkdd/2015/prestwich2015ecmlpkdd-solving/) doi:10.1007/978-3-319-23528-8_21BibTeX
@inproceedings{prestwich2015ecmlpkdd-solving,
title = {{Solving a Hard Cutting Stock Problem by Machine Learning and Optimisation}},
author = {Prestwich, Steven D. and Fajemisin, Adejuyigbe O. and Climent, Laura and O'Sullivan, Barry},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2015},
pages = {335-347},
doi = {10.1007/978-3-319-23528-8_21},
url = {https://mlanthology.org/ecmlpkdd/2015/prestwich2015ecmlpkdd-solving/}
}