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.
# import Pkg
# Pkg.add(["LinearAlgebra", "JuMP", "GLPK", "MathOptInterface", "HiGHS"])
using LinearAlgebra, JuMP, GLPK, MathOptInterface, HiGHS
const MOI = MathOptInterface
Task description
The company receives blanks in the form of pipes of standard length. Let's define this length.
boot 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.
list_ length = [8, 12, 16, 20]
required quantity = [90, 111, 55, 30]
number of types = length(list of lengths)
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 improvement 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: 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.
samples = Diagonal(floor.(Int, the length of the preparation ./ list_line))
number_images = size(samples, 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).
subtask = Model(GLPK.Optimizer)
@variable(subtask, sections[1:number of types] >= 0, Int)
@constraint(subtask, dot(list of lengths, sections) <= length of the preparation)
Initialize the variables for the loop.
reduced cost = -Inf
tolerance of reduced cost = -0.0001
exit status_ = MOI.OPTIMAL
Let's start the cycle.
while reduced cost < tolerance of reduced cost && exit status == MOI.OPTIMAL
main_problem = Model(HiGHS.Optimizer)
set_silent(main_problem)
@variable(main_problem, x[1:number of samples] >= 0)
@objective(main_problem, Min, sum(x))
@constraint(main_problem, Demand, samples * x .>= required quantity)
optimize!(main_problem)
exit status_status = termination_status(main_stask)
number of orders = round(objective_value(main_problem), digits = 2)
if exit status_ == MOI.OPTIMAL
println("Is used ", количество_заготовок, " blanks")
dual variables = dual.(main_problem[:Demand])
@objective(subtask, Min, 1.0 - dot(dual variables, sections))
set_silent(subtask)
optimize!(subtask)
reduced value = objective_value(subtask)
subtask status_ = termination_status(subtask)
new_image = round.(Int, value.(sections))
if task status_ == MOI.OPTIMAL && reduced cost < tolerance of reduced cost
samples = [new_image samples]
number_images = number_images + 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 the exit status_ != MOI.OPTIMAL
println("Error in the column generation phase")
else
integer task = Model(HiGHS.Optimizer)
set_silent(integer_problem)
@variable(integer problem, x_ integer[1:number_images] >= 0, Int)
@objective(integer problem, Min, sum(x_ integer))
@constraint(integer task, Demand, samples * x_ integer .>= required quantity)
optimize!(integer_problem)
status_ integer = termination_status(integer task)
if status_ integer == MOI.OPTIMAL
value_x = value.(x_ integer)
used_references = sum(values of_x)
println("\The optimal solution uses ", использовано_заготовок, " blanks")
total waste = sum((samples * values of x - quantity required) .* list_ length)
for j in 1:length(values of x)
if the values of_x[j] > 0
println("\pRaskroite ", значения_x[j], " blanks according to the sample ", j)
for w in 1:size(samples, 1)
if samples[w, j] > 0
println(" ", образцы[w, j], " length details ", список_длин[w])
end
end
sample waste = sample length - dot(samples[:, j], length list)
general waste += sample waste
println(" Waste of this sample: ", отходы_образца)
end
end
println("General waste: ", общие_отходы, ".")
else
println("Error in the final optimization")
end
end
println("\Results table:")
println("Length\T required\T Produced")
println("------\t---------\t-----------")
produced = round.(Int, samples * value_x)
for i in 1:length(list_length)
println(список_длин[i], "\t", требуемое_количество[i], "\t\t", произведено[i])
end
Conclusion
This example shows a complete algorithmic cycle for 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.