Re: [Bug-glpk] Root node handling issue (and patch)

[Andrew Makhorin]

> In function ios_driver(), the root node is identified by checking
> whether the node level is zero (T->curr->level == 0). However, the
> node level may be zero even after branching if one of the branches is
> hopeless, in which case the node is reused. With the existing check,
> several procedures that are intended for the root node only are run
> again (e.g. proximity search, feasibility pump and heavy node
> preprocessing).
> 
> 
> This can be seen using neos13.mps from miplib with:
> glpsol --fpump --cuts neos13.mps
> 
> 
> The attached patch introduces a new variable "root_done" which is
> initially zero and is set to one before the first branching decision.
> All checks for the root node are replaced with !root_done, and two
> more checks are added before the calls to ios_feas_pump()
> and ios_proxy_heur() where the original checks are inside the
> functions.
> 

Fixed.

Please see a patched version attached.


Andrew Makhorin


PS: glpsol managed to solve neos13 to optimality (for about 12 mins on
my Intel Celeron 2.5 GHz):

GLPSOL: GLPK LP/MIP Solver, v4.58
Parameter(s) specified in the command line:
 --fpump --cuts --pcost neos13.mps
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...
[...]
+  7677: mip =  -9.547480656e+01 >=  -9.549197195e+01 < 0.1% (5; 1399)
+  7696: mip =  -9.547480656e+01 >=  -9.549197195e+01 < 0.1% (5; 1410)
+  7711: mip =  -9.547480656e+01 >=  -9.549197195e+01 < 0.1% (4; 1417)
+  7725: mip =  -9.547480656e+01 >=  -9.549197195e+01 < 0.1% (5; 1423)
+  7740: mip =  -9.547480656e+01 >=  -9.549197195e+01 < 0.1% (4; 1430)
+  7750: mip =  -9.547480656e+01 >=     tree is empty   0.0% (0; 1583)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   785.7 secs
Memory used: 62.9 Mb (65962477 bytes)

glpios03.c.gz
Description: GNU Zip compressed data