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

[Andrew Makhorin]

Chris,

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

There is a bug in the proxy routine--it reports a wrong solution to
neos13 (please see the solver output below). The correct mip solution is
-95.474806559 while proxy reports -195.792876649. 


Andrew Makhorin


GLPSOL: GLPK LP/MIP Solver, v4.58
Parameter(s) specified in the command line:
 --fpump --proxy neos13.mps --log neos13.log
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
Pass 1
Solution found by heuristic: -54.3737134419
Pass 1
Solution found by heuristic: -61.9701251566
Pass 1
Pass 2
Pass 3
Pass 4
Pass 5
Applying PROXY heuristic...
Proxy's time limit set to 60 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.2 secs.  Memory used: 65.8 Mb
Starting proximity search...
>>>>> it:   1:   mip = -6.599752e+01;   elapsed time 11.5 sec.s
>>>>> it:   2:   mip = -6.675891e+01;   elapsed time 30.3 sec.s
>>>>> it:   3:   mip = -1.957929e+02;   elapsed time 56.5 sec.s
Proxy heuristic terminated.
Time used: 60.1.  Memory used: 86.3 Mb
Solution found by heuristic: -195.792876649
+  2109: mip =  -1.957928766e+02 >=     tree is empty   0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   85.2 secs
Memory used: 86.3 Mb (90450451 bytes)