[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 13:09:24 +0300 |
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)
- Re: [Bug-glpk] Proximity search bug (and patch),
Andrew Makhorin <=