GLPSOL in webassemby faster than native ?

[Domingo Alvarez Duarte]

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 !