Algorithmic solution of the problem of optimal cutting of materials
Introduction
The optimal cutting problem is a classic operational research problem that arises when it is necessary to separate materials of standard sizes into blanks of specified parameters. The goal is to meet the production plan with minimal consumption of raw materials.
This paper examines the mathematical formulation of this problem and an algorithmic approach to its solution based on a combination of linear and integer programming.
This example demonstrates how to solve a cutting problem using linear programming with an integer linear programming routine.
We will connect the necessary libraries.
neededLibs = ["LinearAlgebra", "JuMP", "GLPK", "MathOptInterface", "HiGHS"]
for lib in neededLibs
try
eval(Meta.parse("using $lib"))
catch ex
Pkg.add(lib)
eval(Meta.parse("using $lib"))
end
end
const MOI = MathOptInterface
Task description
The company receives blanks in the form of pipes of standard length. Let's define this length.
длина_заготовки = 40
Then these pipes are cut into blanks of standard sizes suitable for further use. The optimization task is to determine a cutting scheme that will allow you to fulfill a given set of orders using the minimum number of source pipes.
It is necessary to specify the required billet sizes and order volumes for each of these sizes.
список_длин = [8, 12, 16, 20]
требуемое_количество = [90, 111, 55, 30]
число_типов = length(список_длин)
Let's assume that there are no material losses during the cutting process, and the cost of the cutting operation is not taken into account.
The solution algorithm
A cutting pattern is defined as a set of billet lengths that can be obtained from a single pipe when it is cut.
Instead of a complete search of acceptable cutting patterns, an iterative column generation procedure is used. The algorithm implements a two-level optimization scheme:
-
The main task (linear relaxation): Minimizing the number of raw blanks while meeting demand with a combination of current patterns.
-
Auxiliary task (column generation): Search for a new template with a negative present value calculated through dual variables of the main task. The negativity criterion provides an improvement in the objective function.
The iterative process continues until the improving patterns are exhausted, which corresponds to the optimality condition in the simplex method. The resulting linear relaxation solution serves as a lower bound.
The final stage: In order to obtain an integer solution, the problem is solved repeatedly over a generated set of templates with the requirement of an integer number of variables. This approach combines the efficiency of linear programming with the precision of integer methods.
Setting the task
In this problem statement, the sample is a vector of integers, the elements of which indicate the number of blanks of each standard size from the list of lengths. To store templates, a matrix is organized with the name образцы, where each column corresponds to one pattern.
The first template (the first column) corresponds to two blanks with a length of 8 and one blank with a length of 20. The second template is for two blanks with a length of 12 and one blank with a length of 16. Both templates are acceptable, since the total length of all blanks in each of them does not exceed длина_заготовки = 40.
In this formulation, if x — this is a column vector of integers indicating how many times each sample is used, then the product gives a column vector with the total number of blanks of each type. The demand satisfaction condition is written as образцы*x >= требуемое_количество.
To form the initial set of acceptable cutting patterns, the simplest options are used, containing blanks of only one standard size. Each such sample includes the maximum possible number of blanks of a given size.
образцы = Diagonal(floor.(Int, длина_заготовки ./ список_длин))
число_образцов = size(образцы, 2)
The goal of the subproblem is to minimize a function that depends only on Lagrange multipliers. The variables are non—negative integers (the number of blanks of each type). The only limitation is that the total length of the blanks in the template must not exceed the length of the original blank (pipe).
подзадача = Model(GLPK.Optimizer)
@variable(подзадача, разрезы[1:число_типов] >= 0, Int)
@constraint(подзадача, dot(список_длин, разрезы) <= длина_заготовки)
Initialize the variables for the loop.
приведённая_стоимость = -Inf
допуск_приведённой_стоимости = -0.0001
статус_выхода = MOI.OPTIMAL
Let's start the cycle.
while приведённая_стоимость < допуск_приведённой_стоимости && статус_выхода == MOI.OPTIMAL
основная_задача = Model(HiGHS.Optimizer)
set_silent(основная_задача)
@variable(основная_задача, x[1:число_образцов] >= 0)
@objective(основная_задача, Min, sum(x))
@constraint(основная_задача, Спрос, образцы * x .>= требуемое_количество)
optimize!(основная_задача)
статус_выхода = termination_status(основная_задача)
количество_заготовок = round(objective_value(основная_задача), digits = 2)
if статус_выхода == MOI.OPTIMAL
println("Is used ", количество_заготовок, " blanks")
двойственные_переменные = dual.(основная_задача[:Спрос])
@objective(подзадача, Min, 1.0 - dot(двойственные_переменные, разрезы))
set_silent(подзадача)
optimize!(подзадача)
приведённая_стоимость = objective_value(подзадача)
статус_подзадачи = termination_status(подзадача)
новый_образец = round.(Int, value.(разрезы))
if статус_подзадачи == MOI.OPTIMAL && приведённая_стоимость < допуск_приведённой_стоимости
образцы = [образцы новый_образец]
число_образцов = число_образцов + 1
end
else
break
end
end
At this stage, a solution to the linear programming problem has been obtained. To complete the calculations, it is necessary to solve the problem again with the final set of templates, changing the type of the solution variable. to an integer. It is also required to calculate the amount of waste — the amount of unused material for each sample and for the entire task as a whole.
if статус_выхода != MOI.OPTIMAL
println("Error in the column generation phase")
else
целочисленная_задача = Model(HiGHS.Optimizer)
set_silent(целочисленная_задача)
@variable(целочисленная_задача, x_целое[1:число_образцов] >= 0, Int)
@objective(целочисленная_задача, Min, sum(x_целое))
@constraint(целочисленная_задача, Спрос, образцы * x_целое .>= требуемое_количество)
optimize!(целочисленная_задача)
статус_целое = termination_status(целочисленная_задача)
if статус_целое == MOI.OPTIMAL
значения_x = value.(x_целое)
использовано_заготовок = sum(значения_x)
println("\nОптимальное решение использует ", использовано_заготовок, " blanks")
общие_отходы = sum((образцы * значения_x - требуемое_количество) .* список_длин)
for j in 1:length(значения_x)
if значения_x[j] > 0
println("\nРаскроить ", значения_x[j], " blanks according to the sample ", j)
for w in 1:size(образцы, 1)
if образцы[w, j] > 0
println(" ", образцы[w, j], " length details ", список_длин[w])
end
end
отходы_образца = длина_заготовки - dot(образцы[:, j], список_длин)
общие_отходы += отходы_образца
println(" Waste of this sample: ", отходы_образца)
end
end
println("General waste: ", общие_отходы, ".")
else
println("Error in the final optimization")
end
end
println("\nТаблица результатов:")
println("Длина\tТребуется\tПроизведено")
println("------\t---------\t-----------")
произведено = round.(Int, образцы * значения_x)
for i in 1:length(список_длин)
println(список_длин[i], "\t", требуемое_количество[i], "\t\t", произведено[i])
end
Conclusion
This example shows the complete algorithmic cycle of solving the optimal cutting problem. The effectiveness of an iterative approach using linear relaxation to find improving patterns and subsequent integer programming to obtain a final plan is demonstrated.
The resulting solution allows you to determine the minimum amount of required material and analyze the structure of production waste. The presented method has practical value for optimizing technological processes in various industries.