[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-glpk] Proximity search bug (and patch)
From: |
Andrew Makhorin |
Subject: |
Re: [Bug-glpk] Proximity search bug (and patch) |
Date: |
Mon, 29 Feb 2016 20:42:25 +0300 |
> The do_refine() function of proximity search tries to use either
> glp_intopt() or glp_simplex() depending on whether there are any
> general integer variables left after fixing all the binary ones.
> Unfortunately, if the time limit is reached, the only check is for the
> status being GLP_UNDEF. This is OK for glp_intopt(), but if
> glp_simplex is in phase I the status will be GLP_INFEAS.
>
>
> I noticed this trying to solve neos13.mps from miplib with:
> glpsol --fpump --proxy neos13.mps
> The problem was more obvious with versions up to 4.56 where the
> returned solution is so low that the search finishes instantly. With
> version 4.57 the solution is again wrong, but the search continues and
> shows another issue (which will be the topic of a separate email).
>
>
> The attached patch modifies the error handling in do_refine() to
> account for this and to work in case the returned status is GLP_UNDEF
> or GLP_INFEAS irrespective of whether the time limit expired.
>
I fixed this bug just by adjusting the solution status appropriately on
exit from glp_simplex/glp_intopt.
Please see the attachment for a patched version.
Now the proxy heuristic seems to work correctly producing an integer
feasible solution; see the terminal output below.
Giorgio, hope you're reading this message. Could you please verify the
fragment I added to correct the solution status (lines 1017-1026)?
Thanks.
Andrew Makhorin
GLPSOL: GLPK LP/MIP Solver, v4.58
Parameter(s) specified in the command line:
--fpump --proxy 600 neos13.mps --log log --save sol
Reading problem data from 'neos13.mps'...
Problem: NEOS13
Objective: r_0
20853 rows, 1827 columns, 253854 non-zeros
1815 integer variables, all of which are binary
297396 records were read
One free row was removed
GLPK Integer Optimizer, v4.58
20852 rows, 1827 columns, 253842 non-zeros
1815 integer variables, all of which are binary
Preprocessing...
279 constraint coefficient(s) were reduced
19278 rows, 1827 columns, 234954 non-zeros
1815 integer variables, all of which are binary
Scaling...
A: min|aij| = 1.500e-05 max|aij| = 2.275e+02 ratio = 1.516e+07
GM: min|aij| = 1.027e-03 max|aij| = 9.738e+02 ratio = 9.483e+05
EQ: min|aij| = 1.055e-06 max|aij| = 1.000e+00 ratio = 9.483e+05
2N: min|aij| = 9.375e-07 max|aij| = 1.549e+00 ratio = 1.652e+06
Constructing initial basis...
Size of triangular part is 19278
Solving LP relaxation...
GLPK Simplex Optimizer, v4.58
19278 rows, 1827 columns, 234954 non-zeros
0: obj = 0.000000000e+00 inf = 1.633e+03 (1)
500: obj = 0.000000000e+00 inf = 1.133e+03 (1)
1000: obj = 0.000000000e+00 inf = 6.330e+02 (1)
1500: obj = 0.000000000e+00 inf = 1.330e+02 (1)
1633: obj = 0.000000000e+00 inf = 0.000e+00 (0)
* 2000: obj = -1.141866535e+02 inf = 0.000e+00 (3) 3
* 2109: obj = -1.261783778e+02 inf = 0.000e+00 (0) 1
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
+ 2109: mip = not found yet >= -inf (1; 0)
Applying FPUMP heuristic...
Pass 1
Solution found by heuristic: -46.3368032777
Writing MIP solution to 'sol'...
22688 lines were written
Pass 1
Solution found by heuristic: -54.3737134419
Writing MIP solution to 'sol'...
22688 lines were written
Pass 1
Solution found by heuristic: -61.9701251566
Writing MIP solution to 'sol'...
22688 lines were written
Pass 1
Pass 2
Pass 3
Pass 4
Pass 5
Applying PROXY heuristic...
Proxy's time limit set to 600 seconds.
Proxy's relative improvement set to 1.00 %.
Searching for a feasible solution...
Input solution found.
>>>>> first solution = -6.197013e+01;
Time used: 4.3 secs. Memory used: 65.8 Mb
Starting proximity search...
>>>>> it: 1: mip = -6.311341e+01; elapsed time 12.7 sec.s
>>>>> it: 2: mip = -6.390111e+01; elapsed time 27.5 sec.s
>>>>> it: 3: mip = -6.479415e+01; elapsed time 42.5 sec.s
>>>>> it: 4: mip = -6.565516e+01; elapsed time 57.6 sec.s
>>>>> it: 5: mip = -6.650058e+01; elapsed time 73.7 sec.s
>>>>> it: 6: mip = -6.736974e+01; elapsed time 98.9 sec.s
>>>>> it: 7: mip = -6.815050e+01; elapsed time 135.2 sec.s
>>>>> it: 8: mip = -6.890661e+01; elapsed time 172.1 sec.s
>>>>> it: 9: mip = -6.998742e+01; elapsed time 209.5 sec.s
>>>>> it: 10: mip = -7.111550e+01; elapsed time 254.9 sec.s
>>>>> it: 11: mip = -7.182665e+01; elapsed time 324.6 sec.s
>>>>> it: 12: mip = -7.254492e+01; elapsed time 400.9 sec.s
>>>>> it: 13: mip = -7.327037e+01; elapsed time 459.9 sec.s
>>>>> it: 14: mip = -7.400591e+01; elapsed time 480.5 sec.s
>>>>> it: 15: mip = -7.497166e+01; elapsed time 519.1 sec.s
Time limit exceeded. Proxy heuristic terminated.
Time used: 600.1. Memory used: 86.4 Mb
Solution found by heuristic: -74.9716624485
Writing MIP solution to 'sol'...
22688 lines were written
+ 2109: mip = -7.497166245e+01 >= -1.261783778e+02 68.3% (2; 0)
Time used: 622.4 secs. Memory used: 33.2 Mb.
+ 2112: mip = -7.497166245e+01 >= -1.261783778e+02 68.3% (2; 0)
+ 2114: mip = -7.497166245e+01 >= -1.261783778e+02 68.3% (2; 0)
+ 2117: mip = -7.497166245e+01 >= -1.261783778e+02 68.3% (2; 0)
[...]
proxy.c.gz
Description: GNU Zip compressed data
- Re: [Bug-glpk] Proximity search bug (and patch),
Andrew Makhorin <=