Multi-objective: have no optimal solutions after changing the priority of the objectives

Specific Domains Optimization (Mathematical)
, ,
1

Hi,
I have a 4-objective optimization model using Gurobi, and there was the optimal solution when I set the poriority of one order (e.g. [4,3,2,1]). but when the priority changes ((e.g. [2,3,4,1])), the optimal solution cannot be obtained.

Below is the simple code I set and ran. Is there any wrong with this set?

using JuMP, Gurobi
import MultiObjectiveAlgorithms as MOA

model = Model()
@variable(…)
@constraint(…)
@expression(model,f1,…)
@expression(model,f2,…)
@expression(model,f3,…)
@expression(model,f4,…)
@objective(model,Min,[f1, f2, f3, f4])

set_optimizer(model, () -> MOA.Optimizer(Gurobi.Optimizer))
set_attribute(model, MOA.Algorithm(), MOA.Hierarchical())

set_attribute(model, MOA.ObjectivePriority(1), 4)  
set_attribute(model, MOA.ObjectivePriority(2), 3)
set_attribute(model, MOA.ObjectivePriority(3), 2)
set_attribute(model, MOA.ObjectivePriority(4), 1)

optimize!(model)

And below is the output when there was no optimal solution.

Optimize a model with 2054 rows, 13260 columns and 46184 nonzeros      
Coefficient statistics:
  Matrix range     [1e+00, 5e+10]
  Objective range  [1e+00, 5e+06]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 1e+11]
Warning: Model contains large matrix coefficients
Warning: Model contains large rhs
         Consider reformulating model or setting NumericFocus parameter         to avoid numerical issues.
LP warm-start: use basis
Warning: Markowitz tolerance tightened to 0.03125
Iteration    Objective       Primal Inf.    Dual Inf.      Time        
       0   -1.6384000e+34   7.420476e+36   1.638400e+04      0s        
       1    9.7566885e+07   0.000000e+00   0.000000e+00      0s        

Solved in 1 iterations and 0.02 seconds (0.00 work units)
Optimal objective  9.756688463e+07

User-callback calls 27, time in user-callback 0.00 sec
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (win64 - Windows 10.0 
(19045.2))

CPU model: Intel(R) Xeon(R) CPU E5-1620 v4 @ 3.50GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 4 threads

Optimize a model with 2055 rows, 13260 columns and 59444 nonzeros      
Coefficient statistics:
  Matrix range     [1e+00, 5e+10]
  Objective range  [4e+05, 1e+13]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 1e+11]
Warning: Model contains large matrix coefficients
Warning: Model contains large objective coefficients
Warning: Model contains large rhs
         Consider reformulating model or setting NumericFocus parameter         to avoid numerical issues.
LP warm-start: use basis
Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0   -1.2542692e+40   4.531669e+33   1.254269e+10      0s        

Solved in 1850 iterations and 0.09 seconds (0.11 work units)
Infeasible model

User-callback calls 1879, time in user-callback 0.00 sec

Thanks.

2

Hi @Shaolin, thanks for posting the question over here.

Can you include a reproducible example?

When I use the data you sent me, I get:

julia> solution_summary(model)
* Solver : MOA[algorithm=MultiObjectiveAlgorithms.Hierarchical, optimizer=Gurobi]

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

* Candidate solution (result #1)
  Primal status      : FEASIBLE_POINT
  Dual status        : NO_SOLUTION
  Objective value    : [-3.15912e+10,1.04274e+14,1.17896e+08,3.32927e+07]
  Objective bound    : [-3.15912e+10,1.04274e+14,1.07637e+08,3.06829e+07]
  Dual objective value : 3.06829e+07

* Work counters
  Solve time (sec)   : 2.49966e+00
  Barrier iterations : 0
  Node count         : 0

Without looking too deeply, the biggest issue appears to be:

Try to rescale your model so that the coefficients are 1e6 or smaller. For example, the Water_min objective has a value of 1e14. Use a different unit, like mega-liters instead of liters.

3

Hi @odow , thank you for your comments.
I changed the units and no longer get the warning. But still can’t find the optimal solution when the priority changes, like:

set_attribute(model, MOA.ObjectivePriority(1), 2) 
set_attribute(model, MOA.ObjectivePriority(2), 3)
set_attribute(model, MOA.ObjectivePriority(3), 4)
set_attribute(model, MOA.ObjectivePriority(4), 1)

And here the clean code and data.

code&data

4

You really need to change the units on the constraints, not just by re-scaling the objective.

Gurobi has a good set of articles on numerical issues:

Here’s how I’d write your model:

using JuMP
import CSV
import DataFrames
import Gurobi
import MultiObjectiveAlgorithms as MOA

data = CSV.read("data.csv", DataFrames.DataFrame)
n = nrow(data)

PI = [623.75,357.37,227.91,701.06,197.26,4527.03,293.04,-16.82,479.54,923.48,426.19,282.5566667,132.8]
WI = [206,1160,3016,1726,1598,365,1010,1876,230,302,2871,1433,2340]
FI = [12.32429686,5.759303271,1.486327048,3.205533846,5.881588758,9.323822963,5.312003246,3.847869561,6.821161941,4.193942646,3.57359744,5.650965092,7.696433774]
GI = [1.19,0.74,0.35,0.63,0.61,0.94,6.84,0.99,1.27,1.33,1.28,0.28,0.61]
XI = [11888.218490594381, 12414.226607455736, 533.9122822424877, 183.48414095294515, 3650.7712263207227, 104594.74027733805, 19355.056903806755, 1133.9787794219592, 10.221437080474042, 27586.665274751886, 2765.6134903319276, 2424.772619481199, 26.692913728869367]

for j in 1:13
    data[:, "Y$j"] ./= 1_000
end
data[!, "Cr"] = data[:,"Cr"] ./ 1_000_000
XI ./= 1_000

model = Model()
@variable(model, 0 <= X[i in 1:n, j in 1:13] <= ceil(data[i, "R$j"]))
@constraints(model, begin
    [i in 1:n], sum(X[i, :]) <= 1
    [i in 1:n], sum(X[i,j]*data[i,"Y$j"]*WI[j] for j in 1:13) <= data[i, "w2020"]
    X * FI .<= data[:, "f2020"]
    X * GI .<= data[:, "g2020"]
    X * PI .>= data[:, "p2020"]
    [j in 1:13], sum(data[i,"Y$j"]*X[i,j]*data[i,"Cr"] for i in 1:n) >= XI[j]
end)
@expressions(model, begin
    W_min, sum(sum(X[i,j] * data[i,"Y$j"] * WI[j] for j in 1:13) * data[i,"Cr"] for i in 1:n)
    P_max, data[:,"Cr"]' * X * PI
    F_min, data[:,"Cr"]' * X * FI
    G_min, data[:,"Cr"]' * X * GI
end)
@objective(model, Min, [-P_max, W_min, F_min, G_min])
set_optimizer(model, () -> MOA.Optimizer(Gurobi.Optimizer))
set_attribute(model, MOA.Algorithm(), MOA.Hierarchical())
set_attribute.(model, MOA.ObjectivePriority.(1:4), [2, 3, 4, 1])
# This may also help
# set_attribute.(model, MOA.ObjectiveRelativeTolerance.(1:4), 0.01)
optimize!(model)
termination_status(model)
solution_summary(model)

Even after this, you still see the occasional Warning: Markowitz tolerance tightened to warning, which is an indicator of numerical difficulty.