GLPSOL in webassemby faster than native ?
Domingo Alvarez Duarte <[email protected]> Mon, 21 Sep 2020 12:16:35 +0200
| Newsgroups | gmane.comp.gnu.glpk |
|---|---|
| Message-ID | <[email protected]> |
Hello ! I'm a bit lost here, I did some changes to GLPK/GMPL here https://github.com/mingodad/GLPK/tree/local-set-param and compiled it to webassembly and made it availlable here https://meimporta.eu/myglpk-ext/ then a user (Karl) pointed out that it was segfaulting when using the "--cuts" command line extension, I looked at it and found a "xassert" with side effects that I missed in my preview review https://github.com/mingodad/GLPK/commit/9ccff77d75c7f9ecdcc94419bfc4745327235076, fixing it and rebuilding now it works but I don't know why the wasm version online can solve the "hashi.mod" in 8s on my machine but the native code takes 60s (do not seem to benefit from the --cuts parameter). I noticed that it starts with different values for the cuts: Cuts on level 0: gmi = 10; mir = 28; cov = 33; clq = 3; ///wasm Cuts on level 0: gmi = 5; mir = 44; cov = 20; clq = 3; ///native Does someone can give a possible explanation ? ==== glpsol --cuts -m hashi.mod ==== Webassembly output: ==== GLPSOL: GLPK LP/MIP Solver, v4.65 Parameter(s) specified in the command line: --cuts --math input_file Reading model section from input_file... 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 = 10; mir = 28; cov = 33; clq = 3; + 15681: mip = not found yet >= 0.000000000e+00 (17; 64) Cuts on level 36: gmi = 21; mir = 41; cov = 63; clq = 10; + 25717: >>>>> 0.000000000e+00 >= 0.000000000e+00 0.0% (29; 121) + 25717: mip = 0.000000000e+00 >= tree is empty 0.0% (0; 203) INTEGER OPTIMAL SOLUTION FOUND Time used: 7.0 secs Memory used: 10.5 Mb (10978907 bytes) ==== Native output: ==== 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; + 26286: 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) +167617: mip = not found yet >= 0.000000000e+00 (22; 631) +194581: mip = not found yet >= 0.000000000e+00 (15; 790) +220187: mip = not found yet >= 0.000000000e+00 (12; 917) +249499: mip = not found yet >= 0.000000000e+00 (8; 1039) +276819: mip = not found yet >= 0.000000000e+00 (10; 1130) +305612: mip = not found yet >= 0.000000000e+00 (13; 1226) Time used: 60.0 secs. Memory used: 11.7 Mb. +334163: mip = not found yet >= 0.000000000e+00 (9; 1333) +363890: mip = not found yet >= 0.000000000e+00 (8; 1440) 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.8 secs Memory used: 12.7 Mb (13330830 bytes) ==== Cheers !