Solutions of mixed integer linear programming problems

This example shows how to solve a Mixed Integer Linear Programming (MILP) problem. Typical steps of problem formulation using a problem-oriented approach are given here.

We will use the functions of the library JuMP.jl to formulate the optimisation problem and the linear optimisation library GLPK.jl.

Installing the libraries

If your environment does not have the latest version of the JuMP package installed , uncomment and run the box below:

Pkg.add(["GLPK", "JuMP"])

#Pkg.add("JuMP");

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

Then click on the "Stop" button:

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

Task Description

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

The objective of the optimisation problem is to minimise the cost of mixing steel.

Four different steel ingots are available for purchase. You can only buy one ingot of each type.

| ingot | Weight in tonnes | % carbon | % molybdenum | Cost per tonne | | ----------- | ----------- | ----------- | ----------- | ----------- | | 1 | 5 | 5 | 5 | 3 | $350 | | 2 | 3 | 4 | 3 | $330 | | 3 | 4 | 4 | 5 | 4 | $310 | | 4 | 6 | 3 | 4 | $280 |

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

| Alloy | % carbon | % molybdenum | Cost per tonne | | ----------- | ----------- | ----------- | ----------- | | 1 | 8 | 8 | 6 | $500 | | 2 | 7 | 7 | $450 | | 3 | 6 | 8 | $400 | | Лом | 3 | 9 | $| 100 |

Connecting libraries

Connect the library JuMP:

using JuMP;

Connect the solver library GLPK:

using GLPK;

Creating an optimisation problem

Create an optimisation problem using the function Model() and specify the name of the solver in brackets:

steel_prob = Model(GLPK.Optimizer)

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 purchasing). Since ingots cannot be purchased in fractional amounts, specify the variable type Int. The lower bound for all variables will be 0, because we cannot procure a negative quantity. Each ingot is available in a single copy, so for this variable specify an upper bound of 1.

@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 steel scrap into a separate variable. Since alloys can be purchased in fractional quantities, it is not necessary to specify the variable type.

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

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

@variable(steel_prob, scrap, lower_bound = 0);

Since the weight of each ingot is different, you must first create the variable weightIngots to calculate the cost of purchasing ingots. Calculate the costs for each of the components and create the variable cost, which contains the total cost of purchasing the components. As part of the solution to our problem, we will find the minimum value of this variable.

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)

$ 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 target function to minimise the cost to solve our optimisation problem:

@objective(steel_prob, Min, cost)

$ 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:

totalWeight = sum(weightIngots.*ingots) + sum(alloys) + scrap

$ 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 the steel:

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)

$ 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 the steel:

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)

$ 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 obtained steel should be 25 tonnes:

@constraint(steel_prob, C1, totalWeight == 25)

$$ 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 the solution of the optimization problem that the total weight of carbon in the resulting steel should be 1.25 tonnes:

@constraint(steel_prob, C2, totalCarbon == 1.25)

$$ 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 the solution of the optimization problem that the total weight of molybdenum in the resulting steel should be 1.25 tonnes:

@constraint(steel_prob, C3, totalMolyb == 1.25)

$$ 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 $$

Solution of the problem

Solve the optimisation problem:

optimize!(steel_prob)

Check whether an optimal solution has been found:

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 off excessively accurate values.

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 results of the optimisation:

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 $8495. Thus, ingots 1, 2 and 4 should be purchased, but not 3. Also purchase 7.25 tonnes of alloy 1, 0.25 tonnes of alloy 3 and 3.5 tonnes of steel scrap.

Conclusion

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