Engee documentation
Notebook

Solutions to problems of mixed integer linear programming

This example shows how to solve the problem of mixed integer linear programming (English Mixed Integer Linear Programming, MILP). Here are the typical steps to formulate a problem using a problem-oriented approach.

We will use the functions of the [JuMP.jl] library(https://github.com/jump-dev/JuMP .jl) for the formulation of the optimization problem and the linear optimization library GLPK.jl.

Installing Libraries

If the latest version of the package is not installed in your environment JuMP, uncomment and run the cell below:

In [ ]: 
Pkg.add(["GLPK", "JuMP"])
In [ ]: 
#Pkg.add("JuMP");

To launch a new version of the library after the installation is complete, click on the "Personal Account" button:

Screenshot_20240710_134852.png Then click on the "Stop" button: Screenshot_20240710_2.png

Restart the session by clicking the "Start Engee" button:

Screenshot_20240710_135431.png

Task description

You need to mix steels with different chemical compositions to produce 25 tons of steel with a specific chemical composition. The result should be steel containing 5% carbon and 5% molybdenum of the total weight, which means 1.25 tons of carbon and 1.25 tons of molybdenum.

The purpose of the optimization task is to minimize the cost of mixing steel.

Four different steel bars are available for purchase. However, you can only buy one ingot of each type.

Ingot Weight in tons % carbon % molybdenum Cost per ton
1 5 5 3 $350
2 3 4 3 $330
3 4 5 4 $310
4 6 3 4 $280

Three grades of alloy steel and one grade of scrap steel are also available for sale. Alloy steels and scrap can be purchased in fractional quantities.

Alloy % carbon % Molybdenum Cost per ton
1 8 6 $500
2 7 7 $450
3 6 8 $400
Лом 3 9 $100

Connecting libraries

Connect the library JuMP:

In [ ]: 
using JuMP;

Connect the solver library GLPK:

In [ ]: 
using GLPK;

Creating an optimization task

Create an optimization task using the function Model() and specify the name of the solver in parentheses.:

In [ ]: 
steel_prob = Model(GLPK.Optimizer)
Out[0]:
A JuMP Model
├ solver: GLPK
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

Create a variable ingots, containing four values (according to the number of ingots available for purchase). Since ingots cannot be purchased in fractional quantities, specify the type of variable. Int. The lower bound for all variables will be 0, because we cannot purchase a negative quantity. Each of the bars is available in a single instance, so specify an upper bound of 1 for this variable.

In [ ]: 
@variable(steel_prob, ingots[1:4], Int; lower_bound = 0, upper_bound = 1);

Create a variable alloys, containing three values (according to the number of alloys available for purchase). We will separate the scrap steel into a separate variable. Since alloys can be purchased in fractional quantities, it is not necessary to specify the type of variable.

In [ ]: 
@variable(steel_prob, alloys[1:3], lower_bound = 0);

Create a variable scrap for scrap steel. Since scrap can be purchased in fractional quantities, you do not need to specify the type of variable.

In [ ]: 
@variable(steel_prob, scrap, lower_bound = 0);

Since the weight of each of the bars is different, to calculate the cost of purchasing the bars, you must first create a variable weightIngots. Calculate the costs for each of the components and create a variable cost, containing the total cost of purchasing components. As part of our task, we will find the minimum value of this variable.

In [ ]: 
weightIngots = [5,3,4,6];
costIngots = weightIngots.*[350,330,310,280];
costAlloys = [500,450,400];
costScrap = 100;
cost = sum(costIngots.*ingots) + sum(costAlloys.*alloys) + sum(costScrap*scrap)
Out[0]:
$ 1750 ingots_{1} + 990 ingots_{2} + 1240 ingots_{3} + 1680 ingots_{4} + 500 alloys_{1} + 450 alloys_{2} + 400 alloys_{3} + 100 scrap $

Create an objective function to minimize costs to solve our optimization problem.:

In [ ]: 
@objective(steel_prob, Min, cost)
Out[0]:
$ 1750 ingots_{1} + 990 ingots_{2} + 1240 ingots_{3} + 1680 ingots_{4} + 500 alloys_{1} + 450 alloys_{2} + 400 alloys_{3} + 100 scrap $

Create a variable totalWeight, containing the total weight of all components:

In [ ]: 
totalWeight = sum(weightIngots.*ingots) + sum(alloys) + scrap
Out[0]:
$ 5 ingots_{1} + 3 ingots_{2} + 4 ingots_{3} + 6 ingots_{4} + alloys_{1} + alloys_{2} + alloys_{3} + scrap $

Calculate the total mass of carbon in steel:

In [ ]: 
carbonIngots = [5,4,5,3]/100;
carbonAlloys = [8,7,6]/100;
carbonScrap = 3/100;
totalCarbon = sum((weightIngots.*carbonIngots).*ingots) + sum(carbonAlloys.*alloys) + sum(carbonScrap.*scrap)
Out[0]:
$ 0.25 ingots_{1} + 0.12 ingots_{2} + 0.2 ingots_{3} + 0.18 ingots_{4} + 0.08 alloys_{1} + 0.07 alloys_{2} + 0.06 alloys_{3} + 0.03 scrap $

Calculate the total mass of molybdenum in steel:

In [ ]: 
molybIngots = [3,3,4,4]/100;
molybAlloys = [6,7,8]/100;
molybScrap = 9/100;
totalMolyb = sum((weightIngots.*molybIngots).*ingots) + sum(molybAlloys.*alloys) + sum(molybScrap.*scrap)
Out[0]:
$ 0.15 ingots_{1} + 0.09 ingots_{2} + 0.16 ingots_{3} + 0.24 ingots_{4} + 0.06 alloys_{1} + 0.07 alloys_{2} + 0.08 alloys_{3} + 0.09 scrap $

Formulation of conditions

Set the first condition for solving the optimization problem, that the total weight of the steel obtained should be 25 tons.:

In [ ]: 
@constraint(steel_prob, C1, totalWeight == 25)
Out[0]:
$$ 5 ingots_{1} + 3 ingots_{2} + 4 ingots_{3} + 6 ingots_{4} + alloys_{1} + alloys_{2} + alloys_{3} + scrap = 25 $$

Set the second condition for solving the optimization problem, that the total carbon weight in the resulting steel should be 1.25 tons.:

In [ ]: 
@constraint(steel_prob, C2, totalCarbon == 1.25)
Out[0]:
$$ 0.25 ingots_{1} + 0.12 ingots_{2} + 0.2 ingots_{3} + 0.18 ingots_{4} + 0.08 alloys_{1} + 0.07 alloys_{2} + 0.06 alloys_{3} + 0.03 scrap = 1.25 $$

Set the third condition for solving the optimization problem, that the total weight of molybdenum in the resulting steel should be 1.25 tons.:

In [ ]: 
@constraint(steel_prob, C3, totalMolyb == 1.25)
Out[0]:
$$ 0.15 ingots_{1} + 0.09 ingots_{2} + 0.16 ingots_{3} + 0.24 ingots_{4} + 0.06 alloys_{1} + 0.07 alloys_{2} + 0.08 alloys_{3} + 0.09 scrap = 1.25 $$

Problem solving

Solve the optimization problem:

In [ ]: 
optimize!(steel_prob)

Check if an optimal solution has been found.:

In [ ]: 
if !is_solved_and_feasible(steel_prob)
    error("Solver did not find an optimal solution")
end

Save the values of interest in variables. You can use the function round to round up overly precise values.

In [ ]: 
ingots_value = value.(ingots);
alloys_value = round.(value.(alloys); digits = 3);
scrap_value = round(value.(scrap); digits = 3);
fval = objective_value(steel_prob);

Output the optimization results:

In [ ]: 
println("Ingots: ", ingots_value)
println("Alloys: ", alloys_value)
println("Scrap: ", scrap_value)
println("Objective Value: ", fval)

Ingots: [1.0, 1.0, 0.0, 1.0]
Alloys: [7.25, 0.0, 0.25]
Scrap: 3.5
Objective Value: 8495.0

The optimal purchase price is $8,495. Thus, it is necessary to purchase ingots 1, 2 and 4, but not 3. And also to purchase 7.25 tons of alloy 1, 0.25 tons of alloy 3 and 3.5 tons of steel scrap.

Conclusion

In this example, we solved the problem of mixed integer linear programming and found the optimal set and number of components to produce 25 tons of steel with the required chemical composition at the lowest price.