Re: GLPSOL in webassemby faster than native ?

[Domingo Alvarez Duarte]

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