[Clp] initialBarrierSolve runs into an infinite loop

Henning Thielemann coinor at henning-thielemann.de
Wed Dec 6 07:18:39 EST 2023 

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 ...
-------------- next part --------------
NAME          ClpDefau
ROWS
 N  OBJROW
 L  R0000000
 L  R0000001
 L  R0000002
 L  R0000003
 L  R0000004
 L  R0000005
 G  R0000006
 L  R0000007
 L  R0000008
 G  R0000009
 L  R0000010
 G  R0000011
 G  R0000012
 L  R0000013
 L  R0000014
 L  R0000015
 L  R0000016
 G  R0000017
 G  R0000018
 L  R0000019
COLUMNS
    C0000000  OBJROW    2.          
    C0000000  R0000000   -5.        
    C0000000  R0000001  1.          
    C0000000  R0000002   -6.        
    C0000000  R0000003  5.          
    C0000000  R0000005  9.          
    C0000000  R0000007   -8.        
    C0000000  R0000008  8.          
    C0000000  R0000009   -8.        
    C0000000  R0000012   -10.       
    C0000000  R0000013   -7.        
    C0000000  R0000017   -6.        
RHS
    RHS       R0000000  85.         
    RHS       R0000001  66.         
    RHS       R0000002  88.         
    RHS       R0000003   -8.        
    RHS       R0000004  24.         
    RHS       R0000005  64.         
    RHS       R0000006  69.         
    RHS       R0000007  93.         
    RHS       R0000008  67.         
    RHS       R0000009   -34.       
    RHS       R0000010  87.         
    RHS       R0000011   -42.       
    RHS       R0000012  55.         
    RHS       R0000013  45.         
    RHS       R0000014   -1.        
    RHS       R0000015  66.         
    RHS       R0000016  51.         
    RHS       R0000017  56.         
    RHS       R0000018  78.         
    RHS       R0000019  38.         
RANGES
    RANGE     R0000000  28.         
    RANGE     R0000002  95.         
    RANGE     R0000003  75.         
    RANGE     R0000004  41.         
    RANGE     R0000005  81.         
    RANGE     R0000008  125.        
    RANGE     R0000015  39.         
BOUNDS
 LO BOUND     C0000000   -108.      
 UP BOUND     C0000000  77.         
ENDATA

More information about the Clp mailing list