# Simple multi-objective examples

This tutorial contains a number of examples of multi-objective programs from the literature.

## Required packages

This tutorial requires the following packages:

using JuMP
import HiGHS
import MultiObjectiveAlgorithms as MOA

## Bi-objective linear problem

This is example is taken from Example 6.3 (from Steuer, 1985), page 154 of Multicriteria Optimization (2nd ed), M. Ehrgott, Springer 2005. The code was adapted from an example in vOptGeneric by @xgandibleux.

model = Model()
set_silent(model)
@variable(model, x1 >= 0)
@variable(model, 0 <= x2 <= 3)
@objective(model, Min, [3x1 + x2, -x1 - 2x2])
@constraint(model, 3x1 - x2 <= 6)
set_optimizer(model, () -> MOA.Optimizer(HiGHS.Optimizer))
set_attribute(
model,
MOA.Algorithm(),
MOA.Lexicographic(; all_permutations = true),
)
optimize!(model)
solution_summary(model)
* Solver : MOA[algorithm=MultiObjectiveAlgorithms.Lexicographic, optimizer=HiGHS]

* Status
Result count       : 2
Termination status : OPTIMAL
Message from the solver:
"Solve complete. Found 2 solution(s)"

* Candidate solution (result #1)
Primal status      : FEASIBLE_POINT
Dual status        : NO_SOLUTION
Objective value    : [0.00000e+00,0.00000e+00]
Objective bound    : [0.00000e+00,-9.00000e+00]
Relative gap       : Inf
Dual objective value : -9.00000e+00

* Work counters
Solve time (sec)   : 1.06978e-03
Simplex iterations : 1
Barrier iterations : 0
Node count         : -1

for i in 1:result_count(model)
print(i, ": z = ", round.(Int, objective_value(model; result = i)), " | ")
println("x = ", value.([x1, x2]; result = i))
end
1: z = [0, 0] | x = [0.0, -0.0]
2: z = [12, -9] | x = [3.0, 3.0]

## Bi-objective linear assignment problem

This is example is taken from Example 9.38 (from Ulungu and Teghem, 1994), page 255 of Multicriteria Optimization (2nd ed), M. Ehrgott, Springer 2005. The code was adapted from an example in vOptGeneric by @xgandibleux.

C1 = [5 1 4 7; 6 2 2 6; 2 8 4 4; 3 5 7 1]
C2 = [3 6 4 2; 1 3 8 3; 5 2 2 3; 4 2 3 5]
n = size(C2, 1)
model = Model()
set_silent(model)
@variable(model, x[1:n, 1:n], Bin)
@objective(model, Min, [sum(C1 .* x), sum(C2 .* x)])
@constraint(model, [i = 1:n], sum(x[i, :]) == 1)
@constraint(model, [j = 1:n], sum(x[:, j]) == 1)
set_optimizer(model, () -> MOA.Optimizer(HiGHS.Optimizer))
set_attribute(model, MOA.Algorithm(), MOA.EpsilonConstraint())
optimize!(model)
solution_summary(model)
* Solver : MOA[algorithm=MultiObjectiveAlgorithms.EpsilonConstraint, optimizer=HiGHS]

* Status
Result count       : 6
Termination status : OPTIMAL
Message from the solver:
"Solve complete. Found 6 solution(s)"

* Candidate solution (result #1)
Primal status      : FEASIBLE_POINT
Dual status        : NO_SOLUTION
Objective value    : [6.00000e+00,2.40000e+01]
Objective bound    : [6.00000e+00,7.00000e+00]
Relative gap       : 0.00000e+00

* Work counters
Solve time (sec)   : 1.00813e-02
Simplex iterations : -1
Barrier iterations : -1
Node count         : 1

for i in 1:result_count(model)
print(i, ": z = ", round.(Int, objective_value(model; result = i)), " | ")
println("x = ", round.(Int, value.(x; result = i)))
end
1: z = [6, 24] | x = [0 1 0 0; 0 0 1 0; 1 0 0 0; 0 0 0 1]
2: z = [9, 17] | x = [0 0 1 0; 0 1 0 0; 1 0 0 0; 0 0 0 1]
3: z = [12, 13] | x = [1 0 0 0; 0 1 0 0; 0 0 1 0; 0 0 0 1]
4: z = [16, 11] | x = [0 0 0 1; 0 1 0 0; 0 0 1 0; 1 0 0 0]
5: z = [19, 10] | x = [0 0 1 0; 1 0 0 0; 0 0 0 1; 0 1 0 0]
6: z = [22, 7] | x = [0 0 0 1; 1 0 0 0; 0 0 1 0; 0 1 0 0]

## Bi-objective shortest path problem

This is example is taken from Exercise 9.5 page 269 of Multicriteria Optimization (2nd edition), M. Ehrgott, Springer 2005. The code was adapted from an example in vOptGeneric by @xgandibleux.

M = 50
C1 = [
M 4 5 M M M
M M 2 1 2 7
M M M 5 2 M
M M 5 M M 3
M M M M M 4
M M M M M M
]
C2 = [
M 3 1 M M M
M M 1 4 2 2
M M M 1 7 M
M M 1 M M 2
M M M M M 2
M M M M M M
]
n = size(C2, 1)
model = Model()
set_silent(model)
@variable(model, x[1:n, 1:n], Bin)
@objective(model, Min, [sum(C1 .* x), sum(C2 .* x)])
@constraint(model, sum(x[1, :]) == 1)
@constraint(model, sum(x[:, n]) == 1)
@constraint(model, [i = 2:n-1], sum(x[i, :]) - sum(x[:, i]) == 0)
set_optimizer(model, () -> MOA.Optimizer(HiGHS.Optimizer))
set_attribute(model, MOA.Algorithm(), MOA.EpsilonConstraint())
optimize!(model)
solution_summary(model)
* Solver : MOA[algorithm=MultiObjectiveAlgorithms.EpsilonConstraint, optimizer=HiGHS]

* Status
Result count       : 4
Termination status : OPTIMAL
Message from the solver:
"Solve complete. Found 4 solution(s)"

* Candidate solution (result #1)
Primal status      : FEASIBLE_POINT
Dual status        : NO_SOLUTION
Objective value    : [8.00000e+00,9.00000e+00]
Objective bound    : [8.00000e+00,4.00000e+00]
Relative gap       : 0.00000e+00

* Work counters
Solve time (sec)   : 5.61881e-03
Simplex iterations : -1
Barrier iterations : -1
Node count         : 1

for i in 1:result_count(model)
print(i, ": z = ", round.(Int, objective_value(model; result = i)), " | ")
X = round.(Int, value.(x; result = i))
print("Path:")
for ind in findall(val -> val ≈ 1, X)
i, j = ind.I
print(" $i->$j")
end
println()
end
1: z = [8, 9] | Path: 1->2 2->4 4->6
2: z = [10, 7] | Path: 1->2 2->5 5->6
3: z = [11, 5] | Path: 1->2 2->6
4: z = [13, 4] | Path: 1->3 3->4 4->6

Tip