[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: GLPSOL in webassemby faster than native ?
|
From: |
Domingo Alvarez Duarte |
|
Subject: |
Re: GLPSOL in webassemby faster than native ? |
|
Date: |
Sat, 26 Sep 2020 13:42:17 +0200 |
|
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.10.0 |
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.000000000e+00 inf = 2.452e+03 (269)
739: obj = 0.000000000e+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.000000000e+00 (23; 63)
+ 54641: mip = not found yet >= 0.000000000e+00 (15; 189)
+ 80727: mip = not found yet >= 0.000000000e+00 (19; 291)
+108666: mip = not found yet >= 0.000000000e+00 (23; 399)
+137106: mip = not found yet >= 0.000000000e+00 (20; 512)
+167888: mip = not found yet >= 0.000000000e+00 (23; 631)
+195255: mip = not found yet >= 0.000000000e+00 (15; 791)
+221348: mip = not found yet >= 0.000000000e+00 (14; 918)
+252185: mip = not found yet >= 0.000000000e+00 (7; 1046)
+278887: mip = not found yet >= 0.000000000e+00 (8; 1140)
+307555: mip = not found yet >= 0.000000000e+00 (13; 1239)
Time used: 60.0 secs. Memory used: 11.7 Mb.
+336139: mip = not found yet >= 0.000000000e+00 (10; 1337)
+365233: mip = not found yet >= 0.000000000e+00 (7; 1447)
Cuts on level 32: gmi = 11; mir = 61; cov = 73; clq = 7;
+377836: >>>>> 0.000000000e+00 >= 0.000000000e+00 0.0% (14; 1517)
+377836: mip = 0.000000000e+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 | | | | | | 2 | 2 | 1 | 3
" | | | | | | | | | | | | | "
2---6===6-----2 | 2 | 2===5 | | | | 2 | | "
| | " | | | " | | | | | | | "
| | " 1-------3 | | " 1 | 1 | | 4---3 "
| | " | | | " | | | " | "
| 4===5-----2 | | 2-----6===6-----3 | " | 3
| | | | | | " | | " | |
2 | | | 2-----1 | " | 1 " 1 |
| | | | | " | " |
| 3-----3===5===5-----4===6---7=====4---6-----4
| | | | " " " "
2 | 3===5---2 | 1 | " " " "
| | | " | | | | " " " "
| | | " | 1 | | " 3---2-----5=====5
| | | " | | | " |
2---3---3---5===4---3---3---4-----2---2-------1 |
|
1---2---2-------2---2-------2---------2---2---2
Model has been successfully processed
67.80user 0.01system 1:07.94elapsed 99%CPU (0avgtext+0avgdata
15992maxresident)k
0inputs+0outputs (0major+6867minor)pagefaults 0swaps
====
Output of glpsol with "glp_long_double == long double":
====
/usr/bin/time ./glpsol --cuts -m hashi.mod
GLPSOL: GLPK LP/MIP Solver, v4.65, glp_double size 8
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.000000000e+00 inf = 2.452e+03 (269)
765: obj = 0.000000000e+00 inf = 4.455e-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
+ 765: mip = not found yet >= -inf (1; 0)
Cuts on level 0: gmi = 10; mir = 34; cov = 19; clq = 4;
Cuts on level 33: gmi = 19; mir = 46; cov = 56; clq = 9;
+ 15815: >>>>> 0.000000000e+00 >= 0.000000000e+00 0.0% (19; 50)
+ 15815: mip = 0.000000000e+00 >= tree is empty 0.0% (0; 103)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 3.1 secs
Memory used: 11.9 Mb (12513906 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 | | | | | | 2 | 2 | 1 | 3
" | | | | | | | | | | | | | "
2---6===6-----2 | 2 | 2===5 | | | | 2 | | "
| | " | | | " | | | | | | | "
| | " 1-------3 | | " 1 | 1 | | 4---3 "
| | " | | | " | | | " | "
| 4===5-----2 | | 2-----6===6-----3 | " | 3
| | | | | | " | | " | |
2 | | | 2-----1 | " | 1 " 1 |
| | | | | " | " |
| 3-----3===5===5-----4===6---7=====4---6-----4
| | | | " " " "
2 | 3===5---2 | 1 | " " " "
| | | " | | | | " " " "
| | | " | 1 | | " 3---2-----5=====5
| | | " | | | " |
2---3---3---5===4---3---3---4-----2---2-------1 |
|
1---2---2-------2---2-------2---------2---2---2
Model has been successfully processed
3.47user 0.01system 0:03.48elapsed 99%CPU (0avgtext+0avgdata
15264maxresident)k
0inputs+0outputs (0major+4454minor)pagefaults 0swaps
====
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 ?, (continued)
- Re: GLPSOL in webassemby faster than native ?, Michael Hennebry, 2020/09/22
- Re: GLPSOL in webassemby faster than native ?, Domingo Alvarez Duarte, 2020/09/23
- Re: GLPSOL in webassemby faster than native ?, Domingo Alvarez Duarte, 2020/09/24
- Re: GLPSOL in webassemby faster than native ?, Michael Hennebry, 2020/09/24
- Re: GLPSOL in webassemby faster than native ?, Domingo Alvarez Duarte, 2020/09/25
- Re: GLPSOL in webassemby faster than native ?, Andrew Makhorin, 2020/09/25
- Re: GLPSOL in webassemby faster than native ?, Domingo Alvarez Duarte, 2020/09/25
- Re: GLPSOL in webassemby faster than native ?,
Domingo Alvarez Duarte <=
- Re: GLPSOL in webassemby faster than native ?, Michael Hennebry, 2020/09/27
- Re: GLPSOL in webassemby faster than native ?, Domingo Alvarez Duarte, 2020/09/26
- Re: GLPSOL in webassemby faster than native ?, Domingo Alvarez Duarte, 2020/09/22
- Re: GLPSOL in webassemby faster than native ?, Andrew Makhorin, 2020/09/22
- Re: GLPSOL in webassemby faster than native ?, Domingo Alvarez Duarte, 2020/09/22
- Re: GLPSOL in webassemby faster than native ?, Chris Matrakidis, 2020/09/22
- Re: GLPSOL in webassemby faster than native ?, Domingo Alvarez Duarte, 2020/09/25
- Re: GLPSOL in webassemby faster than native ?, Andrew Makhorin, 2020/09/25
- Re: GLPSOL in webassemby faster than native ?, Manuel Muñoz Márquez, 2020/09/26
- Re: GLPSOL in webassemby faster than native ?, Andrew Makhorin, 2020/09/26