Re: Solver performance solving examples/life_goe.mod

[Chris Matrakidis]

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 
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
>  
> 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:
> 
> .
> Find the GDB manual and other documentation resources online at:
> 
> .
>
> 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.0e+00 inf =   0.000e+00 (1152)
> *   458: obj =   1.96000e+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.
> 0x555ae48d in _glp_avl_set_node_link (node=0x0,
> link=0x55dc11c8) at misc/avl.c:170
> 170  node->link = link;
> (gdb) bt
> #0  0x555ae48d in _glp_avl_set_node_link (node=0x0,
> link=0x55dc11c8) at misc/avl.c:170
> #1  0x555898cf in _glp_ios_insert_node (tree=0x55dcca20,
> node=0x55dc11c8) at draft/glpios01.c:837
> #2  0x5558d1d5 in branch_on (T=0x55dcca20, j=95, next=2) at
> draft/glpios03.c:529
> #3  0x5558f859 in _glp_ios_driver (T=0x55dcca20) at
> draft/glpios03.c:1490
> #4  0x5558018d in solve_mip (P=0x55876e10,
> parm=0x7fffd808, P0=0x55876760, npp=0x5587c0e0)
> at draft/glpapi09.c:250
> #5  0x5558098e in preprocess_and_solve_mip (P=0x55876760,
> parm=0x7fffd808) at draft/glpapi09.c:415
> #6  0x55581855 in glp_intopt (P=0x55876760,
> parm=0x7fffd808) at draft/glpapi09.c:635
> #7  0xa97a in main (argc=3, argv=0x7fffdb88) 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 
> 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

Re: Solver performance solving examples/life_goe.mod

[Domingo Alvarez Duarte]

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 


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:
.
Find the GDB manual and other documentation resources online at:
    .

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.0e+00 inf =   0.000e+00 (1152)
*   458: obj =   1.96000e+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.
0x555ae48d in _glp_avl_set_node_link (node=0x0, 
link=0x55dc11c8) at misc/avl.c:170

170      node->link = link;
(gdb) bt
#0  0x555ae48d in _glp_avl_set_node_link (node=0x0, 
link=0x55dc11c8) at misc/avl.c:170
#1  0x555898cf in _glp_ios_insert_node (tree=0x55dcca20, 
node=0x55dc11c8) at draft/glpios01.c:837
#2  0x5558d1d5 in branch_on (T=0x55dcca20, j=95, next=2) at 
draft/glpios03.c:529
#3  0x5558f859 in _glp_ios_driver (T=0x55dcca20) at 
draft/glpios03.c:1490
#4  0x5558018d in solve_mip (P=0x55876e10, 
parm=0x7fffd808, P0=0x55876760, npp=0x5587c0e0)

    at draft/glpapi09.c:250
#5  0x5558098e in preprocess_and_solve_mip (P=0x55876760, 
parm=0x7fffd808) at draft/glpapi09.c:415
#6  0x55581855 in glp_intopt (P=0x55876760, 
parm=0x7fffd808) at draft/glpapi09.c:635
#7  0xa97a in main (argc=3, argv=0x7fffdb88) 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 
mailto: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+0

Re: Solver performance solving examples/life_goe.mod

[Domingo Alvarez Duarte]

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

Re: Solver performance solving examples/life_goe.mod

[Chris Matrakidis]

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

[Fwd: Re: Solver performance solving examples/life_goe.mod]

[Andrew Makhorin]

 Forwarded Message 
From: Jeffrey Kantor 
To: Chris Matrakidis 
Cc: Domingo Alvarez Duarte , help-glpk@gnu.org 
Subject: Re: Solver performance solving examples/life_goe.mod
Date: Sat, 26 Sep 2020 10:23:18 -0400

> Will there be a point where the GLPK package will be opened for
> collaborative development using, say, GitHub?
> 
> > On Sep 26, 2020, at 10:20 AM, 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  > .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 !
> > > 
> > > 
> > > 
> 
> 

Re: Solver performance solving examples/life_goe.mod

[Domingo Alvarez Duarte]

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

Re: Solver performance solving examples/life_goe.mod

[Chris Matrakidis]

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

Re: GLPSOL in webassemby faster than native ?

[Domingo Alvarez Duarte]

Hello !

Activating glp_long_double one by one I found that the ones that really 
makes hashi.mod with "--cuts" perform better are the ones bellow (but 
doing so degrades performance for anything else).


=

/***
*  fhv_h_solve - solve system H * x = b
*
*  This routine solves the system H * x = b, where the matrix H is the
*  middle factor of the sparse updatable FHV-factorization.
*
*  On entry the array x should contain elements of the right-hand side
*  vector b in locations x[1], ..., x[n], where n is the order of the
*  matrix H. On exit this array will contain elements of the solution
*  vector x in the same locations. */

void fhv_h_solve(FHV *fhv, glp_double x[/*1+n*/])
{ SVA *sva = fhv->luf->sva;
  int *sv_ind = sva->ind;
  glp_double *sv_val = sva->val;
  int nfs = fhv->nfs;
  int *hh_ind = fhv->hh_ind;
  int hh_ref = fhv->hh_ref;
  int *hh_ptr = &sva->ptr[hh_ref-1];
  int *hh_len = &sva->len[hh_ref-1];
  int i, k, end, ptr;
  glp_long_double x_i;
  for (k = 1; k <= nfs; k++)
  {  x_i = x[i = hh_ind[k]];
 for (end = (ptr = hh_ptr[k]) + hh_len[k]; ptr < end; ptr++)
    x_i -= sv_val[ptr] * x[sv_ind[ptr]];
 x[i] = x_i;
  }
  return;
}

/***
*  fhv_ht_solve - solve system H' * x = b
*
*  This routine solves the system H' * x = b, where H' is a matrix
*  transposed to the matrix H, which is the middle factor of the sparse
*  updatable FHV-factorization.
*
*  On entry the array x should contain elements of the right-hand side
*  vector b in locations x[1], ..., x[n], where n is the order of the
*  matrix H. On exit this array will contain elements of the solution
*  vector x in the same locations. */

void fhv_ht_solve(FHV *fhv, glp_double x[/*1+n*/])
{ SVA *sva = fhv->luf->sva;
  int *sv_ind = sva->ind;
  glp_double *sv_val = sva->val;
  int nfs = fhv->nfs;
  int *hh_ind = fhv->hh_ind;
  int hh_ref = fhv->hh_ref;
  int *hh_ptr = &sva->ptr[hh_ref-1];
  int *hh_len = &sva->len[hh_ref-1];
  int k, end, ptr;
  glp_long_double x_j;
  for (k = nfs; k >= 1; k--)
  {  if ((x_j = x[hh_ind[k]]) == 0.0)
    continue;
 for (end = (ptr = hh_ptr[k]) + hh_len[k]; ptr < end; ptr++)
    x[sv_ind[ptr]] -= sv_val[ptr] * x_j;
  }
  return;
}

=

glp_double spx_update_d_s(SPXLP *lp, glp_double d[/*1+n-m*/], int p, int q,
  const FVS *trow, const FVS *tcol)
{ /* sparse version of spx_update_d */
  int m = lp->m;
  int n = lp->n;
  glp_double *c = lp->c;
  int *head = lp->head;
  int trow_nnz = trow->nnz;
  int *trow_ind = trow->ind;
  glp_double *trow_vec = trow->vec;
  int tcol_nnz = tcol->nnz;
  int *tcol_ind = tcol->ind;
  glp_double *tcol_vec = tcol->vec;
  int i, j, k;
  glp_long_double dq; glp_double e; /*degrade performance*/
  xassert(1 <= p && p <= m);
  xassert(1 <= q && q <= n);
  xassert(trow->n == n-m);
  xassert(tcol->n == m);
  /* compute d[q] in current basis more accurately */
  k = head[m+q]; /* x[k] = xN[q] */
  dq = c[k];
  for (k = 1; k <= tcol_nnz; k++)
  {  i = tcol_ind[k];
 dq += tcol_vec[i] * c[head[i]];
  }
  /* compute relative error in d[q] */
  e = fabs(dq - d[q]) / (1.0 + fabs(dq));
  /* compute new d[q], which is the reduced cost of xB[p] in the
   * adjacent basis */
  d[q] = (dq /= tcol_vec[p]);
  /* compute new d[j] for all j != q */
  for (k = 1; k <= trow_nnz; k++)
  {  j = trow_ind[k];
 if (j != q)
    d[j] -= trow_vec[j] * dq;
  }
  return e;
}

=

Cheers !

On 24/9/20 21:18, Michael Hennebry wrote:

On Thu, 24 Sep 2020, Domingo Alvarez Duarte wrote:

I just got glpsol with "long double" working and add binaries for 
anyone that want to test then here 
https://github.com/mingodad/GLPK/releases


As noted there it'll benefit from tuning the constants in 
src/glpk_real.h


Any help/suggestion/comment is welcome !


Note that using long doubles everywhere
would slow down a memory bound computation.
Fetching more data would be required.

One might introduce glp_double_t.
C99 uses double_t for the type in which unnamed
intermediate results of double calculations are stored.

Use glp_double_t for locals that are not arrays,
especially running totals.
Do the casts to ensure that desired calculations
are actually done in glp_double_t.

Re: GLPSOL in webassemby faster than native ?

[Andrew Makhorin]

On Sat, 2020-09-26 at 09:51 +0200, Manuel Muñoz Márquez wrote:
> > Why do you want glpk to produce absolutely identical results on
> > different platforms? This has no practical sense. 
> > 
> 
> I think this is a desirable behavior. If your are solving a real
> problem it look very weird if you provides a solution using your
> computer and when you put in the user web server the system provides
> other.
> 
> Another point, is that if the calculation, and so the time required,
> depends on the platform there is no reliable way to compare "my
> results" with previous research.
> 
> Some systems, as LaTeX, work in that way. The result doesn't depend
> even the floating computation capabilities of the system CPU.
> 

In case of TeX it is important to provide identical output on any
platform, and to attain this Don implemented all calculations using
rational arithmetic. Though this approach can be used to solve, say,
linear algebra problems, it is impractical in general case. A desirable
behavior of a computer program that solves a problem with a numerical
method is to provide the result with sufficient accuracy for a
reasonable time, not more. Engineers and scientists (unlike
mathematicians and maybe accountants) as a rule are not interested in
more than 5-6 correct decimal places in numerical results.

Re: Solver performance solving examples/life_goe.mod

[Andrew Makhorin]

On Sat, 2020-09-26 at 13:54 +0200, Domingo Alvarez Duarte 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 ?

Hire 100 top-class specialists in integer programming and combinatorial
optimization, and give them 10 (or better 20) years. )))

If seriously, I think that gurobi (as well as cplex) solves many
combinatorial instances with hybrid methods other than pure branch-and-
cut. For example, glpk/examples/pbn.mod is very hard for b&c, but can be
relatively easily solved with a SAT solver.

> 
> Cheers !
> 
> 
> 

Solver performance solving examples/life_goe.mod

[Domingo Alvarez Duarte]

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 !

Re: GLPSOL in webassemby faster than native ?

[Domingo Alvarez Duarte]

Hello Michael !

I did a revision of the usage of "glp_long_double" see here 
https://github.com/mingodad/GLPK/commit/4941d1633e52b802bdc5f102715ac3db25db5245




Revised usage of glp_long_double, now it does solve hashi.mod and 
tiling.mod faster with "--cuts" option but hashi.mod without it's a lot 
slower.




- Standard glpsol  => 67.6 secs

- glpsol with some "long double" => 3.1 secs

A 20x improvement with "--cuts" and some "long double", but solving 
tiling.mod is 2x improvement, but without "--cuts" it degrades in both.


Output of normal glpsol:



/usr/bin/time glpsol2 --cuts -m hashi.mod
GLPSOL: GLPK LP/MIP Solver, v4.65
Parameter(s) specified in the command line:
 --cuts -m hashi.mod
Reading model section from hashi.mod...
168 lines were read
168 lines were read
Generating edge_sel...
Generating satisfy_vertex_demand...
Generating no_crossing1...
Generating no_crossing2...
Generating no_crossing3...
Generating no_crossing4...
Generating flow_conservation...
Generating connectivity_vub1...
Generating connectivity_vub2...
Generating cost...
Model has been successfully generated
GLPK Integer Optimizer, v4.65
2487 rows, 1264 columns, 7400 non-zeros
632 integer variables, all of which are binary
Preprocessing...
1891 rows, 1162 columns, 5802 non-zeros
530 integer variables, all of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.820e+02  ratio = 1.820e+02
GM: min|aij| =  8.270e-01  max|aij| =  1.209e+00  ratio = 1.462e+00
EQ: min|aij| =  6.930e-01  max|aij| =  1.000e+00  ratio = 1.443e+00
2N: min|aij| =  3.555e-01  max|aij| =  1.422e+00  ratio = 4.000e+00
Constructing initial basis...
Size of triangular part is 1887
Solving LP relaxation...
GLPK Simplex Optimizer, v4.65
1891 rows, 1162 columns, 5802 non-zeros
  0: obj =   0.0e+00 inf =   2.452e+03 (269)
    739: obj =   0.0e+00 inf =   1.554e-15 (0) 6
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
Long-step dual simplex will be used
Gomory's cuts enabled
MIR cuts enabled
Cover cuts enabled
Number of 0-1 knapsack inequalities = 354
Clique cuts enabled
Constructing conflict graph...
Conflict graph has 530 + 20 = 550 vertices
+   739: mip = not found yet >=  -inf (1; 0)
Cuts on level 0: gmi = 5; mir = 44; cov = 20; clq = 3;
+ 26492: mip = not found yet >=   0.0e+00 (23; 63)
+ 54641: mip = not found yet >=   0.0e+00 (15; 189)
+ 80727: mip = not found yet >=   0.0e+00 (19; 291)
+108666: mip = not found yet >=   0.0e+00 (23; 399)
+137106: mip = not found yet >=   0.0e+00 (20; 512)
+167888: mip = not found yet >=   0.0e+00 (23; 631)
+195255: mip = not found yet >=   0.0e+00 (15; 791)
+221348: mip = not found yet >=   0.0e+00 (14; 918)
+252185: mip = not found yet >=   0.0e+00 (7; 1046)
+278887: mip = not found yet >=   0.0e+00 (8; 1140)
+307555: mip = not found yet >=   0.0e+00 (13; 1239)
Time used: 60.0 secs.  Memory used: 11.7 Mb.
+336139: mip = not found yet >=   0.0e+00 (10; 1337)
+365233: mip = not found yet >=   0.0e+00 (7; 1447)
Cuts on level 32: gmi = 11; mir = 61; cov = 73; clq = 7;
+377836: >   0.0e+00 >= 0.0e+00   0.0% (14; 1517)
+377836: mip =   0.0e+00 >= tree is empty   0.0% (0; 1573)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   67.6 secs
Memory used: 12.7 Mb (13330830 bytes)

Solution:
2---2---2-2---2-2-2---2---2---2
| |
| 1-2---4=5===2 1---2---2 | 1
|   | | | | |
2-5===4-3   | | 1-4===5---1 | 1 |
  "   | "   | |   |   " |   |
  "   | "   | 1---3-1 |   " |   |
  "   | "   | |   " |   |
2-6===6=8===5---2-3---5===7-2   |
| |   | "   | |   |   " |
| 1   |   | "   | 1-2 |   |   " 1---3
| |   |   | "   |   | |   |   " |
2 |   |   5=6---4-2 | |   2---5---4---2 |
| |   |   " |   | | | |   |   "   | |
| 2---2   " |   | | | 3-3 |   " 1 | 2
| " |   | | | | " |   " | | |
| " |   4---2 | 2 |   1 " |   3 | 1 |
| " |   "   | | | |   | " |   | |   |
2   3=6-2   "   | | | |   | " 3   | |   |
|   | | "   | | | |   | " "   | |   |
|   |   1 |   2-5   | 1 | 4===3 " "   | 2---4
|   |   | |   | "   |   | | " "   | "
|   2   | 1   | "   5===4 | " 4===3 "
|   |   | | "   "   | | "   "
2   |   3---1 | "   "   | 3-5---5=2 "
|   |   | | "   "   | | |   "   "
|   |   | 2---5=7===5---3 | 1   | 1 "   1---4
|   |   | |   | |   | | |   | | "   |
2---5---3 |   |   1 | 2---1 | | |   2 | 4-2 |
    "   | |   |   | | | | | |   | | | | |
    "   | 1   |   | | |

Re: GLPSOL in webassemby faster than native ?

[Manuel Muñoz Márquez]

>Why do you want glpk to produce absolutely identical results on
> different platforms? This has no practical sense. 
> 

I think this is a desirable behavior. If your are solving a real
problem it look very weird if you provides a solution using your
computer and when you put in the user web server the system provides
other.

Another point, is that if the calculation, and so the time required,
depends on the platform there is no reliable way to compare "my
results" with previous research.

Some systems, as LaTeX, work in that way. The result doesn't depend
even the floating computation capabilities of the system CPU.

-- 
Manuel Muñoz Márquez 

>