Re: GLPSOL in webassemby faster than native ?

[Domingo Alvarez Duarte]

Hello Michael !

You answer is pointing correctly the issue on this thread, and that is 
the difference between libc/qsort and musl/qsort, I found it adding 
"printf" inside "src/intopt/gmigen::glp_gmi_gen" and compared 
native/wasm output and seeing the difference looked in the source of 
emscripten and found they are using musl/qsort then I've added it to my 
repository and I'm sing it instead of libc/qsort, at least this way 
we'll have a stable result on every platform (till we found a way to 
better fix this issue).

But in reality it seems that musl/qsort results in "stable sort" but 
actually for hashi.mod and tiling.mod the order of the "tie-breaker" 
results in a lot shorter solving time.

Probably a review of "glp_gmi_gen" function and others that use qsort 
with this insight can reveal a better/stable approach to calculate cuts 
(or other tasks around qsort).

====
int glp_gmi_gen(glp_prob *P, glp_prob *pool, int max_cuts)
{
...
      /* sort the list by descending fractionality */
      glp_qsort(&var[1], nv, sizeof(struct var), fcmp);
      /* try to generate cuts by one for each variable in the list, but
       * not more than max_cuts cuts */
      nnn = 0;
      for (t = 1; t <= nv; t++)
      {  len = glp_gmi_cut(P, var[t].j, ind, val, phi);
         if (len < 1)
            goto skip;
         /* if the cut inequality seems to be badly scaled, reject it
          * to avoid numerical difficulties */
         for (k = 1; k <= len; k++)
         {  if (fabs(val[k]) < GLP_GMI_GEN_TOL)
               goto skip;
            if (fabs(val[k]) > GLP_GMI_GEN_TOL2)
               goto skip;
         }
         /* add the cut to the cut pool for further consideration */
         i = glp_add_rows(pool, 1);
         glp_set_row_bnds(pool, i, GLP_LO, val[0], 0);
         glp_set_mat_row(pool, i, len, ind, val);
         /* one cut has been generated */
         /*printf("nnn %d : %d : %d : %d : %g : %g : %g\n", i, len, t, 
var[t].j, var[t].f, val[k], fabs(val[k]));*/
         nnn++;
         if (nnn == max_cuts)
            break;
skip:    ;
      }
}
====
Cheers !

On 1/10/20 19:29, Michael Hennebry wrote:
> On Thu, 1 Oct 2020, Heinrich Schuchardt wrote:
>
> > On 9/30/20 10:02 PM, Michael Hennebry wrote:
> > > On Tue, 29 Sep 2020, Domingo Alvarez Duarte wrote:
> > >
> > > > I found why GLPK in wasm was faster with "--cuts" option than native,
> > > > it was due wasm using qsort from muslc that is a "stable sort", I've
> > > > added it to my GLPK repository and running all models in the
> > > > "examples" folder only "color.mod" produces a different solution (that
> > > > seems to be valid anyway).
> >
> > My expectation is that all sort algorithms produce the same result if
> > you supply a sort key that is different for all elements.
>
> In the case of ties, tie-breaking matters.
> For a stable sort, the tie-breaker is the original position.