# Equivalent constraints in MILP give different answers

I'm getting unexpected results from the HiGHS solver in scipy (scipy.optimize.linprog with integrality constraints).

In my mixed integer program one of my constraints is that $$x_0 \geq 100$$. I get a result where $$x_0$$ is 100 and my cost function has a minimum of 220902.826196.

Running HiGHS 1.2.0 [date: 2021-07-09, git hash: n/a]
Copyright (c) 2022 ERGO-Code under MIT licence terms
Presolving model
813 rows, 1081 cols, 5815 nonzeros
643 rows, 911 cols, 5495 nonzeros
538 rows, 781 cols, 5440 nonzeros

Solving MIP model with:
538 rows
781 cols (110 binary, 0 integer, 0 implied int., 671 continuous)
5440 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

Solving report
Status            Optimal
Primal bound      220902.826196
Dual bound        220902.826196
Gap               0% (tolerance: 0.01%)
Solution status   feasible
220902.826196 (objective)
0 (bound viol.)
3.7562287347e-17 (int. viol.)
0 (row viol.)
Timing            0.02 (total)
0.01 (presolve)
0.00 (postsolve)
Nodes             1
LP iterations     297 (total)
0 (strong br.)
0 (separation)
0 (heuristics)
Optimization terminated successfully. (HiGHS Status 7: Optimal)


However if I change my constraint to be $$x_0 = 100$$, I get a result where $$x_0$$ is 100 and my cost function has a minimum of 191817.038217.

Running HiGHS 1.2.0 [date: 2021-07-09, git hash: n/a]
Copyright (c) 2022 ERGO-Code under MIT licence terms
Presolving model
813 rows, 1080 cols, 5780 nonzeros
643 rows, 910 cols, 5460 nonzeros
538 rows, 780 cols, 5405 nonzeros

Solving MIP model with:
538 rows
780 cols (110 binary, 0 integer, 0 implied int., 670 continuous)
5405 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%   -3171485.384239 inf                  inf        0      0      0         0     0.0s
R       0       0         0   0.00%   170865.965397   220902.826196     22.65%        0      0      0       326     0.0s
L       0       0         0   0.00%   171141.068245   192959.352843     11.31%       10     10      0       347     0.4s
[...many logging lines here...]
B   23848     223     10070  98.90%   191059.243484   191842.696644      0.41%      130     16    725    337428    66.1s
B   23857     145     10072  98.93%   191059.243484   191817.038217      0.40%      124     16    721    337454    66.1s

Solving report
Status            Optimal
Primal bound      191817.038217
Dual bound        191797.945869
Gap               0.00995% (tolerance: 0.01%)
Solution status   feasible
191817.038217 (objective)
0 (bound viol.)
7.23311321847e-17 (int. viol.)
0 (row viol.)
Timing            66.53 (total)
0.01 (presolve)
0.00 (postsolve)
Nodes             24003
LP iterations     344914 (total)
57769 (strong br.)
1023 (separation)
21044 (heuristics)
Optimization terminated successfully. (HiGHS Status 7: Optimal)


Shouldn't both formulations of the problem find the same cost minimum as the only constraint I'm changing is the constraint on $$x_0$$ and $$x_0$$ is found to have the same value in both cases.

(In this program I'm also using binary decision variables and bigM formulations. But I'm not changing those constraints between the two runs.)

Edit: Added log files and changed the cost numbers to my actual results. The first one stops at 220902. That number also appears in the second log file, but the solver finds something better by the time the next logging statement is printed. At this point I feel like I'm asking how to read HiGHS log files, which might be what I really need to know.

Edit2: The comments here hinted that something might be going wrong in the presolve. So I ran it again with options={'presolve' : False} in both cases and got the answers of 191800 and 191808 both within the gap tolerance.

• What are the values of the other variables in the objective function in both cases? Feb 2 at 16:34
• What optimality gap are you solving to? Presuming this is a minimization problem, is the final lower bound from the 1st problem <= 5.7? If so, the results are not inconsistent. Feb 2 at 17:08
• I'm using the default gap (I think this is 0.01%). Yes, this is a minimization problem. For the x[0] >= 100 it reports a primal bound and dual bound of 6.5 with a gap of 0%. In the logging it does not show any Branch & Bound exploration. It returns an answer almost immediately. For the x[0] == 100 the logs show multiple levels of B&B exploration. The first row of B&B logs reports a BestSol of 6.5, but then it continues to explore until it gets to 5.7 with a gap of 0.00995%. That program runs for about 60 seconds. Can I force HiGHS to do B&B in the first case? Feb 2 at 18:17
• @Kuifje, the values of the other variables in the objective function are different between runs, but that is essentially my question. I'm only changing the constraint on x[0] and then x[0] turns out to be the same on both runs so I don't know why other values would be different. The problem seems ridiculously huge to me with 1892 variables. I wouldn't know where I'd begin to try to make it small enough to discuss. Feb 2 at 19:20
• Please include the log of both solves in the question. This might be a bug, or not. Such behaviors might happen because of presolve and/or tolerances Feb 2 at 21:18