Feasibility cut from HiGHS and Mosek are different (Benders decomposition)

Specific Domains Optimization (Mathematical)
, ,
1

Hi,
I am implementing bender’s decomposition using JuMP in Julia. I am investigating generation of feasibility cuts using “dual_objective_value” and “reduced_cost” of fixing constraint as detailed in JuMP documentation.
I observed that for the problem I am solving, Mosek generated values of “dual_objective_value” and “reduced_cost” are far different than HiGHS generated values.

Also, optimal solutions for monolithic version of the same problem are different from both solvers.

I wonder anyone faced similar issue or anyone know how to deal with this? Please help me understand the problem.

2

This is probably this bug in HiGHS: Changing a model does not invalidate stored dual ray · Issue #2159 · ERGO-Code/HiGHS · GitHub

Can you try

import Pkg; Pkg.pkg"add HiGHS_jll@1.8"

then restart Julia for the change to take effect.

3

Are the objective values different? If so, this is expected behavior. The primal solutions may be different, provided they have the same optimal cost.

If not, could you post a reproducible example? This seems like a bug.

4

Hi @odow,
I have been using HiGHS 1.7.2 so far. I updated it using the command given by you (I think I am confused here with HiGHS.jl vs. HiGHS_jll.jl).
Following is the result of Mosek, HiGHS 1.7.2 and HiGHS 1.13.0 one after the other. I couldn’t get to run with HiGHS_jll.jl (usual commands giving errors, HiGHS not found etc.). You can see differences in dual objective value and reduced costs. HiGHS versions themselves start differing from 2nd iteration onwards. And both differ from Mosek. Which one should be taken as correct to use in generating feasibility cut in master problem?

Mosek solver -----------------------------------------------

Iteration  Lower Bound  Upper Bound          Gap
[ Info: iteration 1:
Master problem solution: [0.0, 234.0, 60.0, 25.2, 100.1, 18.9, 51.5, 7.0])
Solver summary 1: * Solver : Mosek

* Status
  Result count       : 2
  Termination status : INFEASIBLE
  Message from the solver:
  "Mosek.MSK_SOL_STA_PRIM_INFEAS_CER, Mosek.MSK_SOL_STA_PRIM_INFEAS_CER"

* Candidate solution (result #1)
  Primal status      : NO_SOLUTION
  Dual status        : INFEASIBILITY_CERTIFICATE
  Objective value    : 2.03298e+03
  Objective bound    : 2.03298e+03
  Relative gap       : 0.00000e+00
  Dual objective value : 6.76234e+02

* Work counters
  Solve time (sec)   : 1.50000e-02
  Simplex iterations : 0
  Barrier iterations : 7
  Node count         : 0

Dual objective 676.233791424253
Dual objective2 1.5538908976216987
Dual of fixing constraint: 1-dimensional DenseAxisArray{Float64,1,...} with index sets:
    Dimension 1, ["BESS", "Coal", "Wind", "Gas", "Solar", "Nuclear", "Hydro", "PHES"]
And data, a 8-element Vector{Float64}:
 -224.23117926597823
   -6.84714838029748
   -3.179480575453545
  -51.57296129189378
  -11.778385241730215
  -77.57091035661986
  -25.619933698782408
 -133.87907206605246
[ Info: From SP_slide: 1, adding the feasibility cut
[ Info: iteration 2:
Master problem solution: [0.0, 234.0, 60.0, 25.2, 100.1, 18.9, 51.5, 12.100000000000001])
Solver summary 1: * Solver : Mosek

* Status
  Result count       : 2
  Termination status : INFEASIBLE
  Message from the solver:
  "Mosek.MSK_SOL_STA_PRIM_INFEAS_CER, Mosek.MSK_SOL_STA_PRIM_INFEAS_CER"

* Candidate solution (result #1)
  Primal status      : NO_SOLUTION
  Dual status        : INFEASIBILITY_CERTIFICATE
  Objective value    : 1.96198e+03
  Objective bound    : 1.96198e+03
  Relative gap       : 0.00000e+00
  Dual objective value : 7.61661e+02

* Work counters
  Solve time (sec)   : 1.60000e-02
  Simplex iterations : 0
  Barrier iterations : 7
  Node count         : 0

Dual objective 761.6605191761382
Dual objective2 61.853870753565474
Dual of fixing constraint: 1-dimensional DenseAxisArray{Float64,1,...} with index sets:
    Dimension 1, ["BESS", "Coal", "Wind", "Gas", "Solar", "Nuclear", "Hydro", "PHES"]
And data, a 8-element Vector{Float64}:
 -222.44186832040563
   -6.798786982402782
   -3.316844327926217
  -53.10916382473041
  -12.434561518222992
  -81.19830351987589
  -26.784778424512876
  -92.44951124796701
[ Info: From SP_slide: 1, adding the feasibility cut
Max. iterations exceeded



HiGHS 1.7.2 -----------------------------------------------

Iteration  Lower Bound  Upper Bound          Gap
[ Info: iteration 1:
Master problem solution: [0.0, 234.0, 60.0, 25.2, 100.1, 18.9, 51.5, 7.0])
Solver summary 1: * Solver : HiGHS

* Status
  Result count       : 1
  Termination status : INFEASIBLE
  Message from the solver:
  "kHighsModelStatusInfeasible"

* Candidate solution (result #1)
  Primal status      : NO_SOLUTION
  Dual status        : INFEASIBILITY_CERTIFICATE
  Objective value    : 1.50441e+03
  Objective bound    : 0.00000e+00
  Relative gap       : Inf
  Dual objective value : 1.47435e+03

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

Dual objective 1474.3466658977077
Dual of fixing constraint: 1-dimensional DenseAxisArray{Float64,1,...} with index sets:
    Dimension 1, ["BESS", "Coal", "Wind", "Gas", "Solar", "Nuclear", "Hydro", "PHES"]
And data, a 8-element Vector{Float64}:
  -7.963777549480293
   1.5124659704116015
  -1.4186121244278929
 -18.833898051852934
  -7.293967319889654
 -39.996100703090676
 -13.62277602167863
 -17.564137281840175
[ Info: From SP_slide: 1, adding the feasibility cut
[ Info: iteration 2:
Master problem solution: [0.0, 199.2, 60.0, 25.2, 211.5, 31.5, 51.5, 13.0])
Solver summary 1: * Solver : HiGHS

* Status
  Result count       : 1
  Termination status : INFEASIBLE
  Message from the solver:
  "kHighsModelStatusInfeasible"

* Candidate solution (result #1)
  Primal status      : NO_SOLUTION
  Dual status        : INFEASIBILITY_CERTIFICATE
  Objective value    : 1.38974e+03
  Objective bound    : 0.00000e+00
  Relative gap       : Inf
  Dual objective value : 1.40608e+03

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

Dual objective 1406.0834601001025
Dual of fixing constraint: 1-dimensional DenseAxisArray{Float64,1,...} with index sets:
    Dimension 1, ["BESS", "Coal", "Wind", "Gas", "Solar", "Nuclear", "Hydro", "PHES"]
And data, a 8-element Vector{Float64}:
 -25.3361718883356
 -41.69553162856768
  -1.518704568788242
 -44.46746354407891
  -3.063426351870198
 -38.33576771634835
 -14.566792175993577
 -28.667955876273886
[ Info: From SP_slide: 1, adding the feasibility cut
Max. iterations exceeded

HiGHS 1.13.0. -----------------------------------------------------------

Iteration  Lower Bound  Upper Bound          Gap
[ Info: iteration 1:
Master problem solution: [0.0, 234.0, 60.0, 25.2, 100.1, 18.9, 51.5, 7.0])
Solver summary 1: * Solver : HiGHS

* Status
  Result count       : 1
  Termination status : INFEASIBLE
  Message from the solver:
  "kHighsModelStatusInfeasible"

* Candidate solution (result #1)
  Primal status      : NO_SOLUTION
  Dual status        : INFEASIBILITY_CERTIFICATE
  Objective value    : 1.50441e+03
  Objective bound    : 0.00000e+00
  Relative gap       : Inf
  Dual objective value : 1.47435e+03

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

Dual objective 1474.3466658977086
Dual of fixing constraint: 1-dimensional DenseAxisArray{Float64,1,...} with index sets:
    Dimension 1, ["BESS", "Coal", "Wind", "Gas", "Solar", "Nuclear", "Hydro", "PHES"]
And data, a 8-element Vector{Float64}:
  -7.963777549480293
   1.5124659704116015
  -1.4186121244278929
 -18.833898051852934
  -7.293967319889654
 -39.996100703090676
 -13.62277602167863
 -17.564137281840175
[ Info: From SP_slide: 1, adding the feasibility cut
[ Info: iteration 2:
Master problem solution: [0.0, 199.2, 60.0, 25.2, 211.5, 31.5, 51.5, 13.0])
Solver summary 1: * Solver : HiGHS

* Status
  Result count       : 1
  Termination status : INFEASIBLE
  Message from the solver:
  "kHighsModelStatusInfeasible"

* Candidate solution (result #1)
  Primal status      : NO_SOLUTION
  Dual status        : INFEASIBILITY_CERTIFICATE
  Objective value    : 1.38974e+03
  Objective bound    : 0.00000e+00
  Relative gap       : Inf
  Dual objective value : -1.70802e-01

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

Dual objective -0.17080185830855044
Dual of fixing constraint: 1-dimensional DenseAxisArray{Float64,1,...} with index sets:
    Dimension 1, ["BESS", "Coal", "Wind", "Gas", "Solar", "Nuclear", "Hydro", "PHES"]
And data, a 8-element Vector{Float64}:
  -7.963777549480293
   1.5124659704116015
  -1.4186121244278929
 -18.833898051852934
  -7.293967319889654
 -39.996100703090676
 -13.62277602167863
 -17.564137281840175
[ Info: From SP_slide: 1, adding the feasibility cut
Max. iterations exceeded
5

I checked through my results of earlier runs of monolithic problem with both HiGHS 1.7.2 and Mosek and I found the objective values are close enough (its an MILP, so exact match might not come !?) and optimal solution is different in only few cases. That can be problem dependent.

For LPs, CPLEX, Mosek and HiGHS were giving different optimal solutions with same objective function value in some cases. That also could be problem dependent, as I understand from the structure of the problem.

6

Re HiGHS_jll: Still use HiGHS.jl in your code. You just need to add compatibility restrictions for HiGHS_jll.jl, which is a separate package.

Just do:

import Pkg; Pkg.pkg"add HiGHS_jll@1.8"
using JuMP, HiGHS
model = Model(HiGHS.Optimizer)

Different solutions with the same objective value is expected behavior. Any yes, MIPs are often solved to some tolerance, so their objectives might be slightly different.

7

I have done this only last time.
added HiGHS_jll@1.8 (during this process I noticed that many other Julia packages got updated to later versions).
Then ran the simulation (with fresh Julia instance in VS code) and then posted the result.
Later I noticed with Pkg.status() that the version of HiGHS was 1.13.0 while HiGHS_jll was 1.8.1. So, I confused.

I would like to highlight the difference in dual_objective_value and reduced_cost of fixing constraint among Mosek and two different versions of HiGHS which is leading to infeasibility of master problem with HiGHS generated feasibility cuts, while same problem runs well with Mosek generated feasibility cuts.

As of now, I am going with Mosek because my problem is being solved correctly. Need to do something about HiGHS to set the feasibility cuts right.