Clp icon indicating copy to clipboard operation
Clp copied to clipboard

Published 20 hours ago • verified publisher icon coin-or

Inconsistent results and long resolve times when resolving an instance with different objectives

Open akazachk opened this issue 4 years ago • 2 comments

I have an LP instance (link to instance) that is giving me some trouble, and I would like to report inconsistencies I have encountered while trying to solve the instance, and maybe someone could suggest something I should try. The instance probably has numerical issues, but it does not seem terribly unstable at first glance, though there are free variables.

I am comparing a few different Clp versions (commits bd4c4079, 51fe3bd8, and 02c5a7ef). I have tried compiling Clp with debug mode enabled and with it disabled, with similar results.

First, using the Clp standalone executable from commit 51fe3bd8 or bd4c4079, I have the following output:

Clp:import seymour1_presolved_prlp.mps.gz
At line 1 NAME          ClpDefau
At line 2 ROWS
At line 2836 COLUMNS
At line 65400 RHS
At line 65403 BOUNDS
At line 66129 ENDATA
Problem ClpDefau has 2832 rows, 789 columns and 124946 elements
Model was imported from ./seymour1_presolved_prlp.mps.gz in 0.041766 seconds
Clp:solve
Presolve 398 (-2434) rows, 117 (-672) columns and 13294 (-111652) elements
Optimal - objective value 764.98007
After Postsolve, objective 764.98007, infeasibilities - dual 0 (0), primal 0.0016743791 (139)
Presolved model was optimal, full model needs cleaning up
Optimal - objective value 764.97937
Optimal objective 764.979367 - 439 iterations time 0.072, Presolve 0.03

but using an older "Coin LP version trunk, build Jun 18 2020" (I think it is from commit 02c5a7ef), I get

Clp:import seymour1_presolved_prlp.mps.gz
At line 1 NAME          ClpDefau
At line 2 ROWS
At line 2836 COLUMNS
At line 65400 RHS
At line 65403 BOUNDS
At line 66129 ENDATA
Problem ClpDefau has 2832 rows, 789 columns and 124946 elements
Model was imported from ./seymour1_presolved_prlp.mps.gz in 0.046458 seconds
Clp:solve
Presolve 398 (-2434) rows, 117 (-672) columns and 13294 (-111652) elements
Optimal - objective value 557.91045
After Postsolve, objective 557.91045, infeasibilities - dual 0 (0), primal 0 (0)
Optimal objective 557.9104506 - 293 iterations time 0.112, Presolve 0.03

which is the correct answer, I believe --- at least it matches what Gurobi and CPLEX say.

The instability of this instance comes out most evidently when resolving it with different objectives (which is actually my use case). The following script illustrates the issue: test_seymour.cpp.zip.

Compiling and running the script with the newest Clp (bd4c4079), I observe that Clp enters a long loop before declaring the instance with an all-ones objective is dual infeasible. Something I am not able to reproduce with this short script is that, in my own code, when resolving the instance with the objective as given, Clp enters an even longer loop that does not terminate within 24 hours. Using the Clp version from commit 51fe3bd8 on July 16, the output of the test_seymour script is

Coin0008I ClpDefau read with 0 errors

Solving with inital obj.
Coin0506I Presolve 398 (-2434) rows, 117 (-672) columns and 13294 (-111652) elements
Clp0000I Optimal - objective value 764.97914
Coin0511I After Postsolve, objective 764.97914, infeasibilities - dual 0 (0), primal 0.0016840225 (127)
Coin0512I Presolved model was optimal, full model needs cleaning up
Clp0000I Optimal - objective value 764.97986
Clp0032I Optimal objective 764.9798623 - 437 iterations time 0.302, Presolve 0.10
Initial solved value: 764.979862

Solving with zero obj.
Clp0029I End of values pass after 357 iterations
Clp0006I 487  Obj 0 Primal inf 0.00078594096 (21) Dual inf 231.39616 (17)
Clp0000I Optimal - objective value 0

Resolving with all-ones obj.
Clp0006I 0  Obj 5.8560307e+11 Primal inf 0.00010077425 (11) Dual inf 6915.8025 (370) w.o. free dual inf (75)
Clp0006I 486  Obj -49.378029 Dual inf 1.0835433e+09 (89) w.o. free dual inf (72)
Clp0006I 705  Obj -164.5539 Dual inf 6.1971883e+09 (101) w.o. free dual inf (84)
Clp0006I 919  Obj -452.47193 Dual inf 3.4718261e+09 (95) w.o. free dual inf (78)
Clp0006I 1129  Obj -1105.7207 Dual inf 5.7476632e+09 (85) w.o. free dual inf (68)
Clp0006I 1320  Obj -2091.1796 Dual inf 5.4275168e+09 (89) w.o. free dual inf (72)
Clp0006I 1440  Obj -3865.0766 Dual inf 4.1590669e+10 (89) w.o. free dual inf (72)
Clp0006I 1579  Obj -54408.505 Dual inf 7.7662662e+10 (85) w.o. free dual inf (68)
Clp0006I 1634  Obj -2.2494561e+08 Primal inf 0.0053322488 (7) Dual inf 4.8355678e+14 (91) w.o. free dual inf (74)
Clp0006I 1680  Obj -8.7957869e+12 Primal inf 0.26854087 (41) Dual inf 1.4912388e+12 (111) w.o. free dual inf (93)
Clp0006I 2063  Obj -8.7871827e+12 Primal inf 0.027032342 (32) Dual inf 4.9790998e+11 (86) w.o. free dual inf (68)
Clp0006I 2505  Obj -8.3355527e+12 Primal inf 0.027103564 (41) Dual inf 2.809655e+12 (109) w.o. free dual inf (91)
Clp0006I 2893  Obj -7.768484e+12 Primal inf 0.022723528 (29) Dual inf 6.0383602e+11 (102) w.o. free dual inf (84)
Clp0006I 3326  Obj -7.3278989e+12 Primal inf 0.031029671 (53) Dual inf 1.5938084e+12 (108) w.o. free dual inf (90)
Clp0002I Dual infeasible - objective value -7.3270086e+12

Resolving with original obj.
Clp0006I 118  Obj 8476.6914 Primal inf 0.00075443391 (4) Dual inf 6.2897575e+10 (65)
Clp0006I 348  Obj 8476.7266 Primal inf 0.024203919 (20) Dual inf 3.0577582e+14 (87) w.o. free dual inf (86)
Clp0000I Optimal - objective value 8476.7305
Resolved value: 8476.730469

Another initial solve with original obj.
Clp0006I 0  Obj 8476.7227 Primal inf 0.37475653 (297) Dual inf 5.8286455e+11 (318)
Clp0029I End of values pass after 595 iterations
Clp0000I Optimal - objective value 8476.7422
Initial solved value: 8476.742188

On the other hand, with the old Clp version from commit 02c5a7ef, the initial solve gets the right objective value, but after changing the objective a couple of times then returning to the original objective, the objective value is much different, so the instability is present there as well. This is the output of the test_seymour script using the old Clp version:

Coin0008I ClpDefau read with 0 errors

Solving with inital obj.
Coin0506I Presolve 398 (-2434) rows, 117 (-672) columns and 13294 (-111652) elements
Clp0000I Optimal - objective value 557.91045
Coin0511I After Postsolve, objective 557.91045, infeasibilities - dual 0 (0), primal 0 (0)
Clp0032I Optimal objective 557.9104506 - 293 iterations time 0.282, Presolve 0.08
Initial solved value: 557.910451

Solving with zero obj.
Clp0000I Optimal - objective value 0

Resolving with all-ones obj.
Clp0006I 290  Obj 1.1985176 Dual inf 5.0941163e+09 (86) w.o. free dual inf (84)
Clp0006I 586  Obj 0.98832826 Dual inf 1.0738005e+09 (79)
Clp0006I 879  Obj -56.94733 Dual inf 3.4998675e+08 (77)
Clp0006I 1151  Obj -192.01109 Dual inf 2.2420656e+09 (90)
Clp0006I 1399  Obj -255.3583 Dual inf 9.0324258e+08 (83)
Clp0006I 1631  Obj -314.18019 Dual inf 2.5737412e+09 (84)
Clp0006I 1875  Obj -512.18192 Dual inf 3.7696918e+09 (76)
Clp0006I 2138  Obj -1632.9161 Dual inf 1.1993422e+10 (71)
Clp0006I 2338  Obj -3662.5901 Dual inf 4.6021586e+09 (60)
Clp0006I 2534  Obj -16098.738 Dual inf 6.2443758e+09 (71)
Clp0006I 2631  Obj -130459.24 Primal inf 1.2857074e-05 (5) Dual inf 6.0964272e+11 (83)
Clp0006I 2794  Obj -1.811171e+19 Primal inf 5711.8795 (5) Dual inf 2.5105766e+11 (57) w.o. free dual inf (56)
Clp0006I 2891  Obj -1.811171e+19 Primal inf 51796.716 (32) Dual inf 3.6280495e+11 (62) w.o. free dual inf (61)
Clp0006I 3020  Obj -1.811171e+19 Primal inf 12332.632 (8) Dual inf 1.3838956e+11 (59) w.o. free dual inf (58)
Clp0006I 3148  Obj -1.811171e+19 Primal inf 66304.284 (42) Dual inf 1.572774e+12 (83) w.o. free dual inf (82)
Clp0006I 3257  Obj -1.811171e+19 Primal inf 45596.511 (38) Dual inf 7.2443479e+12 (71) w.o. free dual inf (70)
Clp0006I 3339  Obj -1.811171e+19 Primal inf 47252.228 (36) Dual inf 1.1716893e+12 (79) w.o. free dual inf (78)
Clp0006I 3428  Obj -1.811171e+19 Primal inf 519.45225 (5) Dual inf 2.7722927e+11 (69) w.o. free dual inf (68)
Clp0006I 3554  Obj -1.811171e+19 Dual inf 660.09948 (74) w.o. free dual inf (73)
Clp0002I Dual infeasible - objective value -1.811171e+19

Resolving with original obj.
Clp0006I 643  Obj -96.670958 Primal inf 7.8230745e+12 (635) Dual inf 6.0395658e+13 (371) w.o. free dual inf (273)
Clp0006I 1900  Obj 120.79559 Primal inf 35814.343 (178) Dual inf 1.9684878e+13 (95) w.o. free dual inf (93)
Clp0006I 2416  Obj 114.31089 Primal inf 12311.946 (164) Dual inf 2.860656e+13 (135) w.o. free dual inf (133)
Clp0006I 2878  Obj 115.77871 Primal inf 6734.2529 (124) Dual inf 3.7561999e+12 (130) w.o. free dual inf (128)
Clp0006I 3342  Obj 116.53358 Primal inf 3624.2302 (101) Dual inf 6.3081178e+12 (115) w.o. free dual inf (113)
Clp0006I 3806  Obj 115.99163 Primal inf 2664.3917 (92) Dual inf 5.2055427e+12 (119) w.o. free dual inf (117)
Clp0006I 4137  Obj 115.42406 Primal inf 2213.3628 (70) Dual inf 2.0436752e+12 (108) w.o. free dual inf (106)
Clp0006I 4593  Obj 115.21006 Primal inf 1236.4623 (66) Dual inf 3.5605843e+12 (99) w.o. free dual inf (97)
Clp0006I 5014  Obj 116.18993 Primal inf 913.8131 (47) Dual inf 5.9365285e+11 (89) w.o. free dual inf (87)
Clp0006I 5381  Obj 118.8183 Primal inf 581.33315 (41) Dual inf 5.8510055e+11 (95) w.o. free dual inf (93)
Clp0006I 5737  Obj 119.48398 Primal inf 406.1746 (39) Dual inf 4.5399916e+11 (97) w.o. free dual inf (95)
Clp0006I 6151  Obj 113.55575 Primal inf 214.58133 (25) Dual inf 2.9825274e+11 (83) w.o. free dual inf (82)
Clp0006I 6535  Obj 113.39645 Primal inf 132.80785 (44) Dual inf 1.1017619e+12 (102) w.o. free dual inf (101)
Clp0006I 6997  Obj 113.95045 Primal inf 29.408421 (12) Dual inf 4.1815101e+11 (72) w.o. free dual inf (71)
Clp0000I Optimal - objective value 113.95053
Resolved value: 113.950531

Another initial solve with original obj.
Clp0006I 0  Obj 113.94992 Primal inf 0.0041158456 (260) Dual inf 3.2121659e+12 (269)
Clp0029I End of values pass after 530 iterations
Clp0000I Optimal - objective value 113.94955
Initial solved value: 113.949554

Any help with this would be greatly appreciated. Thank you.

akazachk avatar Aug 02 '20 22:08 akazachk

Aleksandr,

I think the problem is that the model is so nearly dual infeasible - even with original objective, that it is easy to get different optimal values. The 557 answer comes up when I do simple solves - but by switching off scaling and fiddling around, I managed to get an answer better than 557!

command line - clp seymour1_presolved_prlp.mps.gz -basisin odd.bas -scaling off -presolve off -primals At line 1 NAME ClpDefau At line 2 ROWS At line 2836 COLUMNS At line 65400 RHS At line 65403 BOUNDS At line 66129 ENDATA Problem ClpDefau has 2832 rows, 789 columns and 124946 elements Model was imported from ./seymour1_presolved_prlp.mps.gz in 0.285364 seconds At line 1 NAME ClpDefau FREEIEEE At line 724 ENDATA End of values pass after 0 iterations End of values pass after 110 iterations Optimal - objective value 525.58144 Optimal objective 525.5814369 - 110 iterations time 0.042

I will send you the basis.

John Forrest On 02/08/2020 23:31, akazachk wrote:

I have an LP instance https://github.com/coin-or/Clp/files/5012736/seymour1_presolved_prlp.mps.gz that is giving me some trouble, and I would like to report inconsistencies I have encountered while trying to solve the instance, and maybe someone could suggest something I should try. The instance probably has numerical issues, but it does not seem terribly unstable at first glance, though there are free variables.

First, using the Clp standalone executable from commit 51fe3bd https://github.com/coin-or/Clp/commit/51fe3bd8ee9ae1411bbc68ed6ab3e581d5a27457 or bd4c407 https://github.com/coin-or/Clp/commit/bd4c407973346d81ded2e9c80d4fe9b0bd78114d, I have the following output:

|Clp:import seymour1_presolved_prlp.mps.gz At line 1 NAME ClpDefau At line 2 ROWS At line 2836 COLUMNS At line 65400 RHS At line 65403 BOUNDS At line 66129 ENDATA Problem ClpDefau has 2832 rows, 789 columns and 124946 elements Model was imported from ./seymour1_presolved_prlp.mps.gz in 0.041766 seconds Clp:solve Presolve 398 (-2434) rows, 117 (-672) columns and 13294 (-111652) elements Optimal - objective value 764.98007 After Postsolve, objective 764.98007, infeasibilities - dual 0 (0), primal 0.0016743791 (139) Presolved model was optimal, full model needs cleaning up Optimal - objective value 764.97937 Optimal objective 764.979367 - 439 iterations time 0.072, Presolve 0.03 |

but using an older "Coin LP version trunk, build Jun 18 2020" (I think it is from commit 02c5a7e https://github.com/coin-or/Clp/commit/02c5a7ef5f41c87ee0f71ffb924fe4d0e8d08f46), I get

|Clp:import seymour1_presolved_prlp.mps.gz At line 1 NAME ClpDefau At line 2 ROWS At line 2836 COLUMNS At line 65400 RHS At line 65403 BOUNDS At line 66129 ENDATA Problem ClpDefau has 2832 rows, 789 columns and 124946 elements Model was imported from ./seymour1_presolved_prlp.mps.gz in 0.046458 seconds Clp:solve Presolve 398 (-2434) rows, 117 (-672) columns and 13294 (-111652) elements Optimal - objective value 557.91045 After Postsolve, objective 557.91045, infeasibilities - dual 0 (0), primal 0 (0) Optimal objective 557.9104506 - 293 iterations time 0.112, Presolve 0.03 |

which is the correct answer, I believe --- at least it matches what Gurobi and CPLEX say.

The instability of this instance comes out most evidently when resolving it with different objectives (which is actually my use case). The following script illustrates the issue: test_seymour.cpp.zip https://github.com/coin-or/Clp/files/5013066/test_seymour.cpp.zip.

Compiling and running the script with the newest Clp (bd4c407 https://github.com/coin-or/Clp/commit/bd4c407973346d81ded2e9c80d4fe9b0bd78114d), I observe that Clp enters a long loop before declaring the instance with an all-ones objective is dual infeasible. Something I am not able to reproduce with this short script is that, in my own code, when resolving the instance with the objective as given, Clp enters an even longer loop that does not terminate within 24 hours. Using the Clp version from commit 51fe3bd https://github.com/coin-or/Clp/commit/51fe3bd8ee9ae1411bbc68ed6ab3e581d5a27457 on July 16, the output of the |test_seymour| script is

|Coin0008I ClpDefau read with 0 errors Solving with inital obj. Coin0506I Presolve 398 (-2434) rows, 117 (-672) columns and 13294 (-111652) elements Clp0000I Optimal - objective value 764.97914 Coin0511I After Postsolve, objective 764.97914, infeasibilities - dual 0 (0), primal 0.0016840225 (127) Coin0512I Presolved model was optimal, full model needs cleaning up Clp0000I Optimal - objective value 764.97986 Clp0032I Optimal objective 764.9798623 - 437 iterations time 0.302, Presolve 0.10 Initial solved value: 764.979862 Solving with zero obj. Clp0029I End of values pass after 357 iterations Clp0006I 487 Obj 0 Primal inf 0.00078594096 (21) Dual inf 231.39616 (17) Clp0000I Optimal - objective value 0 Resolving with all-ones obj. Clp0006I 0 Obj 5.8560307e+11 Primal inf 0.00010077425 (11) Dual inf 6915.8025 (370) w.o. free dual inf (75) Clp0006I 486 Obj -49.378029 Dual inf 1.0835433e+09 (89) w.o. free dual inf (72) Clp0006I 705 Obj -164.5539 Dual inf 6.1971883e+09 (101) w.o. free dual inf (84) Clp0006I 919 Obj -452.47193 Dual inf 3.4718261e+09 (95) w.o. free dual inf (78) Clp0006I 1129 Obj -1105.7207 Dual inf 5.7476632e+09 (85) w.o. free dual inf (68) Clp0006I 1320 Obj -2091.1796 Dual inf 5.4275168e+09 (89) w.o. free dual inf (72) Clp0006I 1440 Obj -3865.0766 Dual inf 4.1590669e+10 (89) w.o. free dual inf (72) Clp0006I 1579 Obj -54408.505 Dual inf 7.7662662e+10 (85) w.o. free dual inf (68) Clp0006I 1634 Obj -2.2494561e+08 Primal inf 0.0053322488 (7) Dual inf 4.8355678e+14 (91) w.o. free dual inf (74) Clp0006I 1680 Obj -8.7957869e+12 Primal inf 0.26854087 (41) Dual inf 1.4912388e+12 (111) w.o. free dual inf (93) Clp0006I 2063 Obj -8.7871827e+12 Primal inf 0.027032342 (32) Dual inf 4.9790998e+11 (86) w.o. free dual inf (68) Clp0006I 2505 Obj -8.3355527e+12 Primal inf 0.027103564 (41) Dual inf 2.809655e+12 (109) w.o. free dual inf (91) Clp0006I 2893 Obj -7.768484e+12 Primal inf 0.022723528 (29) Dual inf 6.0383602e+11 (102) w.o. free dual inf (84) Clp0006I 3326 Obj -7.3278989e+12 Primal inf 0.031029671 (53) Dual inf 1.5938084e+12 (108) w.o. free dual inf (90) Clp0002I Dual infeasible - objective value -7.3270086e+12 Resolving with original obj. Clp0006I 118 Obj 8476.6914 Primal inf 0.00075443391 (4) Dual inf 6.2897575e+10 (65) Clp0006I 348 Obj 8476.7266 Primal inf 0.024203919 (20) Dual inf 3.0577582e+14 (87) w.o. free dual inf (86) Clp0000I Optimal - objective value 8476.7305 Resolved value: 8476.730469 Another initial solve with original obj. Clp0006I 0 Obj 8476.7227 Primal inf 0.37475653 (297) Dual inf 5.8286455e+11 (318) Clp0029I End of values pass after 595 iterations Clp0000I Optimal - objective value 8476.7422 Initial solved value: 8476.742188 |

On the other hand, with the old Clp version from commit 02c5a7e https://github.com/coin-or/Clp/commit/02c5a7ef5f41c87ee0f71ffb924fe4d0e8d08f46, the initial solve gets the right objective value, but after changing the objective a couple of times then returning to the original objective, the objective value is much different, so the instability is present there as well. This is the output of the |test_seymour| script using the old Clp version:

|Coin0008I ClpDefau read with 0 errors Solving with inital obj. Coin0506I Presolve 398 (-2434) rows, 117 (-672) columns and 13294 (-111652) elements Clp0000I Optimal - objective value 557.91045 Coin0511I After Postsolve, objective 557.91045, infeasibilities - dual 0 (0), primal 0 (0) Clp0032I Optimal objective 557.9104506 - 293 iterations time 0.282, Presolve 0.08 Initial solved value: 557.910451 Solving with zero obj. Clp0000I Optimal - objective value 0 Resolving with all-ones obj. Clp0006I 290 Obj 1.1985176 Dual inf 5.0941163e+09 (86) w.o. free dual inf (84) Clp0006I 586 Obj 0.98832826 Dual inf 1.0738005e+09 (79) Clp0006I 879 Obj -56.94733 Dual inf 3.4998675e+08 (77) Clp0006I 1151 Obj -192.01109 Dual inf 2.2420656e+09 (90) Clp0006I 1399 Obj -255.3583 Dual inf 9.0324258e+08 (83) Clp0006I 1631 Obj -314.18019 Dual inf 2.5737412e+09 (84) Clp0006I 1875 Obj -512.18192 Dual inf 3.7696918e+09 (76) Clp0006I 2138 Obj -1632.9161 Dual inf 1.1993422e+10 (71) Clp0006I 2338 Obj -3662.5901 Dual inf 4.6021586e+09 (60) Clp0006I 2534 Obj -16098.738 Dual inf 6.2443758e+09 (71) Clp0006I 2631 Obj -130459.24 Primal inf 1.2857074e-05 (5) Dual inf 6.0964272e+11 (83) Clp0006I 2794 Obj -1.811171e+19 Primal inf 5711.8795 (5) Dual inf 2.5105766e+11 (57) w.o. free dual inf (56) Clp0006I 2891 Obj -1.811171e+19 Primal inf 51796.716 (32) Dual inf 3.6280495e+11 (62) w.o. free dual inf (61) Clp0006I 3020 Obj -1.811171e+19 Primal inf 12332.632 (8) Dual inf 1.3838956e+11 (59) w.o. free dual inf (58) Clp0006I 3148 Obj -1.811171e+19 Primal inf 66304.284 (42) Dual inf 1.572774e+12 (83) w.o. free dual inf (82) Clp0006I 3257 Obj -1.811171e+19 Primal inf 45596.511 (38) Dual inf 7.2443479e+12 (71) w.o. free dual inf (70) Clp0006I 3339 Obj -1.811171e+19 Primal inf 47252.228 (36) Dual inf 1.1716893e+12 (79) w.o. free dual inf (78) Clp0006I 3428 Obj -1.811171e+19 Primal inf 519.45225 (5) Dual inf 2.7722927e+11 (69) w.o. free dual inf (68) Clp0006I 3554 Obj -1.811171e+19 Dual inf 660.09948 (74) w.o. free dual inf (73) Clp0002I Dual infeasible - objective value -1.811171e+19 Resolving with original obj. Clp0006I 643 Obj -96.670958 Primal inf 7.8230745e+12 (635) Dual inf 6.0395658e+13 (371) w.o. free dual inf (273) Clp0006I 1900 Obj 120.79559 Primal inf 35814.343 (178) Dual inf 1.9684878e+13 (95) w.o. free dual inf (93) Clp0006I 2416 Obj 114.31089 Primal inf 12311.946 (164) Dual inf 2.860656e+13 (135) w.o. free dual inf (133) Clp0006I 2878 Obj 115.77871 Primal inf 6734.2529 (124) Dual inf 3.7561999e+12 (130) w.o. free dual inf (128) Clp0006I 3342 Obj 116.53358 Primal inf 3624.2302 (101) Dual inf 6.3081178e+12 (115) w.o. free dual inf (113) Clp0006I 3806 Obj 115.99163 Primal inf 2664.3917 (92) Dual inf 5.2055427e+12 (119) w.o. free dual inf (117) Clp0006I 4137 Obj 115.42406 Primal inf 2213.3628 (70) Dual inf 2.0436752e+12 (108) w.o. free dual inf (106) Clp0006I 4593 Obj 115.21006 Primal inf 1236.4623 (66) Dual inf 3.5605843e+12 (99) w.o. free dual inf (97) Clp0006I 5014 Obj 116.18993 Primal inf 913.8131 (47) Dual inf 5.9365285e+11 (89) w.o. free dual inf (87) Clp0006I 5381 Obj 118.8183 Primal inf 581.33315 (41) Dual inf 5.8510055e+11 (95) w.o. free dual inf (93) Clp0006I 5737 Obj 119.48398 Primal inf 406.1746 (39) Dual inf 4.5399916e+11 (97) w.o. free dual inf (95) Clp0006I 6151 Obj 113.55575 Primal inf 214.58133 (25) Dual inf 2.9825274e+11 (83) w.o. free dual inf (82) Clp0006I 6535 Obj 113.39645 Primal inf 132.80785 (44) Dual inf 1.1017619e+12 (102) w.o. free dual inf (101) Clp0006I 6997 Obj 113.95045 Primal inf 29.408421 (12) Dual inf 4.1815101e+11 (72) w.o. free dual inf (71) Clp0000I Optimal - objective value 113.95053 Resolved value: 113.950531 Another initial solve with original obj. Clp0006I 0 Obj 113.94992 Primal inf 0.0041158456 (260) Dual inf 3.2121659e+12 (269) Clp0029I End of values pass after 530 iterations Clp0000I Optimal - objective value 113.94955 Initial solved value: 113.949554 |

Any help with this would be greatly appreciated. Thank you.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/coin-or/Clp/issues/157, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJYHHFG6TWDFWODH52GQ3R6XSNBANCNFSM4PSYTLWQ.

jjhforrest avatar Aug 03 '20 15:08 jjhforrest

@jjhforrest I think you are correct that the instance is nearly unbounded with the original objective. It seems I unintentionally cause the numerical issues. I actually intentionally set the objective parallel to the first constraint, to prevent the LP from being unbounded, since that constraint should give an explicit lower bound for the objective. However, when assigning the objective, I normalize by its 2-norm, so instead of a lower bound of 1 as in the right-hand side of the first constraint, the lower bound on the objective is approximately 557.91045062774344. Without doing that scaling, Clp does not seem to struggle, probably by avoiding errors due to numerical imprecision.

It still seems to me that something strange is going on, in that between commit 02c5a7e and the current version, the initial solve of the instance no longer obtains the "correct" objective value (equal to the 2-norm of the first constraint). Also, when I resolve this instance within my original code that generates this instance, Clp never seems to terminate.

However, this problem only occurs on one of two servers I can access, though I think I am using the same version of Clp in both cases, compiled with the same options. In case it helps, the server with the "interminable" behavior is running CentOS Linux release 7.7.1908, while the other server is Oracle Linux Server release 7.7. I am also not able to reproduce the lack of halting within a test script outside my project.

akazachk avatar Aug 04 '20 06:08 akazachk