ERGO-Code / HiGHS

Linear optimization software
MIT License
976 stars 180 forks source link

HiGHS wrongly reporting infeasibilty #1704

Open Matryoskas opened 7 months ago

Matryoskas commented 7 months ago

HiGHS reporting infeasibility with feasible problem.
Note that using value = 10**11 or value = 10**13 reports feasibility Bug originating in scipy/scipy#20116

Reproducing code

import highspy
import numpy as np

# Highs h
h = highspy.Highs()

inf = highspy.kHighsInf

h.addVar(0, 1)
h.addVar(0, 1)

h.changeColCost(0, 0)
h.changeColCost(1, 0)

num_nz = 2
index = np.array([0, 1])
value = 10**12
values = np.array([100.4534, value])
h.addRow(-inf, value, num_nz, index, values)

values = np.array([100.4534, -value])
h.addRow(-inf, 0, num_nz, index, values)

h.changeColsIntegrality(2, np.array([0, 1]), np.array([highspy.HighsVarType.kInteger, highspy.HighsVarType.kInteger]))

h.run()

solution = h.getSolution()
basis = h.getBasis()
info = h.getInfo()
model_status = h.getModelStatus()
print('Model status = ', h.modelStatusToString(model_status))
print()
print('Optimal objective = ', info.objective_function_value)
print('Iteration count = ', info.simplex_iteration_count)

Result

Running HiGHS 1.5.3 [date: 2023-05-16, git hash: 594fa5a9d-dirty]
Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
Presolve: Infeasible

Solving report
  Status            Infeasible
  Primal bound      inf
  Dual bound        -inf
  Gap               inf
  Solution status   -
  Timing            0.00 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             0
  LP iterations     0 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)
Model status =  Infeasible

Optimal objective =  inf
Iteration count =  0
jajhall commented 7 months ago

I'll investigate, but using such extreme values in the matrix is asking for trouble

jajhall commented 7 months ago

I've reproduced this and note that presolve performs one action for value up to 10^12, and a different action for 10^13 (and beyond, I guess). For value up to 10^12, there is a subsequent action that changes for 10^12, leading to an error.

Will investigate further, but not a priority for now