[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.
>
>
>