ERGO-Code
HIGHS 1.7.2. MIP solver terminates prematurely due to error in dual bound
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 . . .
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.
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.
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?
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
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
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
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.
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
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.
Just downloaded and installed HIGHS 1.8.0.
We still get the inferior solution of 931850 but the global optimum is 937000 as described in the previously documented issue - see below:
The MIP gaps are the HIGHS defaults of, mip_rel_gap = 0.0001 and mip_abs_gap = 1d-06
Running HiGHS 1.8.0 (git hash: fcfb53414): 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] 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 10s 4475 rows, 2389 cols, 63749 nonzeros 20s
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 20.2s 0 0 0 0.00% 1083352.409137 -inf inf 0 0 8 2481 20.6s 0 0 0 0.00% 1083175.188266 -inf inf 2818 194 225 2776 25.9s 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 30.1s
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 40.4s 0 0 0 0.00% 1068641.18325 909416.666667 17.51% 174 52 3 5603 40.6s 0 0 0 0.00% 1068010.097849 909416.666667 17.44% 6171 323 83 8494 47.2s 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 74.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 76.5s 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 77.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 78.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 79.3s 708 0 18 100.00% 931850 931850 0.00% 8809 233 1646 39807 79.4s impl> impl> MILP objective = 931850.000000000 impl> MILP solutions = 7 impl> MILP status = optimal. impl> MILP time = 79.6895523071289
Thanks. It looks as if this was closed due to a comment typo in #1942
I've run the model again - in debug - and it triggers an assert suggesting that something numerically horrible has happened in an LP solve. I'll see if I can identify what it is, but it takes >400s to get to the assert in debug.
Fixed! Was a bad strategy in a relatively obscure scenario in the simplex solver