kHighsModelStatusOptimal reported for non-convex QP

[odow]

Solving Max x * y returns "Optimal" instead of declaring the QP to be non-convex. See the JuMP example:

julia> using JuMP, HiGHS

julia> model = Model(HiGHS.Optimizer)
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: EMPTY_OPTIMIZER
Solver name: HiGHS

julia> @variable(model, x)
x

julia> @variable(model, y)
y

julia> @objective(model, Max, x * y)
x*y

julia> optimize!(model)
Running HiGHS 1.7.0 (git hash: 50670fd4c): Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Cost   [0e+00, 0e+00]
  Bound  [0e+00, 0e+00]
Iteration, Runtime, ObjVal, NullspaceDim
0, 0.000214, 0.000000, 2
2, 0.000252, 0.000000, 2
Model   status      : Optimal
Objective value     :  0.0000000000e+00
HiGHS run time      :          0.00

julia> solution_summary(model)
* Solver : HiGHS

* Status
  Result count       : 1
  Termination status : OPTIMAL
  Message from the solver:
  "kHighsModelStatusOptimal"

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

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

As well as the C calls:

julia> using HiGHS

julia> model = Highs_create()
Ptr{Nothing} @0x00007fab448a6c00

julia> Highs_addCol(model, 0.0, -Inf, Inf, 0, C_NULL, C_NULL)
Running HiGHS 1.7.0 (git hash: 50670fd4c): Copyright (c) 2024 HiGHS under MIT licence terms
0

julia> Highs_addCol(model, 0.0, -Inf, Inf, 0, C_NULL, C_NULL)
0

julia> Highs_changeObjectiveSense(model, kHighsObjSenseMaximize)
0

julia> Highs_passHessian(
           model,
           2,
           1,
           kHighsHessianFormatTriangular,
           Cint[0, 1, 1],
           Cint[1],
           [1.0],
       )
0

julia> Highs_run(model)
Coefficient ranges:
  Cost   [0e+00, 0e+00]
  Bound  [0e+00, 0e+00]
Iteration, Runtime, ObjVal, NullspaceDim
0, 0.000229, 0.000000, 2
2, 0.000256, 0.000000, 2
Model   status      : Optimal
Objective value     :  0.0000000000e+00
HiGHS run time      :          0.00
0

julia> Highs_getModelStatus(model)
7

Originally reported in https://discourse.julialang.org/t/highs-jl-gives-strange-results/112995 x-ref https://github.com/jump-dev/HiGHS.jl/issues/210

[feldmeier]

This might be a side effect I didn't anticipate of a recent improvement I made for unconstrained QPs. I'll check

[odow]

I can to report this again: https://github.com/odow/SDDP.jl/issues/782#issuecomment-2336825119

This time, we find an INFEASIBLE_POINT, but HiGHS declares optimality.

julia> using JuMP, HiGHS

julia> model = JuMP.read_from_file("subproblem_9.mof.json")
A JuMP Model
├ solver: none
├ objective_sense: MAX_SENSE
│ └ objective_function_type: QuadExpr
├ num_variables: 6
├ num_constraints: 9
│ ├ AffExpr in MOI.EqualTo{Float64}: 2
│ ├ AffExpr in MOI.LessThan{Float64}: 1
│ ├ VariableRef in MOI.EqualTo{Float64}: 2
│ ├ VariableRef in MOI.GreaterThan{Float64}: 3
│ └ VariableRef in MOI.LessThan{Float64}: 1
└ Names registered in the model: none

julia> set_optimizer(model, HiGHS.Optimizer)

julia> optimize!(model)
Running HiGHS 1.7.2 (git hash: 5ce7a2753): Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [6e-05, 3e+02]
  Cost   [1e+00, 1e+00]
  Bound  [3e+02, 1e+03]
  RHS    [2e-02, 2e-02]
  Iteration        Objective     NullspaceDim
          0     0.0091790712                0      0.00s
          4     0.0091790712                0      0.00s
ERROR:   getKktFailures: Row    2 status-value error: [-inf; 0.0183407; 0.0182876] has residual 5.3111e-05
ERROR:   QP solver claims optimality, but with num/max/sum primal(1/5.3111e-05/5.3111e-05)and dual(1/1/1) infeasibilities
Model   status      : Optimal
QP ASM    iterations: 4
Objective value     : -5.3111048675e-05
HiGHS run time      :          0.00

julia> solution_summary(model)
* Solver : HiGHS

* Status
  Result count       : 1
  Termination status : OPTIMAL
  Message from the solver:
  "kHighsModelStatusOptimal"

* Candidate solution (result #1)
  Primal status      : INFEASIBLE_POINT
  Dual status        : INFEASIBLE_POINT
  Objective value    : -5.31110e-05
  Objective bound    : -0.00000e+00
  Relative gap       : Inf
  Dual objective value : -1.84113e-02

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

julia> HiGHS.Highs_writeModel(unsafe_backend(model), "bug_sddp.mps")
Writing the model to bug_sddp.mps
WARNING: There are empty or excessively-long column names: using constructed names with prefix "c"
WARNING: There are empty or excessively-long row names: using constructed names with prefix "r"
1

shell> cat bug_sddp.mps
NAME        
OBJSENSE
  MAX
ROWS
 N  Obj     
 E  r0      
 E  r1      
 L  r2      
COLUMNS
    c0        r1        1
    c1        r1        -1
    c1        r2        -302.4250644
    c2        r0        -1.001701446
    c3        r0        1
    c3        r2        6.048507839e-05
    c4        r1        -1
    c5        Obj       1
    c5        r2        1
RHS
    RHS_V     r2        0.01828761203
BOUNDS
 FX BOUND     c0        0
 FX BOUND     c2        302.7121865
 MI BOUND     c5      
 UP BOUND     c5        1000
QUADOBJ
    c3        c4        1
ENDATA

[jajhall]

@feldmeier can no longer work on HiGHS, but I think I have enough understanding of the QP solver to return an appropriate error code