Re: GLPSOL in webassemby faster than native ?
Domingo Alvarez Duarte <[email protected]> Sat, 26 Sep 2020 13:42:17 +0200
| Newsgroups | gmane.comp.gnu.glpk |
|---|---|
| Message-ID | <[email protected]> |
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. >