Issue with Interior point method for HiGHS

Specific Domains Optimization (Mathematical)
1

I’m using JuMP, and have just started testing out the HiGHS optimizer, and I’ve encounted a strange issue with the interior point method.

For a small model, the HiGHS optimizer toggles between returning the optimal solution and returning ‘infeasible’. This appears to be related to whether presolve is used (if presolve is forced to be ‘off’, the result is always infeasible). Is the interior point method in HiGHS still under development, and not ready for general use?

model = read_from_file("fail.mps")
set_optimizer(model,optimizer_with_attributes(HiGHS.Optimizer,
    "solver" => "ipm", "output_flag" => true))

for i in 1:4
    @info("Attempt $i")
    optimize!(model)
    println(termination_status(model))
end

[ Info: Attempt 1
Presolving model
0 rows, 0 cols, 0 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve : Reductions: rows 0(-38); columns 0(-38); elements 0(-70) - Reduced to empty
Solving the original LP from the solution after postsolve
Model   status      : Optimal
Objective value     :  6.2875000000e+01
HiGHS run time      :          0.01
OPTIMAL
[ Info: Attempt 2
Solving LP without presolve or with basis
IPX model has 38 rows, 38 columns and 70 nonzeros
Input
    Number of variables:                                38
    Number of free variables:                           8
    Number of constraints:                              38
    Number of equality constraints:                     38
    Number of matrix entries:                           70
    Matrix range:                                       [2e-01, 1e+02]
    RHS range:                                          [1e+00, 2e+00]
    Objective range:                                    [1e-01, 1e-01]
    Bounds range:                                       [1e+00, 2e+00]
Preprocessing
    Dualized model:                                     no
    Number of dense columns:                            0
    Range of scaling factors:                           [2.50e-01, 2.00e+00]
IPX version 1.0
Interior Point Solve
 Iter     P.res    D.res            P.obj           D.obj        mu     Time
   0   6.09e+00 2.49e-01   1.18016444e-01 -4.22655591e+01  9.89e+00       0s
   1   2.07e+00 1.83e-01   2.47301107e-02 -3.16192108e+00  3.35e+00       0s
   2   2.00e+00 2.09e+00   1.34352352e+00  5.28801748e+02  3.54e+00       0s
 Constructing starting basis...
Summary
    Runtime:                                            0.01s
    Status interior point solve:                        primal infeas
    Status crossover:                                   not run
WARNING: Ipx: IPM       primal infeasible
WARNING: Ipx: Crossover not run
Model   status      : Infeasible
IPM       iterations: 2
Objective value     :  1.3435235189e+00
HiGHS run time      :          0.04
INFEASIBLE
[ Info: Attempt 3
Presolving model
0 rows, 0 cols, 0 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve : Reductions: rows 0(-38); columns 0(-38); elements 0(-70) - Reduced to empty
Solving the original LP from the solution after postsolve
Model   status      : Optimal
Objective value     :  6.2875000000e+01
HiGHS run time      :          0.05
OPTIMAL
[ Info: Attempt 4
Solving LP without presolve or with basis
IPX model has 38 rows, 38 columns and 70 nonzeros
Input
    Number of variables:                                38
    Number of free variables:                           8
    Number of constraints:                              38
    Number of equality constraints:                     38
    Number of matrix entries:                           70
    Matrix range:                                       [2e-01, 1e+02]
    RHS range:                                          [1e+00, 2e+00]
    Objective range:                                    [1e-01, 1e-01]
    Bounds range:                                       [1e+00, 2e+00]
Preprocessing
    Dualized model:                                     no
    Number of dense columns:                            0
    Range of scaling factors:                           [2.50e-01, 2.00e+00]
IPX version 1.0
Interior Point Solve
 Iter     P.res    D.res            P.obj           D.obj        mu     Time
   0   6.09e+00 2.49e-01   1.18016444e-01 -4.22655591e+01  9.89e+00       0s
   1   2.07e+00 1.83e-01   2.47301107e-02 -3.16192108e+00  3.35e+00       0s
   2   2.00e+00 2.09e+00   1.34352352e+00  5.28801748e+02  3.54e+00       0s
 Constructing starting basis...
Summary
    Runtime:                                            0.01s
    Status interior point solve:                        primal infeas
    Status crossover:                                   not run
WARNING: Ipx: IPM       primal infeasible
WARNING: Ipx: Crossover not run
Model   status      : Infeasible
IPM       iterations: 2
Objective value     :  1.3435235189e+00
HiGHS run time      :          0.07
INFEASIBLE

Thanks.

2

I reported a number of bugs like this. They should be fixed in the next release.

But also, yes, the IPM is less mature. Julian is getting some funding to improve it.

2 Likes