Re: [Help-glpk] linear ordering problem again

[Yingjie Lan]

> From: Yingjie Lan <address@hidden>
> Subject: [Help-glpk] linear ordering problem again
> To: "glpk help" <address@hidden>
> Date: Saturday, February 6, 2010, 12:51 PM
> Hi Andrew,
> 
> Here is a page containing a program that specializes in
> solving the linear ordering problem (exactly, not
> heuristically). I thought it is interesting to do a
> performance comparison with GLPK.
> 
> http://perso.telecom-paristech.fr/~charon/tournament/median.html
> 
> I'd post some results later, hopefully soon.

I did a bench mark on my Mac Book, and there is more than 10% time saving with 
glpk + row generation than the well respected special method!

With the special method, solving the 22-node example on the given page: 
0.219 second (excluding the time to choose a noise method, which is about 1 
second). For more information on this special method, please also see (near the 
end of the page):

http://nyc.lti.cs.cmu.edu/IRLab/11-743f08/alad/node8.html

=========================

With the glpk + row generation, solving the same problem:

0.197 second.

There is more than 10% time saving with glpk + row generation. Cool!

@Andrew:

This line of code must be included to make the row generation work:

void callback(glp_tree *T, void *info)
{     xassert(info == info);
      if (glp_ios_reason(T) == GLP_IROWGEN)
      {  remove_inactive(T);
         //need this to make it work!!!
         if (!generate_rows()) remove_inactive(T);
      }
      return;
}

Cheers,

Yingjie