Re: [Bug-glpk] Proximity search bug (and patch)

[Andrew Makhorin]

> 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