bug-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Bug-glpk] FPUMP heuristic pass bug GLPK4.60


From: Noli Sicad
Subject: Re: [Bug-glpk] FPUMP heuristic pass bug GLPK4.60
Date: Wed, 6 Apr 2016 20:48:04 +1000

OK. It is feature but it seems not a good feature.

I tried to modify the npass (default 5) to npass <=10 and fpump finds
a solution in npass 9 and it starts again from pass 1 to  pass 10. It
takes a long time to finish the job.


See this log (below).

Noli
~~~~~~~~~~~~~
GLPK Simplex Optimizer, v4.60
200649 rows, 20010 columns, 472459 non-zeros
      0: obj =  -0.000000000e+00 inf =   3.200e+01 (10)
     57: obj =   6.006580744e+02 inf =   2.545e-15 (0)
*   500: obj =   1.479734287e+04 inf =   2.482e-14 (4513) 4
*  1000: obj =   2.885327110e+04 inf =   2.872e-13 (6347) 4
*  1500: obj =   4.462901756e+04 inf =   7.828e-13 (6762) 4
*  2000: obj =   6.273023633e+04 inf =   1.332e-15 (7456) 5
*  2500: obj =   7.610573766e+04 inf =   9.670e-14 (7538) 4
*  3000: obj =   8.820237685e+04 inf =   4.508e-13 (8854) 4
*  3500: obj =   9.686042844e+04 inf =   2.436e-14 (9879) 5
*  4000: obj =   1.066277863e+05 inf =   9.490e-13 (8820) 4
*  4500: obj =   1.149014726e+05 inf =   1.316e-13 (8913) 5
*  5000: obj =   1.229292430e+05 inf =   8.491e-13 (9231) 4
*  5500: obj =   1.298167126e+05 inf =   2.222e-13 (7617) 5
*  6000: obj =   1.385346330e+05 inf =   3.670e-14 (7472) 5
*  6500: obj =   1.443391772e+05 inf =   7.720e-13 (7578) 4
*  7000: obj =   1.500589757e+05 inf =   1.055e-12 (8507) 5
*  7500: obj =   1.534419207e+05 inf =   5.420e-14 (8071) 5
*  8000: obj =   1.555747214e+05 inf =   1.379e-13 (9186) 4
*  8500: obj =   1.565622876e+05 inf =   5.180e-14 (7691) 5
*  9000: obj =   1.576439698e+05 inf =   2.143e-14 (6092) 4
*  9500: obj =   1.582713706e+05 inf =   5.197e-13 (5759) 4
* 10000: obj =   1.589228804e+05 inf =   2.165e-13 (4752) 4
* 10500: obj =   1.592913964e+05 inf =   5.452e-14 (4414) 5
* 11000: obj =   1.597122052e+05 inf =   4.998e-13 (3718) 4
* 11500: obj =   1.599944897e+05 inf =   1.951e-13 (4023) 4
* 12000: obj =   1.602487251e+05 inf =   4.133e-14 (5668) 5
* 12500: obj =   1.604484579e+05 inf =   9.448e-14 (2350) 4
* 13000: obj =   1.606341139e+05 inf =   5.718e-13 (6851) 4
* 13500: obj =   1.607144426e+05 inf =   2.222e-14 (2786) 5
* 14000: obj =   1.608418671e+05 inf =   4.007e-12 (1679) 4
* 14500: obj =   1.609166025e+05 inf =   1.437e-13 (4900) 5
* 15000: obj =   1.609766085e+05 inf =   3.248e-13 (2149) 4
* 15349: obj =   1.609840318e+05 inf =   2.391e-12 (0) 3
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
WARNING: LONG-STEP DUAL SIMPLEX WILL BE USED
+ 15349: mip =     not found yet <=              +inf        (1; 0)
Applying FPUMP heuristic...
Pass  1
*  2000: obj =   8.843478242e+02 inf =   0.000e+00 (156) 12
*  2142: obj =   8.843039561e+02 inf =   0.000e+00 (0) 1
Pass  2
* 43000: obj =   3.463453309e+03 inf =   1.735e-13 (6339) 11
* 43500: obj =   3.371641555e+03 inf =   5.069e-14 (7814) 4
* 44000: obj =   3.260757430e+03 inf =   1.737e-13 (4657) 4
* 44500: obj =   3.171743797e+03 inf =   3.808e-13 (4713) 5
* 45000: obj =   3.066802603e+03 inf =   8.440e-14 (4872) 4
* 45500: obj =   3.035830679e+03 inf =   2.462e-14 (3010) 5
* 45909: obj =   3.018200000e+03 inf =   1.644e-12 (0) 4
* 47500: obj =   6.547441417e+02 inf =   0.000e+00 (1441) 9
* 48000: obj =   6.517548952e+02 inf =   0.000e+00 (44) 3
* 48036: obj =   6.517312364e+02 inf =   1.954e-14 (0)
Pass  3
* 66000: obj =   3.535556535e+03 inf =   5.844e-13 (7903) 8
* 66500: obj =   3.430648489e+03 inf =   1.824e-13 (6555) 4
* 67000: obj =   3.337320950e+03 inf =   1.610e-14 (5485) 5
* 67500: obj =   3.241659543e+03 inf =   2.955e-14 (5702) 4
* 68000: obj =   3.138595185e+03 inf =   1.844e-13 (3535) 4
* 68500: obj =   3.079803408e+03 inf =   2.191e-14 (3221) 5
* 69000: obj =   3.057586745e+03 inf =   1.609e-13 (1759) 4
* 69108: obj =   3.056381944e+03 inf =   5.204e-13 (0) 1
* 70500: obj =   7.025931523e+02 inf =   0.000e+00 (5878) 8
* 71000: obj =   6.949728511e+02 inf =   0.000e+00 (297) 2
* 71308: obj =   6.936797174e+02 inf =   0.000e+00 (0) 3
Pass  4
* 84500: obj =   3.630807297e+03 inf =   1.560e-13 (10029) 12
* 85000: obj =   3.508281880e+03 inf =   2.405e-14 (5658) 4
* 85500: obj =   3.374197707e+03 inf =   9.307e-14 (5502) 4
* 86000: obj =   3.277670132e+03 inf =   1.851e-15 (6146) 5
* 86500: obj =   3.173001214e+03 inf =   1.672e-13 (3571) 4
* 87000: obj =   3.065844243e+03 inf =   8.045e-14 (3296) 4
* 87500: obj =   3.008026581e+03 inf =   1.510e-14 (3351) 5
* 88000: obj =   2.987151090e+03 inf =   1.614e-14 (3605) 4
* 88213: obj =   2.983245833e+03 inf =   2.825e-12 (0) 2
* 89500: obj =   5.647437671e+02 inf =   0.000e+00 (9210) 8
* 90000: obj =   5.546936995e+02 inf =   2.486e-14 (2732) 1
* 90486: obj =   5.490302798e+02 inf =   1.688e-12 (0) 4
Pass  5
*101000: obj =   3.438053283e+03 inf =   2.048e-14 (3447) 11
*101500: obj =   3.353459143e+03 inf =   1.700e-14 (3888) 4
*102000: obj =   3.266974515e+03 inf =   4.063e-12 (5014) 4
*102500: obj =   3.181585492e+03 inf =   1.905e-14 (3204) 5
*103000: obj =   3.096121919e+03 inf =   2.709e-14 (3569) 4
*103500: obj =   3.045494436e+03 inf =   7.576e-15 (1780) 5
*104000: obj =   3.024216151e+03 inf =   2.026e-14 (1537) 4
*104060: obj =   3.023733333e+03 inf =   1.954e-14 (0) 1
*105500: obj =   7.032086371e+02 inf =   0.000e+00 (4972) 8
*106000: obj =   6.965838191e+02 inf =   0.000e+00 (582) 3
*106208: obj =   6.961607636e+02 inf =   0.000e+00 (0) 2
Pass  6
*124500: obj =   3.529645974e+03 inf =   3.908e-15 (4094) 8
*125000: obj =   3.392675972e+03 inf =   1.290e-14 (3808) 4
*125500: obj =   3.300684314e+03 inf =   1.506e-14 (4264) 4
*126000: obj =   3.194948842e+03 inf =   2.750e-14 (5325) 4
*126500: obj =   3.117237785e+03 inf =   1.852e-13 (5160) 4
*127000: obj =   3.049107188e+03 inf =   0.000e+00 (3488) 5
*127500: obj =   3.026870051e+03 inf =   2.174e-15 (2115) 4
*127643: obj =   3.025166667e+03 inf =   8.438e-15 (0) 2
*129000: obj =   6.947317356e+02 inf =   4.459e-15 (2014) 7
*129500: obj =   6.905514611e+02 inf =   3.190e-14 (154) 2
*129656: obj =   6.899774762e+02 inf =   1.044e-12 (0) 2
*132931: obj =   6.280324362e+02 inf =   0.000e+00 (0) 3
Pass  7
*147500: obj =   3.620818112e+03 inf =   8.882e-15 (3653) 8
*148000: obj =   3.478408062e+03 inf =   9.326e-15 (3543) 4
*148500: obj =   3.390367726e+03 inf =   1.471e-14 (3618) 4
*149000: obj =   3.285377889e+03 inf =   2.115e-14 (3660) 4
*149500: obj =   3.200846127e+03 inf =   2.929e-14 (4428) 4
*150000: obj =   3.097499987e+03 inf =   5.534e-13 (4718) 4
*150500: obj =   3.068952441e+03 inf =   2.612e-13 (3005) 5
*150872: obj =   3.052700000e+03 inf =   2.220e-14 (0) 4
*152500: obj =   7.078068122e+02 inf =   3.440e-16 (3732) 8
*153000: obj =   7.036130852e+02 inf =   0.000e+00 (71) 4
*153066: obj =   7.035716973e+02 inf =   8.527e-14 (0)
Pass  8
*173000: obj =   3.522387418e+03 inf =   3.399e-14 (3699) 10
*173500: obj =   3.420715326e+03 inf =   1.959e-13 (7835) 4
*174000: obj =   3.331044332e+03 inf =   6.162e-14 (5679) 4
*174500: obj =   3.222734796e+03 inf =   1.632e-13 (3418) 4
*175000: obj =   3.149778676e+03 inf =   5.944e-13 (3541) 4
*175500: obj =   3.092377037e+03 inf =   5.037e-14 (5833) 5
*176000: obj =   3.077575000e+03 inf =   1.095e-14 (19) 5
*176121: obj =   3.076408333e+03 inf =   8.739e-13 (0) 1
*177500: obj =   6.823112207e+02 inf =   5.652e-15 (6935) 7
*178000: obj =   6.704884968e+02 inf =   1.235e-12 (5390) 3
*178500: obj =   6.670190769e+02 inf =   1.422e-14 (61) 3
*178556: obj =   6.669509133e+02 inf =   0.000e+00 (0) 1
Pass  9
*195500: obj =   3.561550342e+03 inf =   4.949e-13 (8182) 10
*196000: obj =   3.450387843e+03 inf =   1.759e-14 (5159) 4
*196500: obj =   3.362044910e+03 inf =   2.764e-13 (6702) 4
*197000: obj =   3.263245228e+03 inf =   1.283e-13 (2299) 4
*197500: obj =   3.163684521e+03 inf =   1.009e-12 (5720) 4
*198000: obj =   3.114185125e+03 inf =   2.621e-13 (4096) 5
*198500: obj =   3.067150557e+03 inf =   6.039e-13 (1540) 5
*198763: obj =   3.063922222e+03 inf =   9.888e-14 (0) 2
*200000: obj =   7.393201431e+02 inf =   7.816e-16 (2575) 7
*200500: obj =   7.260952706e+02 inf =   0.000e+00 (1600) 3
*200981: obj =   7.231072136e+02 inf =   4.245e-13 (0) 5
Solution found by heuristic: 96724.1
Pass  1
*  2000: obj =   8.843478242e+02 inf =   0.000e+00 (156) 12
*  2142: obj =   8.843039561e+02 inf =   0.000e+00 (0) 1
Solution found by heuristic: 112808.8
Pass  1
*  2000: obj =   8.843478242e+02 inf =   0.000e+00 (156) 12
*  2142: obj =   8.843039561e+02 inf =   0.000e+00 (0) 1
* 65984: obj =   1.894423549e+01 inf =   9.773e-13 (0) 9
* 70500: obj =   8.337335162e+00 inf =   0.000e+00 (142) 6
* 70605: obj =   8.335866934e+00 inf =   0.000e+00 (0)
* 72500: obj =   7.237448886e-01 inf =   5.537e-13 (201) 4
* 72794: obj =   7.115086060e-01 inf =   1.296e-11 (0)
Pass  2
* 77000: obj =   3.574563519e+03 inf =   4.384e-13 (10724) 9
* 77500: obj =   3.486895350e+03 inf =   1.275e-12 (9487) 3
* 78000: obj =   3.386136929e+03 inf =   4.405e-13 (7743) 4
* 78500: obj =   3.306930662e+03 inf =   1.388e-17 (5410) 5
* 79000: obj =   3.261288770e+03 inf =   9.300e-14 (3002) 4
* 79500: obj =   3.201179203e+03 inf =   1.982e-12 (6068) 4
* 80000: obj =   3.176571447e+03 inf =   1.008e-14 (3244) 5
* 80500: obj =   3.146841667e+03 inf =   1.827e-13 (477) 4
* 81000: obj =   3.131525990e+03 inf =   4.473e-13 (1753) 4
* 81500: obj =   3.117306484e+03 inf =   2.693e-13 (1123) 4
* 82000: obj =   3.104625000e+03 inf =   2.161e-14 (196) 5
* 82500: obj =   3.089105128e+03 inf =   5.966e-14 (1681) 4
* 82774: obj =   3.086484524e+03 inf =   2.319e-12 (0) 3
* 84500: obj =   6.807370655e+02 inf =   1.436e-14 (2466) 10
* 85000: obj =   6.774337169e+02 inf =   1.506e-14 (3637) 2
* 85500: obj =   6.742958452e+02 inf =   4.443e-15 (1809) 2
* 86000: obj =   6.734087679e+02 inf =   1.776e-15 (1105) 2
* 86500: obj =   6.729848789e+02 inf =   7.835e-15 (6) 2
* 86506: obj =   6.729848789e+02 inf =   2.154e-12 (0)
Pass  3
*102500: obj =   4.036652977e+03 inf =   9.853e-14 (8186) 9
*103000: obj =   3.911663435e+03 inf =   1.805e-13 (7636) 3
*103500: obj =   3.789441840e+03 inf =   6.132e-14 (9400) 4
*104000: obj =   3.651799559e+03 inf =   5.329e-15 (6997) 5
*104500: obj =   3.548705063e+03 inf =   1.645e-14 (7632) 4
*105000: obj =   3.444517495e+03 inf =   3.203e-13 (7430) 3
*105500: obj =   3.355092681e+03 inf =   3.965e-14 (5831) 4
*106000: obj =   3.254394825e+03 inf =   6.537e-14 (8374) 4
*106500: obj =   3.153097376e+03 inf =   2.043e-14 (6667) 4
*107000: obj =   3.071270902e+03 inf =   4.634e-13 (3724) 4
*107500: obj =   3.035628422e+03 inf =   5.107e-15 (6277) 5
*108000: obj =   3.009053456e+03 inf =   1.451e-15 (3876) 4
*108500: obj =   3.000009099e+03 inf =   1.861e-13 (1204) 4
*108583: obj =   2.999287037e+03 inf =   9.575e-13 (0) 1
*110000: obj =   7.264268067e+02 inf =   1.507e-13 (5206) 8
*110500: obj =   7.229235614e+02 inf =   9.484e-14 (2121) 2
*111000: obj =   7.212339294e+02 inf =   1.148e-13 (2575) 2
*111500: obj =   7.203754194e+02 inf =   4.011e-13 (252) 2
*111634: obj =   7.203502651e+02 inf =   4.095e-12 (0) 1
Pass  4
*118500: obj =   4.011731555e+03 inf =   1.155e-14 (6865) 12
*119000: obj =   3.863647835e+03 inf =   7.242e-14 (7864) 3
*119500: obj =   3.745739856e+03 inf =   5.193e-14 (8118) 4
*120000: obj =   3.639904515e+03 inf =   3.398e-14 (7197) 4
*120500: obj =   3.546518187e+03 inf =   1.213e-13 (8168) 4
*121000: obj =   3.455773881e+03 inf =   6.507e-13 (10015) 4
*121500: obj =   3.371357144e+03 inf =   1.786e-14 (5592) 5
*122000: obj =   3.274600833e+03 inf =   4.889e-14 (7993) 4
*122500: obj =   3.195516534e+03 inf =   7.655e-14 (6837) 4
*123000: obj =   3.089727428e+03 inf =   5.835e-13 (6354) 4
*123500: obj =   3.030126871e+03 inf =   9.650e-14 (6644) 4
*124000: obj =   2.994452717e+03 inf =   2.710e-14 (3228) 5
*124423: obj =   2.988922222e+03 inf =   1.354e-14 (0) 4
*126000: obj =   7.214434928e+02 inf =   9.689e-16 (2832) 8
*126500: obj =   7.190882843e+02 inf =   4.051e-15 (7995) 1
*127000: obj =   7.173414460e+02 inf =   9.438e-14 (1035) 2
*127358: obj =   7.169990089e+02 inf =   5.728e-13 (0) 1
Pass  5
*162000: obj =   4.046597925e+03 inf =   1.078e-13 (10234) 8
*162500: obj =   3.908656411e+03 inf =   6.676e-14 (10516) 4
*163000: obj =   3.783475811e+03 inf =   2.011e-14 (7208) 4
*163500: obj =   3.662018420e+03 inf =   3.893e-13 (8529) 3
*164000: obj =   3.550825933e+03 inf =   3.892e-14 (6842) 5
*164500: obj =   3.449167655e+03 inf =   2.071e-14 (8505) 4
*165000: obj =   3.352239304e+03 inf =   1.547e-13 (7198) 3
*165500: obj =   3.260914087e+03 inf =   3.494e-13 (6041) 4
*166000: obj =   3.192568381e+03 inf =   8.513e-14 (6517) 4
*166500: obj =   3.113465554e+03 inf =   5.068e-13 (9295) 4
*167000: obj =   3.058693573e+03 inf =   1.572e-14 (8621) 5
*167500: obj =   3.035317595e+03 inf =   1.155e-14 (4670) 5
*167879: obj =   3.030213889e+03 inf =   2.028e-11 (0) 3
*169500: obj =   7.328615971e+02 inf =   4.918e-15 (9122) 8
*170000: obj =   7.287071697e+02 inf =   7.431e-14 (4504) 2
*170500: obj =   7.279076382e+02 inf =   1.349e-14 (1325) 2
*170862: obj =   7.274028994e+02 inf =   0.000e+00 (0) 2
Pass  6
*174500: obj =   3.940467083e+03 inf =   1.940e-13 (8589) 12
*175000: obj =   3.799945477e+03 inf =   7.122e-15 (8951) 5
*175500: obj =   3.695570374e+03 inf =   2.074e-14 (11160) 4
*176000: obj =   3.590621801e+03 inf =   5.390e-14 (6089) 3
*176500: obj =   3.489081360e+03 inf =   1.421e-14 (8795) 5
*177000: obj =   3.391313491e+03 inf =   5.524e-14 (10125) 4
*177500: obj =   3.302276296e+03 inf =   1.678e-14 (8004) 4
*178000: obj =   3.213581066e+03 inf =   3.718e-13 (7790) 4
*178500: obj =   3.122658421e+03 inf =   5.997e-13 (7369) 4
*179000: obj =   3.046287658e+03 inf =   6.973e-15 (4237) 4
*179500: obj =   2.961918257e+03 inf =   5.040e-13 (4521) 4
*180000: obj =   2.941353570e+03 inf =   9.219e-15 (4779) 5
*180137: obj =   2.940958333e+03 inf =   1.954e-14 (0) 1
*181500: obj =   7.160995862e+02 inf =   8.340e-14 (2733) 8
*182000: obj =   7.148866683e+02 inf =   3.601e-14 (1324) 1
*182500: obj =   7.136339796e+02 inf =   3.045e-14 (714) 2
*182853: obj =   7.134858457e+02 inf =   6.128e-14 (0) 2

Stopped.

Exited: 15






On 4/6/16, Andrew Makhorin <address@hidden> wrote:
>> I think FPUMP Heuristic pass routine has a bug in GLPK4.60
>>
>> When Fpump finds a solution, it loop back again to the beginning of
>> pass instead of continuing from the current npass.
>>
>> See the log below.
>>
>> Noli
>> ~~~~~~~~~
>> .
>> .
>> * 10500: obj =   1.610401485e+05 inf =   8.027e-12 (5255) 3
>> * 11000: obj =   1.611132718e+05 inf =   7.347e-12 (413) 3
>> * 11279: obj =   1.611244848e+05 inf =   1.124e-10 (0) 2
>> OPTIMAL LP SOLUTION FOUND
>> Integer optimization begins...
>> WARNING: LONG-STEP DUAL SIMPLEX WILL BE USED
>> + 11279: mip =     not found yet <=              +inf        (1; 0)
>> Applying FPUMP heuristic...
>> Pass 1
>> Pass 2
>> Solution found by heuristic: 147859.9
>> Pass 1
>> Pass 2
>> Pass 3
>> Pass 4
>> Pass 5
>> + 11279: mip =   1.478599000e+05 <=   1.611235344e+05   9.0% (2; 0)
>> Time used: 86.3 secs.  Memory used: 107.8 Mb.
>> + 11279: mip =   1.478599000e+05 <=   1.611235344e+05   9.0% (2; 0)
>> RELATIVE MIP GAP TOLERANCE REACHED; SEARCH TERMINATED
>>
>
> No, it is not a bug (it is a feature). If FPUMP has found a solution, it
> repeats the search to find a better solution until 5 successive attempts
> fail.
>
>
>



reply via email to

[Prev in Thread] Current Thread [Next in Thread]