3
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ What are the values of the other variables in the objective function in both cases? $\endgroup$
    – Kuifje
    Commented Feb 2 at 16:34
  • $\begingroup$ 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. $\endgroup$
    – Mark L. Stone
    Commented Feb 2 at 17:08
  • $\begingroup$ 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? $\endgroup$
    – Hubcity
    Commented Feb 2 at 18:17
  • $\begingroup$ @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. $\endgroup$
    – Hubcity
    Commented Feb 2 at 19:20
  • 1
    $\begingroup$ 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 $\endgroup$
    – fontanf
    Commented Feb 2 at 21:18

1 Answer 1

Reset to default
3
$\begingroup$

The primal bound of one problem should not be less than dual bound of the other problem. This suggests a bug somewhere.

In a comment, @Hubcity wrote "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."

Combining these two paragraphs, this suggests there might be a bug in the solver's presolve, and the solver incorrectly solved the problem in presolve. Bugs in presolve exist even in "mature" solvers. As confirmed by the OP's edits in response to my comment suggesting this possibility, a bug in presolve does appear to be the culprit in this case, because the discrepancy disappeared when presolve was turned off.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.