HIGHS 1.7.2. MIP solver terminates prematurely due to error in dual bound

[jeffreydeankelly2]

gaswellrig_lpfile.txt gaswellrig_mpsfile.txt

Attached are the LP and MPS file for a MIP problem which terminates at a gap of 5.36% but the gap is set to your defaults i.e.,

mip_rel_gap = 0.0001 mip_abs_gap = 1d-06

The globally optimal value found by other commercial solvers is 937000.0.

The HIGHS 1.7.2 log file is shown below.

Running HiGHS 1.7.2 (git hash: 5ce7a2753): Copyright (c) 2024 HiGHS under MIT licence terms
Cols:           2 lower bounds    less than or equal to       -1e+20 are treated as -Infinity
Cols:           2 upper bounds greater than or equal to        1e+20 are treated as +Infinity
Rows:       25170 lower bounds    less than or equal to       -1e+20 are treated as -Infinity
Writing the model to c:\IndustrialAlgorithms\Platform\IMPL\IMPLtester\gaswellrig.lp
SOLVE
Coefficient ranges:
  Matrix [1e-04, 2e+04]
  Cost   [1e+00, 1e+00]
  Bound  [5e-01, 1e+04]
  RHS    [1e+00, 2e+04]
Presolving model
27851 rows, 10067 cols, 306660 nonzeros  0s
19582 rows, 9529 cols, 288351 nonzeros  0s
15293 rows, 7648 cols, 280708 nonzeros  0s
8664 rows, 4996 cols, 266757 nonzeros  0s
4850 rows, 3084 cols, 65760 nonzeros  8s
4475 rows, 2389 cols, 63749 nonzeros  17s

Solving MIP model with:
   4475 rows
   2389 cols (639 binary, 0 integer, 790 implied int., 960 continuous)
   63749 nonzeros
         0       0         0   0.00%   1576916.666667  -inf                 inf        0      0      0         0    17.7s
         0       0         0   0.00%   1083352.409137  -inf                 inf        0      0      8      2481    18.2s
         0       0         0   0.00%   1083175.188266  -inf                 inf     2818    194    225      2776    23.3s
   impl> Logistics-Feasible Solution #   1 Found with Objective Function =    0.9094166667E+006
SOLUTIONSPOT1
 L       0       0         0   0.00%   1083021.530188  909416.666667     19.09%     3307    248    283      3026    28.2s

0.3% inactive integer columns, restarting
   impl> Logistics-Feasible Solution #   2 Found with Objective Function =    0.9094166667E+006
SOLUTIONSPOT2
Model after restart has 3330 rows, 1930 cols (526 bin., 0 int., 735 impl., 669 cont.), and 46240 nonzeros
         0       0         0   0.00%   1080844.033306  909416.666667     18.85%      174      0      0      4861    39.1s
         0       0         0   0.00%   1068641.18325   909416.666667     17.51%      174     52      3      5603    39.4s
         0       0         0   0.00%   1068010.097849  909416.666667     17.44%     6171    323     83      8494    47.0s
   impl> Logistics-Feasible Solution #   3 Found with Objective Function =    0.9094166667E+006
SOLUTIONSPOT3
       677     532         1  50.00%   981770.731297   909416.666667      7.96%     6232    188   1296     37054    73.9s
   impl> Logistics-Feasible Solution #   4 Found with Objective Function =    0.9153166667E+006
SOLUTIONSPOT4
 T     687     406        11  50.00%   981770.731297   915316.666667      7.26%     8794    233   1444     37349    75.4s
   impl> Logistics-Feasible Solution #   5 Found with Objective Function =    0.9210166667E+006
SOLUTIONSPOT5
 T     696     406        12  62.50%   981770.731297   921016.666667      6.60%     8800    233   1577     38423    76.3s
   impl> Logistics-Feasible Solution #   6 Found with Objective Function =    0.9265250000E+006
SOLUTIONSPOT6
 T     700     406        13  75.00%   981770.731297   926525             5.96%     8806    233   1623     38958    77.3s
   impl> Logistics-Feasible Solution #   7 Found with Objective Function =    0.9318500000E+006
SOLUTIONSPOT7
 T     703     406        14  87.50%   981770.731297   931850             5.36%     8809    233   1643     39536    78.5s
 impl>
 impl> MILP objective =    931850.000000000
 impl> MILP solutions =                      7
 impl> MILP status =   optimal.
 impl> MILP time =    117.460754394531
 impl>
 INCLUDEDELAYEDROWS = 0
STOP
 impl>
 impl> Solve objective =    931850.000000000
 impl> Solve equality closure =   1.167933137868207E-010
 impl> Solve inequality closure =   1.648558158407915E-010
 impl> Solve status = OPTIMAL
 impl>
 impl> Solve time =    117.498727798462
 impl>
 impl> Export time =   0.192487716674805
 impl>
 impl>
 impl> Release successful.
 impl>
 impl> Total time =    118.176826477051
0
Press any key to continue . . .

[jajhall]

You don't give all the HiGHS logging...

I can't reproduce this behaviour with v1.7.2 using gaswellrig.mps, but with gaswellrig.lp, the MIP solver seems to have stalled after the logging line

L 0 0 0 0.00% 1067812.963931 937000 13.96% 2864 351 5 8184 22.3s

I've left it to run overnight to see what happens, However, the run is still different from yours, since your presolved model has

4475 rows, 2389 cols, 63749 nonzeros 17s

and the presolved model from gaswellrig.lp has

4055 rows, 2141 cols, 53519 nonzeros 8s

The latest branch of HiGHS is fine with both files.

[jeffreydeankelly2]

Thanks, I turned on all of the logging settings to the highest numbers and here is the log.

highs_debug_level = 3 mip_report_level = 2

If there are settings to set please let me know.

Running HiGHS 1.7.2 (git hash: 5ce7a2753): Copyright (c) 2024 HiGHS under
MIT licence terms
Cols:           2 lower bounds    less than or equal to       -1e+20 are
treated as -Infinity
Cols:           2 upper bounds greater than or equal to        1e+20 are
treated as +Infinity
Rows:       25170 lower bounds    less than or equal to       -1e+20 are
treated as -Infinity
SOLVE
Coefficient ranges:
  Matrix [1e-04, 2e+04]
  Cost   [1e+00, 1e+00]
  Bound  [5e-01, 1e+04]
  RHS    [1e+00, 2e+04]
checkOptions: Options are OK
Presolving model
27851 rows, 10067 cols, 306660 nonzeros  0s
19582 rows, 9529 cols, 288351 nonzeros  0s
15293 rows, 7648 cols, 280708 nonzeros  0s
8664 rows, 4996 cols, 266757 nonzeros  0s
4850 rows, 3084 cols, 65760 nonzeros  8s
4475 rows, 2389 cols, 63749 nonzeros  17s

Solving MIP model with:
   4475 rows
   2389 cols (639 binary, 0 integer, 790 implied int., 960 continuous)
   63749 nonzeros
         0       0         0   0.00%   1576916.666667  -inf
inf        0      0      0         0    17.2s
Coefficient ranges:
  Matrix [8e-04, 8e+05]
  Cost   [1e-03, 4e+03]
  Bound  [1e+00, 1e+07]
  RHS    [1e+00, 1e+04]
Presolving model
4475 rows, 2389 cols, 63749 nonzeros  0s
3920 rows, 2347 cols, 58996 nonzeros  0s
Presolve : Reductions: rows 3920(-555); columns 2347(-42); elements
58996(-4753)
Solving the presolved LP
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0     0.0000000000e+00 Ph1: 0(0) 0s
       2481    -1.0781024091e+06 Pr: 0(0); Du: 0(4.15668e-13) 0s
Solving the original LP from the solution after postsolve
Model   status      : Optimal
Simplex   iterations: 2481
Objective value     : -1.0781024091e+06
HiGHS run time      :          0.42
         0       0         0   0.00%   1083352.409137  -inf
inf        0      0      8      2481    17.7s
         0       0         0   0.00%   1083131.642462  -inf
inf     3004    240    230      2881    22.8s
   impl> Logistics-Feasible Solution #   1 Found with Objective Function =
   0.9094166667E+006
SOLUTIONSPOT1
 L       0       0         0   0.00%   1083021.530188  909416.666667
19.09%     3307    248    283      3026    27.0s

0.3% inactive integer columns, restarting
   impl> Logistics-Feasible Solution #   2 Found with Objective Function =
   0.9094166667E+006
SOLUTIONSPOT2
Model after restart has 3330 rows, 1930 cols (526 bin., 0 int., 735 impl.,
669 cont.), and 46240 nonzeros
         0       0         0   0.00%   1080844.033306  909416.666667
18.85%      174      0      0      4861    37.0s
Coefficient ranges:
  Matrix [5e-04, 8e+05]
  Cost   [1e-03, 4e+03]
  Bound  [1e+00, 1e+07]
  RHS    [1e+00, 3e+05]
Solving LP without presolve, or with basis, or unconstrained
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0    -1.5444870160e+09 Ph1: 1962(1.91759e+11); Du:
45(1.54449e+09) 1s
        685    -1.0633911832e+06 Pr: 0(0); Du: 0(9.23706e-14) 1s
Model   status      : Optimal
Simplex   iterations: 685
Objective value     : -1.0633911832e+06
HiGHS run time      :          1.48
         0       0         0   0.00%   1068641.18325   909416.666667
17.51%      174     52      3      5603    37.3s
         0       0         0   0.00%   1068010.097849  909416.666667
17.44%     6171    323     83      8494    44.0s
   impl> Logistics-Feasible Solution #   3 Found with Objective Function =
   0.9094166667E+006
SOLUTIONSPOT3
       677     532         1  50.00%   981770.731297   909416.666667
 7.96%     6232    188   1296     37054    70.1s
   impl> Logistics-Feasible Solution #   4 Found with Objective Function =
   0.9153166667E+006
SOLUTIONSPOT4
 T     687     406        11  50.00%   981770.731297   915316.666667
 7.26%     8794    233   1444     37349    71.6s
   impl> Logistics-Feasible Solution #   5 Found with Objective Function =
   0.9210166667E+006
SOLUTIONSPOT5
 T     696     406        12  62.50%   981770.731297   921016.666667
 6.60%     8800    233   1577     38423    72.4s
   impl> Logistics-Feasible Solution #   6 Found with Objective Function =
   0.9265250000E+006
SOLUTIONSPOT6
 T     700     406        13  75.00%   981770.731297   926525
5.96%     8806    233   1623     38958    73.3s
   impl> Logistics-Feasible Solution #   7 Found with Objective Function =
   0.9318500000E+006
SOLUTIONSPOT7
 T     703     406        14  87.50%   981770.731297   931850
5.36%     8809    233   1643     39536    74.3s
 impl>
 impl> MILP objective =    931850.000000000
 impl> MILP solutions =                      7
 impl> MILP status =   optimal.
 impl> MILP time =    74.6287918090820

On Sat, Aug 3, 2024 at 5:52 PM Julian Hall @.***> wrote:

You don't give all the HiGHS logging...

I can't reproduce this behaviour with v1.7.2 using gaswellrig.mps, but with gaswellrig.lp, the MIP solver seems to have stalled after the logging line

L 0 0 0 0.00% 1067812.963931 937000 13.96% 2864 351 5 8184 22.3s

I've left it to run overnight to see what happens, However, the run is still different from yours, since your presolved model has

4475 rows, 2389 cols, 63749 nonzeros 17s

and the presolved model from gaswellrig.lp has

4055 rows, 2141 cols, 53519 nonzeros 8s

The latest branch of HiGHS is fine with both files.

— Reply to this email directly, view it on GitHub https://github.com/ERGO-Code/HiGHS/issues/1865#issuecomment-2267169989, or unsubscribe https://github.com/notifications/unsubscribe-auth/ALHONEAFGXBZPDVZUOZRNLDZPVGLLAVCNFSM6AAAAABL6FSNPOVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDENRXGE3DSOJYHE . You are receiving this because you authored the thread.Message ID: @.***>

--

---

I M P L - " M a k i n g O p t i m i z a t i o n a n d E s t i m i z a t i o n S m a r t e r"

Jeffrey D. Kelly Industrial Algorithms Limited - i n d u s t r i @ l g o r i t h m s Email: @.** Phone: (647) 917-4675 (IMPL) Making Industrial AI (Algorithms & Integration) Real!*

---

This email and any files transmitted with it are confidential, proprietary and intended solely for the individual or entity to whom they are addressed. If you have received this email in error please delete it immediately.

[jajhall]

Sorry, I see the HiGHS logging in the original comment now - it's obscured by your logging. Very odd. Unfortunately the gaswellrig.lp run I left finishes with the optimal solution, but after 315s rather than 24s when starting from gaswellrig.mps

I've never seen the MIP solver do this, so I'm particularly interested in studying this. However, if I can't reproduce it locally, there's nothing I can really do to find out what's happened. Writing and reading the model files truncates doubles (in MPS) or permutes columns (.LP)

How do you pass the model to HiGHS?

If you're passing the whole model (as I suspect) rather than building it, then can you dump out the costs, column lower bounds, column upper bounds, row lower bounds, row upper bounds, and integrality vectors, plus the starts, indices and values, with the doubles in full precision?

[jeffreydeankelly2]

Thanks, here are 10 Fortran dump files for the Highs_passMIP() routine with the name of the files equal to the argument name.

The highs_header.txt contains the values for arguments 2 to 7 as the first argument is not output as it is the internal highs model pointer.

If you require further precision let me know.

highs_a_index.txt highs_a_value.txt highs_integrality.txt highs_a_start.txt highs_col_cost.txt highs_col_lower.txt highs_col_upper.txt highs_header.txt highs_row_lower.txt highs_row_upper.txt

[jajhall]

Closer, but still not there... The start of the presolve logging is the same as you observe, but there's a diversion towards the end, so the presolved model is different, and HiGHS solves the model exactly

Can you put out the doubles as hex?

Running HiGHS 1.7.2 (git hash: 4da5ad88b): Copyright (c) 2024 HiGHS under MIT licence terms Cols: 2 lower bounds less than or equal to -1e+20 are treated as -Infinity Cols: 2 upper bounds greater than or equal to 1e+20 are treated as +Infinity Rows: 25170 lower bounds less than or equal to -1e+20 are treated as -Infinity Coefficient ranges: Matrix [1e-04, 2e+04] Cost [1e+00, 1e+00] Bound [5e-01, 1e+04] RHS [1e+00, 2e+04] Presolving model 27851 rows, 10067 cols, 306660 nonzeros 0s 19582 rows, 9529 cols, 288351 nonzeros 0s 15293 rows, 7648 cols, 280708 nonzeros 0s 8664 rows, 4996 cols, 266757 nonzeros 0s 4882 rows, 3114 cols, 65933 nonzeros 2s 4471 rows, 2377 cols, 64203 nonzeros 6s

[jeffreydeankelly2]

OK, all of the double precisions are output using the Fortran write(*,"(Z20.10)") so I hope this is OK.

highs_a_value.txt highs_integrality.txt highs_a_index.txt highs_a_start.txt highs_row_lower.txt highs_row_upper.txt highs_col_cost.txt highs_col_lower.txt highs_col_upper.txt highs_header.txt

[jajhall]

Bingo! I've reproduced the bug!

Thanks

[jeffreydeankelly2]

Great - thank you for letting me know!

FYI - I have seen this in previous versions as well - sorry for being delinquent - but I don't know precisely which ones.

On Sun, Aug 4, 2024 at 2:21 PM Julian Hall @.***> wrote:

Bingo! I've reproduced the bug!

Thanks

— Reply to this email directly, view it on GitHub https://github.com/ERGO-Code/HiGHS/issues/1865#issuecomment-2267627606, or unsubscribe https://github.com/notifications/unsubscribe-auth/ALHONEAM3Y5TBECVCG5DPRLZPZWKZAVCNFSM6AAAAABL6FSNPOVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDENRXGYZDONRQGY . You are receiving this because you authored the thread.Message ID: @.***>

--

---

I M P L - " M a k i n g O p t i m i z a t i o n a n d E s t i m i z a t i o n S m a r t e r"

Jeffrey D. Kelly Industrial Algorithms Limited - i n d u s t r i @ l g o r i t h m s Email: @.** Phone: (647) 917-4675 (IMPL) Making Industrial AI (Algorithms & Integration) Real!*

---

This email and any files transmitted with it are confidential, proprietary and intended solely for the individual or entity to whom they are addressed. If you have received this email in error please delete it immediately.

[jajhall]

No problem, I understand that it's hard to chase bugs when you're busy.

[jajhall]

Perhaps I'm stating the obvious, but HiGHS terminates with a MIP gap of 0. The bug is that the dual bound has reached 931850, coinciding with the best objective value for a feasible solution

[jeffreydeankelly2]

Thanks for clarifying :-)

On Sun, Aug 4, 2024 at 4:58 PM Julian Hall @.***> wrote:

Perhaps I'm stating the obvious, but HiGHS terminates with a MIP gap of 0. The bug is that the dual bound has reached 931850, coinciding with the best objective value for a feasible solution

— Reply to this email directly, view it on GitHub https://github.com/ERGO-Code/HiGHS/issues/1865#issuecomment-2267666333, or unsubscribe https://github.com/notifications/unsubscribe-auth/ALHONECBA5DBW4NZQKJERXTZP2IVXAVCNFSM6AAAAABL6FSNPOVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDENRXGY3DMMZTGM . You are receiving this because you authored the thread.Message ID: @.***>

--

---

I M P L - " M a k i n g O p t i m i z a t i o n a n d E s t i m i z a t i o n S m a r t e r"

Jeffrey D. Kelly Industrial Algorithms Limited - i n d u s t r i @ l g o r i t h m s Email: @.** Phone: (647) 917-4675 (IMPL) Making Industrial AI (Algorithms & Integration) Real!*

---

This email and any files transmitted with it are confidential, proprietary and intended solely for the individual or entity to whom they are addressed. If you have received this email in error please delete it immediately.