Short description
The cutting-stock problem is an optimization problem, or more specifically, an integer linear programming problem.
It is a quite common problem in the industry and it’s main use is to find the best way to cut a stock piece (i.e. paper, glass) in smaller pieces as requested, minimizing the waste.
Here i’ll briefly explain a simplified version of the bidimensional problem which involves only guillotine cuts (from one edge to the opposite).
As explained in A Linear Programming Approach to the Cutting-Stock Problem (by P. C. Gilmore and R. E. Gomory) this problem can be solved as a 2-stage problem where each stage involves solving a mono-dimensional problem using a Master-Slave pattern and a column generation technique.
My implementation
My implementation is based on the ideas presented in that article. The source code, written in C++, is released under the LGPL license and is provided “as-is” without any implicit or explicit warranty.
To compile it (using the Makefile provided) you need:
- SoPlex, an implementation of the revised simplex algorithm
- SCIP, a framework for Constraint Integer Programming
The Makefile needs to be edited, adding the path to the actual SCIP library after you have installed it.
Source code (.zip file, 19.7KB)
Problem and code explanation (in italian, .pdf 339KB)
