Re: GLPSOL in webassemby faster than native ?
Domingo Alvarez Duarte <[email protected]> Fri, 25 Sep 2020 18:07:21 +0200
| Newsgroups | gmane.comp.gnu.glpk |
|---|---|
| Message-ID | <[email protected]> |
Hello Andrew ! Something doesn't match for me, because I'm compiling GLPK/glpsol with and without optmization and get the same reported cuts: Compiled with "-O3 -DNDEBUG" ===== glpsol2 --cuts -m hashi.mod GLPSOL: GLPK LP/MIP Solver, v4.65 Parameter(s) specified in the command line: --cuts -m hashi.mod ... 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; !!!!!! ***** the same ===== Compiled with "-g" ===== ./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 ... 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; !!!!***** the same ===== Webassembly chromium: ===== GLPSOL: GLPK LP/MIP Solver, v4.65 Parameter(s) specified in the command line: --cuts --math input_fileModel 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; !!!!!***** not the same ===== Cheers ! On 22/9/20 17:56, Andrew Makhorin wrote: > On Tue, 2020-09-22 at 15:53 +0200, Domingo Alvarez Duarte wrote: >> Hello again ! >> >> On an Android phone arm7 32bits Nexux-5 with chrome browser (wasm) >> solving the "hashi.mod" with "--cuts" takes 98s and without it 909s, >> using glpsol native compiled within termux takes 497s with "--cuts" >> and >> without it 925s. > > What does "native" mean? Just changing, for example, optimization level > of the compiler may essentially change the set of generated cuts and > thus the solution time. > > >> Arm7 32bits Nexus-5: >> >> wasm "--cuts -m hashi.mod" -> 98s >> >> wasm " -m hashi.mod" -> 909s >> >> native "--cuts -m hashi.mod" -> 497s >> >> native " -m hashi.mod" -> 925s >> >> >> Laptop Linux 64bits I7: >> >> wasm "--cuts -m hashi.mod" -> 8s >> >> wasm " -m hashi.mod" -> 142s >> >> native "--cuts -m hashi.mod" -> 73s >> >> native " -m hashi.mod" -> 55s >> >> >> On arm7 "--cuts" improves the performance in both wasm and native. >> >> On x86_64 "--cuts" improves in wasm but degrade in native. >> >> I hope this could give hints to improve GLPK solver performance by >> inspecting the decision's criteria and eventually find a better ones. >> >> Anyone can give any idea with this data ? >> >> Cheers ! >> >> On 21/9/20 17:11, Andrew Makhorin wrote: >>> On Mon, 2020-09-21 at 16:09 +0200, Domingo Alvarez Duarte wrote: >>>> Hello Andrew ! >>>> >>>> Are you saying that floating point calculations are more >>>> efficient/precise in webassembly ? >>> No. I meant that due to floating-point computations running the same >>> computer program with the same data as a rule produces different >>> results >>> on different platforms. >>> >>>> Cheers ! >>>> >>>> On 21/9/20 15:08, Andrew Makhorin wrote: >>>>>> Does someone can give a possible explanation ? >>>>> floating-point computations >>