[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] linear ordering problem again
From: |
Yingjie Lan |
Subject: |
Re: [Help-glpk] linear ordering problem again |
Date: |
Sun, 7 Feb 2010 00:42:59 -0800 (PST) |
> 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
- [Help-glpk] linear ordering problem again, Yingjie Lan, 2010/02/06
- Re: [Help-glpk] linear ordering problem again,
Yingjie Lan <=
- Re: [Help-glpk] linear ordering problem again, Andrew Makhorin, 2010/02/07
- Re: [Help-glpk] linear ordering problem again, Yingjie Lan, 2010/02/08
- Re: [Help-glpk] linear ordering problem again, Yingjie Lan, 2010/02/09
- Re: [Help-glpk] linear ordering problem again, Andrew Makhorin, 2010/02/09
- Re: [Help-glpk] linear ordering problem again, Yingjie Lan, 2010/02/09
- Re: [Help-glpk] linear ordering problem again, Andrew Makhorin, 2010/02/10
- Re: [Help-glpk] linear ordering problem again, Yingjie Lan, 2010/02/10