Algorithm for solving optimisation problems

In this example we will consider a standard algorithm for solving optimisation problems using the library JuMP.

JuMP.jl is an open source library. This library implements an algebraic modelling language that allows users to formulate and solve a wide range of optimization problems using various solvers.

Library installation

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

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

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

Algorithm for solving the problem

The algorithm for solving an optimisation problem using JuMP involves several systematic steps, from formulating the problem to obtaining and interpreting the results. Here is the standard algorithm for solving the problem:

1. connecting the library JuMP,
2. selecting and connecting the solver library,
3. creating an optimisation problem,
4. declarations of variables,
5. formulation of the target function,
6. formulating the condition,
7. solving the problem,
8. deriving the results,
9. analysing the results.

Task description

In this example we will find the values of the variables x and y that will lead to the smallest possible value of the linear target function: $$F = 13x + 22y \rightarrow min$$ given the following conditions: $$3x + 8y >= 20 Условие 1$$ $$6x + 10y <= 100 Условие 2$$ We will also denote the following bounds on the values of the variables x and y: $$x >= 1$$ $$0 <= y <= 20$$

Problem solving

Connect the library JuMP:

using JuMP;

In this example, we use the HiGHS.jl solver library. Connect the library HiGHS:

using HiGHS;

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

optimization_problem = Model(HiGHS.Optimizer)

A JuMP Model
├ solver: HiGHS
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

Use the macro @variable to define the solver variables. Specify the limits of the values of the variables x and y:

@variable(optimization_problem, x >= 1);
@variable(optimization_problem, 0 <= y <= 20);

Define the target function to be optimised using the macro @objective:

@objective(optimization_problem, Min, 13x + 22y);

Define the first condition for solving the optimisation problem using the macro @constraint:

@constraint(optimization_problem, c1, 3x + 8y >= 20)

$$ 3 x + 8 y \geq 20 $$

Set the second condition for solving the optimisation problem:

@constraint(optimization_problem, c2, 6x + 10y <= 100)

$$ 6 x + 10 y \leq 100 $$

Solve the optimisation problem:

optimize!(optimization_problem)

Running HiGHS 1.5.1 [date: 1970-01-01, git hash: 93f1876e4]
Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
2 rows, 2 cols, 4 nonzeros
2 rows, 2 cols, 4 nonzeros
Presolve : Reductions: rows 2(-0); columns 2(-0); elements 4(-0) - Not reduced
Problem not reduced by presolve: solving the LP
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0     1.3000046544e+01 Pr: 1(17) 0s
          1     5.9750000000e+01 Pr: 0(0) 0s
Model   status      : Optimal
Simplex   iterations: 1
Objective value     :  5.9750000000e+01
HiGHS run time      :          0.00

Output the found optimal values of x and y:

println("Оптимальное значение x: ", value(x))
println("Оптимальное значение y: ", value(y))

Оптимальное значение x: 1.0
Оптимальное значение y: 2.125

Output the status of the solver result:

status = termination_status(optimization_problem)
println("Статус: ", status)

Статус: OPTIMAL

The OPTIMAL status means that the solver has found a globally optimal solution to the problem.

Conclusion

In this example we have described the algorithm for solving a basic optimisation problem using the libraries JuMP and HiGHS. The JuMP library allows you to formulate an optimisation problem, set the conditions and solve it using a user-defined solver. You can read about practical applications of the JuMP library in our course Fundamentals of Optimisation.