[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: GLPSOL in webassemby faster than native ?

From: Domingo Alvarez Duarte
Subject: Re: GLPSOL in webassemby faster than native ?
Date: Thu, 1 Oct 2020 20:19:10 +0200
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.10.0

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]));*/
         if (nnn == max_cuts)
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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]