The code uses the avl tree to make a priority queue, and only cares about the relative ordering of the nodes. As a matter of fact, in this specific use having duplicate keys is expected and actually quite common. The pre-existing GLPK implementation of AVL trees works fine in this case, as I never search for a specific key but only access the previous or next nodes of a given one.
Best Regards, Chris Matrakidis On Sat, 26 Sep 2020 at 19:52, Domingo Alvarez Duarte <mingo...@gmail.com> wrote: > 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> <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/> > <http://www.gnu.org/software/gdb/bugs/>. > Find the GDB manual and other documentation resources online at: > <http://www.gnu.org/software/gdb/documentation/> > <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 <mingo...@gmail.com> > 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 <mingo...@gmail.com> >> 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 ! >>> >>> >>>
