Unbounded problem not correctly identified

[datejada]

Hi HiGHS team,

The attached .lp file in this .zip file unbounded-problem.zip has a MIP problem that it is unbounded, but HiGHS fails to detect it before going into the B&B, and then after a couple of iterations it freezes and no extra information is given (e.g., warning or error). We detected that the problem was unbounded due to the variables flow_(ccgt,_demand),_2030,XXX,YYY. Although the root cause is a problem in the data of the problem, it would be interesting to get a message from the solver indicating the unbounded condition from the start. Below is all the information to reproduce the error:

  [87dc4568] HiGHS v1.9.3
  [4076af6c] JuMP v1.23.2

using JuMP
using HiGHS

model = read_from_file("unbounded-problem.lp")
set_optimizer(model, HiGHS.Optimizer)
optimize!(model)

A JuMP Model
├ solver: none
├ objective_sense: MIN_SENSE
│ └ objective_function_type: AffExpr
├ num_variables: 1102
├ num_constraints: 2703
│ ├ AffExpr in MOI.EqualTo{Float64}: 216
│ ├ AffExpr in MOI.GreaterThan{Float64}: 288
│ ├ AffExpr in MOI.LessThan{Float64}: 1224
│ ├ VariableRef in MOI.GreaterThan{Float64}: 957
│ ├ VariableRef in MOI.Interval{Float64}: 1
│ └ VariableRef in MOI.Integer: 17
└ Names registered in the model: none

Running HiGHS 1.7.2 (git hash: 5ce7a2753): Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [1e-01, 4e+02]
  Cost   [3e-02, 4e+04]
  Bound  [2e+01, 2e+01]
  RHS    [9e-02, 1e+03]
Presolving model
1296 rows, 706 cols, 4032 nonzeros  0s
936 rows, 346 cols, 3600 nonzeros  0s 
543 rows, 341 cols, 2135 nonzeros  0s 
543 rows, 339 cols, 2135 nonzeros  0s

Solving MIP model with:
   543 rows
   339 cols (0 binary, 11 integer, 0 implied int., 328 continuous)
   2135 nonzeros

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work
     Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   -inf            inf                  inf        0      0      0         0     0.0s
 C       2       0         2 100.00%   -inf            -75737988.86364    Large        0      0      0       439     0.0s
 S       3       0         3 100.00%   -inf            -176187988.8931    Large        0      0      0       574     0.1s
 L       3       0         3 100.00%   -inf            -176189166.7404    Large        0      0      0       574     0.1s

I hope all this information helps you to reproduce and improve the current HiGHS version.

BR,

Diego

[jajhall]

Interesting. I'll look into how the solver interprets an unbounded LP at a (the root) node.

[datejada]

If it helps, we also double-checked that the problem is unbounded using a commercial solver. Thanks!

[jajhall]

We should have a unit test for unbounded MIPs, but might not. May make it easier to debug with a simple problem and presolve off

[jajhall]

We do have a couple of unit tests for unbounded MIPs, so identifying what's wrong is non-trivial