[Clp] initialBarrierSolve runs into an infinite loop

Wed Dec 6 07:51:48 EST 2023

Giving it until having done 50 iterations and making tiny or no progress.

Another change to ClpPredictorCorrector.cpp in master
On 06/12/2023 12:18, Henning Thielemann wrote:
>
> Attached is a minimal MPS problem, where initialBarrierSolve runs into 
> an infinite loop. The problem is pretty degenerate, it has only one 
> variable and 20 constraints. However, I have already observed infinite 
> loops on real-worl problems. I hope that fixing the small problem will 
> also fix the large problems.
>
> Here is the output:
>
> $ ./dual-off-infinity
> Coin0001I At line 1 NAME          ClpDefau
> Coin0001I At line 2 ROWS
> Coin0001I At line 24 COLUMNS
> Coin0001I At line 37 RHS
> Coin0001I At line 58 RANGES
> Coin0001I At line 66 BOUNDS
> Coin0001I At line 69 ENDATA
> Coin0002I Problem ClpDefau has 20 rows, 1 columns and 11 elements
> Clp0027I Model was imported from infinite-loop.mps in 0.003309 seconds
> Coin0507I Presolve determined that the problem was infeasible with 
> tolerance of 1e-08
> Clp3003W Analysis indicates model infeasible or unbounded
> 55 elements in sparse Cholesky, flop count 806
> Clp0035I 0 Primal -31 Dual -8122 Complementarity 13572 - 0 fixed, rank 20
> Clp0035I 1 Primal -30.83143 Dual -6289.1408 Complementarity 11734.028 
> - 0 fixed, rank 20
> Clp0035I 2 Primal -29.584069 Dual -4198.6336 Complementarity 9851.4323 
> - 0 fixed, rank 20
> Clp0035I 3 Primal -27.836856 Dual -1618.4417 Complementarity 8768.2251 
> - 0 fixed, rank 20
> Clp0035I 4 Primal -27.836655 Dual -1616.4364 Complementarity 8766.2341 
> - 0 fixed, rank 20
> Clp0035I 5 Primal -27.835251 Dual -1615.9169 Complementarity 8765.8148 
> - 0 fixed, rank 20
> Clp0035I 6 Primal -27.608275 Dual -1605.2745 Complementarity 8769.6973 
> - 0 fixed, rank 20
> Clp0035I 7 Primal -25.612284 Dual -536.82002 Complementarity 7674.4448 
> - 0 fixed, rank 20
> Clp0035I 8 Primal -25.6121 Dual -536.01941 Complementarity 7673.5769 - 
> 0 fixed, rank 20
> Clp0035I 9 Primal -25.606197 Dual -536.50374 Complementarity 7671.9027 
> - 0 fixed, rank 20
> Clp0035I 10 Primal -23.016652 Dual -1393.969 Complementarity 7514.5766 
> - 0 fixed, rank 20
> Clp0035I 11 Primal -14.988718 Dual -1909.671 Complementarity 4030.3671 
> - 0 fixed, rank 20
> Clp0035I 12 Primal -14.98718 Dual -108.59585 Complementarity 3798.572 
> - 0 fixed, rank 20
> Clp0035I 13 Primal -14.987096 Dual -107.98572 Complementarity 
> 3798.0514 - 0 fixed, rank 20
> Clp0035I 14 Primal -14.986522 Dual -107.27303 Complementarity 
> 3797.9455 - 0 fixed, rank 20
> Clp0035I 15 Primal -14.90807 Dual -21.068381 Complementarity 3794.0643 
> - 0 fixed, rank 20
> Clp0035I 16 Primal -13.972942 Dual 1745.705 Complementarity 3460.6879 
> - 0 fixed, rank 20
> Clp0035I 17 Primal -13.972905 Dual 1747.214 Complementarity 3460.5322 
> - 0 fixed, rank 20
> Clp0035I 18 Primal -13.970358 Dual 1842.9667 Complementarity 3459.7773 
> - 0 fixed, rank 20
> Clp0035I 19 Primal -13.906059 Dual 33226.124 Complementarity 3428.2661 
> - 0 fixed, rank 20
> Clp0035I 20 Primal -13.906104 Dual 33354.159 Complementarity 3428.2518 
> - 0 fixed, rank 20
> Clp0035I 21 Primal -13.918538 Dual 68440.55 Complementarity 3379.2006 
> - 0 fixed, rank 20
> Clp0035I 22 Primal -13.918835 Dual 2.4567344e+08 Complementarity 
> 3223.8691 - 0 fixed, rank 20
> Clp0035I 23 Primal -13.918836 Dual 4.9011895e+08 Complementarity 
> 3177.4635 - 0 fixed, rank 20
> Clp0035I 24 Primal -13.918836 Dual 9.7770125e+08 Complementarity 
> 3177.0002 - 0 fixed, rank 20
> Clp0035I 25 Primal -13.918952 Dual 9.7767603e+08 Complementarity 
> 3001.6032 - 0 fixed, rank 19
> Clp0035I 26 Primal -13.918983 Dual 9.77616e+08 Complementarity 
> 2726.195 - 0 fixed, rank 19
> Clp0035I 27 Primal -17.18931 Dual 9.7762547e+08 Complementarity 
> 1937.6862 - 0 fixed, rank 19
> Clp0035I 28 Primal -17.1896 Dual 9.7762548e+08 Complementarity 
> 1937.1688 - 0 fixed, rank 19
> Clp0035I 29 Primal -17.252352 Dual 9.7762672e+08 Complementarity 
> 1825.3812 - 0 fixed, rank 19
> Clp0035I 30 Primal -18.185925 Dual 9.7762897e+08 Complementarity 
> 1643.6736 - 0 fixed, rank 19
> Clp0035I 31 Primal -18.185927 Dual 1.9504319e+09 Complementarity 
> 1604.3818 - 0 fixed, rank 20
> Clp0035I 32 Primal -18.185984 Dual 1.9504469e+09 Complementarity 
> 1593.5322 - 0 fixed, rank 19
> Clp0035I 33 Primal -18.185984 Dual 3.8910451e+09 Complementarity 
> 1593.1369 - 0 fixed, rank 20
> Clp0035I 34 Primal -18.186014 Dual 3.8910453e+09 Complementarity 
> 1593.0566 - 0 fixed, rank 19
> Clp0035I 35 Primal -18.190597 Dual 3.891078e+09 Complementarity 
> 1559.8329 - 0 fixed, rank 19
> Clp0035I 36 Primal -18.19062 Dual 3.8911432e+09 Complementarity 
> 1559.505 - 0 fixed, rank 19
> Clp0035I 37 Primal -18.19062 Dual 3.8912732e+09 Complementarity 
> 1559.5018 - 0 fixed, rank 19
> Clp0035I 38 Primal -18.696639 Dual 3.8912751e+09 Complementarity 
> 1461.3641 - 0 fixed, rank 18
> Clp0035I 39 Primal -18.696638 Dual 6.6075002e+10 Complementarity 
> 1453.032 - 0 fixed, rank 20
> Clp0035I 40 Primal -87185.761 Dual 5.2363357e+11 Complementarity 
> 1452.4902 - 0 fixed, rank 20
> Clp0035I 41 Primal -18.696623 Dual 5.2363357e+11 Complementarity 
> 1452.4777 - 0 fixed, rank 19
> Clp0035I 42 Primal -18.696623 Dual 3.8626661e+12 Complementarity 
> 1452.5639 - 0 fixed, rank 20
> Clp0035I 43 Primal -18.696623 Dual 3.8626665e+12 Complementarity 
> 1452.5637 - 1 fixed, rank 19
> Clp0035I 44 Primal -18.693444 Dual 1.525382e+13 Complementarity 
> 1451.4797 - 1 fixed, rank 19
> Clp0035I 45 Primal -18.693398 Dual 1.9051401e+13 Complementarity 
> 1450.8932 - 1 fixed, rank 19
> Clp0035I 46 Primal -18.693519 Dual 1.9051424e+13 Complementarity 
> 1439.3911 - 1 fixed, rank 18
> Clp0035I 47 Primal -18.69352 Dual 1.9056301e+13 Complementarity 
> 1429.7395 - 1 fixed, rank 18
> Clp0035I 48 Primal -18.693363 Dual 4.1627754e+14 Complementarity 
> 1371.7534 - 1 fixed, rank 18
> Clp0035I 49 Primal -18.693346 Dual 4.1628235e+14 Complementarity 
> 1371.6507 - 1 fixed, rank 19
> Clp0035I 50 Primal -18.693402 Dual 4.1628235e+14 Complementarity 
> 982.78587 - 1 fixed, rank 17
> Clp0035I 51 Primal -18.693415 Dual 5.0568631e+14 Complementarity 
> 899.19953 - 1 fixed, rank 18
> Clp0035I 52 Primal -18.697784 Dual 5.0568742e+14 Complementarity 
> 895.56822 - 1 fixed, rank 17
> Clp0035I 53 Primal -18.697773 Dual 5.0569121e+14 Complementarity 
> 892.26396 - 1 fixed, rank 18
> Clp0035I 54 Primal -20.939978 Dual 5.0568828e+14 Complementarity 
> 657.8238 - 1 fixed, rank 17
> Clp0035I 55 Primal -20.933986 Dual 5.0573407e+14 Complementarity 
> 649.21558 - 1 fixed, rank 19
> Clp0035I 56 Primal -20.933985 Dual 5.0573458e+14 Complementarity 
> 649.05419 - 1 fixed, rank 19
> Clp0035I 57 Primal -20.933986 Dual 5.0574296e+14 Complementarity 
> 585.84092 - 1 fixed, rank 18
> Clp0035I 58 Primal -20.934217 Dual 5.0574298e+14 Complementarity 
> 579.83037 - 1 fixed, rank 17
> Clp0035I 59 Primal -20.950643 Dual 5.0574292e+14 Complementarity 
> 580.40797 - 1 fixed, rank 17
> Clp0035I 60 Primal -22.59587 Dual 5.0573694e+14 Complementarity 
> 484.36082 - 1 fixed, rank 17
> Clp0035I 61 Primal -22.606512 Dual 5.0432566e+14 Complementarity 
> 484.73628 - 1 fixed, rank 18
> Clp0035I 62 Primal -22.606526 Dual -2.6350238e+27 Complementarity 
> 8.3715132e+24 - 1 fixed, rank 20
> Clp0035I 63 Primal -22.606526 Dual -2.6350238e+27 Complementarity 
> 8.3715132e+24 - 1 fixed, rank 17
> Clp0035I 64 Primal -22.606526 Dual -2.6350238e+27 Complementarity 
> 8.3715132e+24 - 1 fixed, rank 18
> Clp0035I 65 Primal -22.606526 Dual -2.6350238e+27 Complementarity 
> 8.3715132e+24 - 1 fixed, rank 17
> Clp0035I 66 Primal -22.606526 Dual -2.6350238e+27 Complementarity 
> 8.3715132e+24 - 1 fixed, rank 18
> Clp0035I 67 Primal -22.606526 Dual -2.6350144e+27 Complementarity 
> 8.3715132e+24 - 1 fixed, rank 19
> Clp0035I 68 Primal -22.606526 Dual -2.6349955e+27 Complementarity 
> 8.3715132e+24 - 1 fixed, rank 19
> Clp0035I 69 Primal -22.606527 Dual -2.6271469e+27 Complementarity 
> 8.3715132e+24 - 1 fixed, rank 20
> Clp0035I 70 Primal -2.6187651e+27 Dual -2.6271375e+27 Complementarity 
> 8.3715132e+24 - 1 fixed, rank 20
> Clp0035I 71 Primal -2.6187651e+27 Dual -2.6271469e+27 Complementarity 
> 8.3715132e+24 - 1 fixed, rank 20
> Clp0035I 72 Primal -2.6187651e+27 Dual -2.6271375e+27 Complementarity 
> 8.3715132e+24 - 1 fixed, rank 20
> Clp0035I 73 Primal -2.6187651e+27 Dual -2.6271469e+27 Complementarity 
> 8.3715132e+24 - 1 fixed, rank 20
> Clp0035I 74 Primal -2.6187651e+27 Dual -2.6271469e+27 Complementarity 
> 8.3715132e+24 - 1 fixed, rank 20
> Clp0035I 75 Primal -2.6187651e+27 Dual -2.6271469e+27 Complementarity 
> 8.3715132e+24 - 1 fixed, rank 20
> Clp0035I 76 Primal -2.6187651e+27 Dual -2.6271469e+27 Complementarity 
> 8.3715132e+24 - 1 fixed, rank 20
> Clp0035I 77 Primal -2.6187651e+27 Dual -2.6271469e+27 Complementarity 
> 8.3715133e+24 - 1 fixed, rank 20
> Clp0035I 78 Primal -22.606357 Dual 4.635043e+30 Complementarity 
> 8.3715142e+24 - 1 fixed, rank 19
> Clp0035I 79 Primal -22.604971 Dual 3.0483285e+31 Complementarity 
> 8.3715142e+24 - 1 fixed, rank 19
> Clp0035I 80 Primal -22.604971 Dual 9.3472537e+31 Complementarity 
> 8.3715141e+24 - 1 fixed, rank 20
> Clp0035I 81 Primal 9.3472545e+31 Dual 9.3472537e+31 Complementarity 
> 8.3715141e+24 - 1 fixed, rank 20
> Clp0035I 82 Primal -22.566045 Dual 8.2441428e+38 Complementarity 
> 8.4424286e+22 - 1 fixed, rank 19
> Clp0035I 83 Primal -21.852384 Dual 1.6877149e+39 Complementarity 
> 1.1610013e+17 - 1 fixed, rank 19
> Clp0035I 84 Primal -18.588534 Dual 2.1514563e+39 Complementarity 
> 7.5974628e+16 - 1 fixed, rank 19
> Clp0035I 85 Primal -18.588126 Dual 2.1517185e+39 Complementarity 
> 7.5970491e+16 - 1 fixed, rank 19
> Clp0035I 86 Primal -18.58782 Dual 2.1519152e+39 Complementarity 
> 7.5967347e+16 - 1 fixed, rank 19
> Clp0035I 87 Primal -18.587591 Dual 2.1520629e+39 Complementarity 
> 7.596495e+16 - 1 fixed, rank 19
> Clp0035I 88 Primal -18.586902 Dual 3.5769439e+39 Complementarity 
> 6.0764771e+16 - 1 fixed, rank 19
> Clp0035I 89 Primal -16.222803 Dual 5.0007306e+39 Complementarity 
> 2.6619335e+16 - 1 fixed, rank 18
> Clp0035I 90 Primal -15.092384 Dual 7.1195361e+39 Complementarity 
> 8.0112657e+15 - 1 fixed, rank 18
> Clp0035I 91 Primal -14.50499 Dual 9.5707131e+39 Complementarity 
> 3.0783153e+14 - 2 fixed, rank 18
> Clp0035I 92 Primal -14.500005 Dual 1.1909077e+40 Complementarity 
> 3.7551821e+13 - 2 fixed, rank 18
> Clp0035I 93 Primal -14.500001 Dual 1.4201066e+40 Complementarity 
> 7.7404466e+12 - 2 fixed, rank 18
> Clp0035I 94 Primal -14.5 Dual 1.6420061e+40 Complementarity 
> 1.5564476e+12 - 2 fixed, rank 18
> Clp0035I 95 Primal -14.5 Dual 1.8814566e+40 Complementarity 
> 2.3693282e+11 - 3 fixed, rank 18
> Clp0035I 96 Primal -14.5 Dual 1.9060292e+40 Complementarity 
> 2.2044388e+11 - 5 fixed, rank 18
> Clp0035I 97 Primal -14.500621 Dual 1.9060488e+40 Complementarity 
> 2.1913671e+11 - 5 fixed, rank 16
> Clp0035I 98 Primal -14.502411 Dual 1.9061066e+40 Complementarity 
> 2.1783298e+11 - 5 fixed, rank 18
> Clp0035I 99 Primal -14.51073 Dual 2.0112325e+40 Complementarity 
> 1.3041545e+12 - 5 fixed, rank 17
> Clp0035I 100 Primal -14.510733 Dual 2.0112493e+40 Complementarity 
> 1.2939925e+12 - 5 fixed, rank 18
> Clp0035I 101 Primal -14.510613 Dual 2.0112628e+40 Complementarity 
> 1.2863667e+12 - 5 fixed, rank 18
> Clp0035I 102 Primal -14.510608 Dual 2.011263e+40 Complementarity 
> 1.2635685e+12 - 5 fixed, rank 18
> Clp0035I 103 Primal -14.510611 Dual 2.0112632e+40 Complementarity 
> 1.2635656e+12 - 6 fixed, rank 18
> Clp0035I 104 Primal -14.499269 Dual 2.0130851e+40 Complementarity 
> 1.2405551e+12 - 6 fixed, rank 19
> Clp0035I 105 Primal -14.388632 Dual 2.014138e+40 Complementarity 
> 1.2194974e+12 - 6 fixed, rank 16
> Clp0035I 106 Primal -14.369703 Dual 2.0153185e+40 Complementarity 
> 1.1985939e+12 - 6 fixed, rank 16
> Clp0035I 107 Primal -14.412168 Dual 2.0166416e+40 Complementarity 
> 1.1778262e+12 - 6 fixed, rank 15
> Clp0035I 108 Primal -14.459498 Dual 2.0181238e+40 Complementarity 
> 1.1571739e+12 - 6 fixed, rank 15
> Clp0035I 109 Primal -14.512829 Dual 2.0197833e+40 Complementarity 
> 1.1366164e+12 - 6 fixed, rank 16
> Clp0035I 110 Primal -14.171677 Dual 2.02446e+40 Complementarity 
> 1.1111706e+12 - 6 fixed, rank 17
> Clp0035I 111 Primal -14.239256 Dual 2.0265173e+40 Complementarity 
> 1.0909326e+12 - 6 fixed, rank 15
> Clp0035I 112 Primal -14.314191 Dual 2.0288164e+40 Complementarity 
> 1.0707161e+12 - 6 fixed, rank 15
> Clp0035I 113 Primal -14.324142 Dual 2.031384e+40 Complementarity 
> 1.0504966e+12 - 6 fixed, rank 16
> Clp0035I 114 Primal -14.245306 Dual 2.0342487e+40 Complementarity 
> 1.0302384e+12 - 6 fixed, rank 16
> Clp0035I 115 Primal -17.312327 Dual 2.0604787e+40 Complementarity 
> 3.2579936e+11 - 6 fixed, rank 16
> Clp0035I 116 Primal -22.799722 Dual 2.0638235e+40 Complementarity 
> 6.5876012e+10 - 6 fixed, rank 15
> Clp0035I 117 Primal 11.958707 Dual 2.0744352e+40 Complementarity 
> 5.7173104e+10 - 6 fixed, rank 16
> Clp0035I 118 Primal -14.505694 Dual 2.2206806e+40 Complementarity 
> 2.3075425e+10 - 12 fixed, rank 18
> Clp0035I 119 Primal -14.567801 Dual 2.481834e+40 Complementarity 
> 1.2394663e+08 - 12 fixed, rank 18
> Clp0035I 120 Primal -14.652461 Dual 2.739611e+40 Complementarity 
> 2195024.2 - 12 fixed, rank 18
> Clp0035I 121 Primal -14.652461 Dual 2.8661112e+40 Complementarity 
> 858523.21 - 12 fixed, rank 19
> Clp0035I 122 Primal -14.789459 Dual 3.0163162e+40 Complementarity 
> 347535.82 - 12 fixed, rank 18
> Clp0035I 123 Primal -14.509487 Dual 3.2776737e+40 Complementarity 
> 1711.9195 - 13 fixed, rank 18
> Clp0035I 124 Primal -14.35145 Dual 3.5230795e+40 Complementarity 
> 135.77599 - 13 fixed, rank 18
> Clp0035I 125 Primal -14.574429 Dual 3.5583306e+40 Complementarity 
> 64.807731 - 13 fixed, rank 18
> Clp0035I 126 Primal -14.509972 Dual 3.5583317e+40 Complementarity 
> 1091.2881 - 13 fixed, rank 18
> Clp0035I 127 Primal -16.57242 Dual 3.5583317e+40 Complementarity 
> 6.4464228e+09 - 13 fixed, rank 19
> ^C
> Aborted ...
>
> _______________________________________________
> Clp mailing list
> Clp at list.coin-or.org
> https://list.coin-or.org/mailman/listinfo/clp