Re: Solver performance solving examples/life_goe.mod

Hello Chris !

I've add my fix of avl_tree to your code and compiled it and it 
segfaults due to try insert a duplicate node.

=====

gdb --args ./glpsol -m tiling.mod
GNU gdb (Ubuntu 8.2-0ubuntu1~18.04) 8.2
Copyright (C) 2018 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later 
<http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
     <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from ./glpsol...done.
(gdb) r
Starting program: GLPK-cmatraki/examples/glpsol -m tiling.mod
GLPSOL: GLPK LP/MIP Solver, v4.65
Parameter(s) specified in the command line:
  -m tiling.mod
Reading model section from tiling.mod...
Reading data section from tiling.mod...
118 lines were read
Generating covers...
Generating objeval...
Generating obj...
Model has been successfully generated
GLPK Integer Optimizer, v4.65
198 rows, 1349 columns, 8458 non-zeros
1348 integer variables, all of which are binary
Preprocessing...
196 rows, 1348 columns, 8260 non-zeros
1348 integer variables, all of which are binary
Scaling...
  A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio = 1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 196
Solving LP relaxation...
GLPK Simplex Optimizer, v4.65
196 rows, 1348 columns, 8260 non-zeros
*     0: obj =   0.000000000e+00 inf =   0.000e+00 (1152)
*   458: obj =   1.960000000e+02 inf =   1.162e-14 (0) 2
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
Long-step dual simplex will be used
Objective step = 1
+   458: mip =     not found yet <=              +inf (1; 0)

Program received signal SIGSEGV, Segmentation fault.
0x00005555555ae48d in _glp_avl_set_node_link (node=0x0, 
link=0x555555dc11c8) at misc/avl.c:170
170          node->link = link;
(gdb) bt
#0  0x00005555555ae48d in _glp_avl_set_node_link (node=0x0, 
link=0x555555dc11c8) at misc/avl.c:170
#1  0x00005555555898cf in _glp_ios_insert_node (tree=0x555555dcca20, 
node=0x555555dc11c8) at draft/glpios01.c:837
#2  0x000055555558d1d5 in branch_on (T=0x555555dcca20, j=95, next=2) at 
draft/glpios03.c:529
#3  0x000055555558f859 in _glp_ios_driver (T=0x555555dcca20) at 
draft/glpios03.c:1490
#4  0x000055555558018d in solve_mip (P=0x555555876e10, 
parm=0x7fffffffd808, P0=0x555555876760, npp=0x55555587c0e0)
     at draft/glpapi09.c:250
#5  0x000055555558098e in preprocess_and_solve_mip (P=0x555555876760, 
parm=0x7fffffffd808) at draft/glpapi09.c:415
#6  0x0000555555581855 in glp_intopt (P=0x555555876760, 
parm=0x7fffffffd808) at draft/glpapi09.c:635
#7  0x000055555555a97a in main (argc=3, argv=0x7fffffffdb88) at 
glpsol.c:1427
(gdb) q
A debugging session is active.

     Inferior 1 [process 804] will be killed.

Quit anyway? (y or n) y

=====

Cheers !

On 26/9/20 17:30, Chris Matrakidis wrote:
> A brief description of the changes is in 
> https://lists.gnu.org/archive/html/help-glpk/2018-02/msg00018.html - 
> those considerably increased the number of miplib problems that can be 
> solved, in particular using pseudocost branching. Do ask if you have 
> any specific questions, but it was some time ago so it will take me a 
> bit to dig up the details.
>
> Note that for problems like the one you are using with lots of binary 
> variables, a pre-processing technique called probing is very effective 
> but not available in GLPK. I have a draft implementation but I'm not 
> very happy with it, so it isn't committed to my tree.
>
> Best Regards,
>
> Chris Matrakids
>
> On Sat, 26 Sep 2020 at 17:55, Domingo Alvarez Duarte 
> <[email protected] <mailto:[email protected]>> wrote:
>
>     Hello Chris !
>
>     Thank you for reply !
>
>     Can you describe in a few lines what your improvements achieved ?
>
>     I've been looking at your changes and found that you've bitten by
>     "src/env/avl.c" avl_tree do not reject duplicate keys but do not
>     provide a way to recover duplicates, I fixed this here
>     https://github.com/mingodad/GLPK/commit/502da3ae23ffb4c1731cc437fd6b420ac82443d5
>     and I found it while trying to update your code to work with
>     splay_tree.
>
>     See this thread
>     https://lists.gnu.org/archive/html/bug-glpk/2020-08/msg00018.html .
>
>     Comparing your glpsol with mine solving hashi.mod we get this:
>
>     =====
>
>     # your repository compiled with  -O3 -DNDEBUG -march=native
>     -ffp-contract=off
>
>     ...
>
>     INTEGER OPTIMAL SOLUTION FOUND
>     Time used:   91.6 secs
>     Memory used: 19.6 Mb (20560460 bytes)
>
>     ...
>
>     Model has been successfully processed
>     91.72user 0.64system 1:32.37elapsed 100%CPU (0avgtext+0avgdata
>     23032maxresident)k
>     0inputs+0outputs (0major+764597minor)pagefaults 0swaps
>
>     =====
>
>     # your repository compiled with  -O2 -MT -MD -MP -MF
>
>     ...
>
>     INTEGER OPTIMAL SOLUTION FOUND
>     Time used:   120.9 secs
>     Memory used: 19.6 Mb (20560460 bytes)
>
>     ...
>
>     Model has been successfully processed
>     120.93user 1.23system 2:02.16elapsed 99%CPU (0avgtext+0avgdata
>     22900maxresident)k
>     0inputs+0outputs (0major+764575minor)pagefaults 0swaps
>
>     =====
>
>     #my repository compiled with -g -O3 -DNDEBUG -march=native
>     -ffp-contract=off -DWITH_SPLAYTREE
>
>     INTEGER OPTIMAL SOLUTION FOUND
>     Time used:   59.2 secs
>     Memory used: 10.6 Mb (11130654 bytes)
>     ...
>
>     Model has been successfully processed
>     58.99user 0.60system 0:59.59elapsed 99%CPU (0avgtext+0avgdata
>     13664maxresident)k
>     0inputs+0outputs (0major+397605minor)pagefaults 0swaps
>
>     =====
>
>     # ubuntu 18.04 glpsol package
>
>     INTEGER OPTIMAL SOLUTION FOUND
>     Time used:   70.5 secs
>     Memory used: 19.8 Mb (20725782 bytes)
>     ...
>
>     Model has been successfully processed
>     71.49user 0.22system 1:11.71elapsed 99%CPU (0avgtext+0avgdata
>     23500maxresident)k
>     0inputs+0outputs (0major+135565minor)pagefaults 0swaps
>
>     =====
>
>     Cheers !
>
>     On 26/9/20 16:20, Chris Matrakidis wrote:
>>     I made some performance improving patches a few years ago. You
>>     can find them in: https://github.com/cmatraki/GLPK
>>
>>     Best Regards,
>>
>>     Chris Matrakidis
>>
>>     On Sat, 26 Sep 2020 at 14:54, Domingo Alvarez Duarte
>>     <[email protected] <mailto:[email protected]>> wrote:
>>
>>         Hello !
>>
>>         Testing GLPK I left it solving examples/lie_goe.mod for more
>>         than 2
>>         hours and it didn't found a solution (wasm and native) then I
>>         stopped
>>         then and tried with cplex/gurobi/xpress/scip all of then gives a
>>         solution instantly (except scip that takes 3s).
>>
>>         The difference is so big, have someone managed through
>>         command line
>>         options or other means managed to get a solution quickly with
>>         glpsol ?
>>
>>         Any idea of how to improve GLPK to not be so behind ?
>>
>>         Cheers !
>>
>>