[Top][All Lists]

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

Re: [Help-glpk] Modelling Advice Request - Project Tasks

From: Andrew Makhorin
Subject: Re: [Help-glpk] Modelling Advice Request - Project Tasks
Date: Tue, 26 Jan 2010 14:38:34 +0300

> Hi Andrew, I'm curious about how fast is the row generation
> approach? there are some randomly generated LOP instances that are
> known to be very hard, see for
> details. Can we somehow improve on their results using GLPK (probably
> quite difficult, as their code/method is problem specific)? That would
> certainly generate a lot of interests.

For t65d11xx instance (44 nodes) Jeff's model that includes all 26489
transitivity constraints takes about 85 secs on my machine, where most
of the time is spent to solve initial lp relaxation. My code which I
posted to the list solves the same instance for about one second, and
the final formulation has only 946 transitivity constraints. I think
that my code is able to solve instances having up to 100 nodes for a
reasonable time. (I successfully solved some harder instances from LOLIB.)

AFAIK, optsicom researchers are working mainly over heuristics; I have
doubts that b&c could outperform problem specific heuristic methods for
large instances.

reply via email to

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