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

[Andrew Makhorin]

> 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 http://heur.uv.es/optsicom/LOLIB/ 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.