Cutting and packing problems

Cutting and packing problems are important problems that occur in practice. They are characterized by the existence of a set of production orders for smaller items, which must be cut from larger objects or packed in those. In general, the main objective is to minimize trim loss of material, which is realted to the minimization of production costs.

Among the cutting problems, we highlight the cutting of rolls in the paper industry, cutting of steel bars in construction, cutting of pieces of wood, glass and fabric, and cutting of stones such as granite. In these problems, the main objective is to specify how to cut smaller pieces from larger pieces in stock so as to minimize trim loss.

In turn, the packing problems deal with the fitting of smaller parts in larger pieces, called bins, in order to minimize the number of bins used or maximize the use of space in the bins. This type of problem occurs for example in the assembly of pallets and in the cargo loading in trucks.

Cutting and packing problems are hard combinatorial optimization. (Also called NP-hard problems according to the theory computational complexity.) Such problems are characterized by exponential growth in the number of possible solutions, so that it is virtually impossible to find good solutions to real large-scale problems by simple trial and error. However, it is possible to obtain good solutions or even optimal solutions through algorithms that intelligently exploit the mathematical structure of the problem.

In this project, a particular class of cutting problems is investigated in which decisions on cutting are integrated with production order scheduling. Case studies are mainly in the domain of civil construction, with a particular emphasis on the problems that arise in the production of precast beams, cutting of stones such as granite, and cutting of metal bars.

The main technologies used in this project are the solver IBM CPLEX, and the programming languages Python and Julia.