LP reported Infeasible by presolve is Optimal without

[infinity77]

Dear HiGHS developers,

I have a not so large LP (6763 rows; 6735 cols; 12187 nonzeros) and I am attaching it to this discussion - in LP format (I had to change the extension to TXT, but it's an LP file generated by HiGHS).

Up to now I had been using GLPK (which didn't complain about infeasibility in solving this type of problems) and I was looking forward to use HiGHS as it is so much faster - 10 times faster on my problems - when it doesn't complain about infeasibility.

I have a number of questions. I have only overridden these options in a file named "highs_options.txt", as I do not need incredible precision:

kkt_tolerance=1e-6
presolve=on
small_matrix_value=1e-7

Running with:

highs.exe --model_file highs.lp --options_file=highs_options.txt

I get:

Running HiGHS 1.11.0 (git hash: n/a): Copyright (c) 2025 HiGHS under MIT licence terms
Set option presolve to "on"
Set option small_matrix_value to 1e-07
Set option kkt_tolerance to 1e-06
Set option log_file to "HiGHS.log"
LP   highs has 6763 rows; 6735 cols; 12187 nonzeros
Coefficient ranges:
  Matrix [2e-07, 9e+00]
  Cost   [2e-08, 4e+00]
  Bound  [2e+02, 2e+07]
  RHS    [9e+00, 1e+06]
Presolving model
723 rows, 1053 cols, 3312 nonzeros  0s
Problem status detected on presolve: Infeasible
Model name          : highs
Model status        : Infeasible
Objective value     :  0.0000000000e+00
HiGHS run time      :          0.01

So the presolver tells me that the model is infeasible. If I use presolve=off, then I get:

Running HiGHS 1.11.0 (git hash: n/a): Copyright (c) 2025 HiGHS under MIT licence terms
Set option presolve to "off"
Set option small_matrix_value to 1e-07
Set option kkt_tolerance to 1e-06
Set option log_file to "HiGHS.log"
LP   highs has 6763 rows; 6735 cols; 12187 nonzeros
Coefficient ranges:
  Matrix [2e-07, 9e+00]
  Cost   [2e-08, 4e+00]
  Bound  [2e+02, 2e+07]
  RHS    [9e+00, 1e+06]
Solving LP without presolve, or with basis, or unconstrained
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0     0.0000000000e+00 Ph1: 0(0) 0s
        869     5.8915763439e+05 Pr: 0(0); Du: 0(4.44089e-16) 0s
        869     5.8915763439e+05 Pr: 0(0); Du: 0(4.44089e-16) 0s
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
        869     5.8907623341e+05 Pr: 14(0.00330772); Du: 0(7.11341e-08) 0s
        891     5.8907623153e+05 0s
WARNING: LP solution KKT conditions
num/max      1 / 2.98e-05 (relative      0 / 7.19e-11) primal infeasibilities     (tolerance = 1e-06)
num/max      0 / 1.67e-08 (relative      0 / 3.94e-09)   dual infeasibilities     (tolerance = 1e-06)
                                         0 / 1.98e-16  P-D objective error        (tolerance = 1e-06)
WARNING: Model status changed from "Unknown" to "Optimal"
Model name          : highs
Model status        : Optimal
Simplex   iterations: 891
Objective value     :  5.8915763250e+05
P-D objective error :  1.9759605343e-16
HiGHS run time      :          0.03

So the model has been solved to optimality. I get the exact same solution from GLPK (with presolver).

Of course I could disable the presolver in HiGHS, but then I lose all the speed advantage. Models are solved relatively fast but I have to solve thousand upon thousands of them, and without presolver HiGHS is actually 10% slower than GLPK (on average).

So, for the questions:

1. Is there anything I can do to stop the presolver complaining, since the model can be solved to optimality (albeit with warnings)?
2. Unrelated, but: why is it that if I change the value of small_matrix_value to 1e-7 (or smaller) I get that the model is infeasible - with or without presolve? I thought that small_matrix_value was used only to filter out values in the constraint matrix that are too small, but apparently I had misunderstood. Or maybe are exactly those small values in the matrix/cost array that make HiGHS think that the model is infeasible. I do not know. Note that I would like to keep those small values as they have a meaning, and not filter them out via a tweaked small_matrix_values.

This is on Windows 10, HiGHS 1.11.0 compiled via Visual Studio/CMake.

Thank you in advance for any suggestion.

Output of GLPK (glpsol.exe), if it can help in any way (GLPK.lp is the same file as HiGHS.lp, but generated by GLPK). Note that the number of nonzeros in GLPK is greater than the ones in HiGHS, because if I don't force HiGHS to exclude values < 1e-6 then I get that the problem is infeasible.

glpsol.exe --lp GLPK.lp --max --dual --presol
GLPSOL: GLPK LP/MIP Solver, v4.65
Parameter(s) specified in the command line:
 --lp GLPK.lp --max --dual --presol
Reading problem data from 'GLPK.lp'...
6763 rows, 6785 columns, 12187 non-zeros
9747 lines were read
GLPK Simplex Optimizer, v4.65
6763 rows, 6785 columns, 12187 non-zeros
Preprocessing...
785 rows, 988 columns, 3574 non-zeros
Scaling...
 A: min|aij| =  6.981e-07  max|aij| =  9.051e+00  ratio =  1.297e+07
GM: min|aij| =  1.853e-01  max|aij| =  5.396e+00  ratio =  2.911e+01
EQ: min|aij| =  3.474e-02  max|aij| =  1.000e+00  ratio =  2.879e+01
Constructing initial basis...
Size of triangular part is 765
      0: sum =   8.573890694e+01 inf =   8.574e+01 (17)
     34: sum =   0.000000000e+00 inf =   3.708e-18 (0)
#   417: obj =   5.891576317e+05 inf =   3.476e-18 (0) 2
OPTIMAL LP SOLUTION FOUND
Time used:   0.0 secs
Memory used: 5.4 Mb (5712080 bytes)

HiGHS.txt

[jajhall]

I've reproduced your experience with this model.

I gave it to a commercial solver which (like vanilla HiGHS) identified infeasibility in presolve. Switching presolve off, that same commercial solver (like vanilla HiGHS) still identifies infeasibility.

Fundamentally, your LP is badly scaled and close to being infeasible, in that it may only have a small space of feasible solutions, and the bad scaling can make this space appear empty

When HiGHS options are set (as you describe) to obtain an optimal solution, the nonzero optimal values of your variables are (at least) of order 10^3, and I see that some of your bounds of order 10^5 are active. Given that the feasibility tolerance is 1e-6, this is asking for 11 orders of magnitude of accuracy. Far from being the worst that I've seen, but still challenging. Ideally your optimal solution values and constraint activities should be of order one.

HiGHS has a user_bound_scale option that scales the bounds on variables and constraints by a constant value of 2^user_bound_scale. If I set this to -10, then HiGHS (with no other changes to default option values) finds an optimal solution. If I write out the model with scaled bounds on variables and constraints, and give it to the commercial solver, it finds an optimal solution.

The value of small_matrix_value is used in presolve and the simplex solver to make decisions. At 1e-7, no original matrix values in your problem are removed: the smallest is 2e-07 (in magnitude).

[infinity77]

Thank you very much @jajhall for your thoughtful answer. If I came out as disrespectful, please accept my apologies, it was definitely not my intention.

I am mostly a programmer and I am not very strong in linear programming (on the contrary...). I will implement your suggestion of using user_bound_scale.

Other than that, you were explaining about "feasibility tolerance". I can see that HiGHS has 6 possible entries for tolerances:

kkt_tolerance
primal_feasibility_tolerance
dual_feasibility_tolerance
primal_residual_tolerance
dual_residual_tolerance
optimality_tolerance

For problems like mine, would you suggest modifying one (or more, or all?) of them? And if yes, assuming my problems span the ranges/magnitudes you have seen for the constraint matrix/bounds, which value(s) would you suggest me to use?

Sorry for the dumb questions, any suggestion is most welcome.

[jajhall]

No problem! I deal with a lot of people to whom solvers are black boxes!

Your constraint matrix values aren't too bad: internally HiGHS scales the matrix before running the simplex solver, and then cleans up any feasibility violations that occur after removing the scaling.

If your model is well scaled, then there's no need to change the tolerances. That said, it's better to change just the kkt_tolerance, as the others change as a result.

Ideally you'd change your original model, rather than use user_bound_scale. All you need to do is scale down the bounds on the variables and constraints by the same constant value. The matrix coefficients don't change, as the contribution from each variable to a constraint is scaled down by a constant amount, and the bounds on the constraint are also scaled down by that same constant value. Hence the "effect" of that constraint is unchanged. You'll have to scale the solution values back up (as you'll also have to do if you set user_bound_scale = -10, as the scaled problem will have been solved.

Note that with the settings you found to get HiGHS to solve to optimality, it took 891 simplex iterations. When I just set user_bound_scale = -10, it takes 182 simplex iterations. The solution time was halved. This is mainly because the original problem has

6763 rows; 6735 cols; 12187 nonzeros

and the presolved problem has

174 rows, 475 cols, 1982 nonzeros

However, it is typical that improving the numerical properties of an LP also improves solution time.

[ollie-bell]

Hi @jajhall - I just want to pick up on something you've said here if you don't mind...

Ideally you'd change your original model, rather than use user_bound_scale

Are you able to elaborate on what makes applying scaling to the original model "better" than using user_bound_scale (or user_cost_scale for that matter)?

Thanks!

[jajhall]

Are you able to elaborate on what makes applying scaling to the original model "better" than using user_bound_scale (or user_cost_scale for that matter)?

user_bound_scale and user_cost_scale scale all the bounds and costs. If some of your variables and constraints are well scaled (optimal variable and constraint value of order 1) then scaling their bounds down (by 10^3, say) because other variables and constraints are badly scaled will mean that the well-scaled variables and constraints will have optimal variable and constraint values of order 10^{-3} - which is rather small.

It's better if the user makes sure that each individual decision (variable) is modelled with the right units so that the optimal value is of order 1.

For a more extensive treatment of scaling, see this JuMP tutorial