Re: Solver performance solving examples/life_goe.mod

Hello Chris !

Thank you for reply !

Please commit your "probing" code to a new branch in your repository, 
this way maybe someone can give you some help polishing it.

Also about the problem with "avl_tree" do you plan to review and fix 
your repository ?

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