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

[Andrew Makhorin]

> I am modelling a project in which doing some tasks before others
> will save time. I think that the model is correct - but even though I
> have only entered the savings for 1 task into the objective function,
> it is taking too long to run. I believe that the problem lies in my
> "before1" and "before2" conditions, each of which contain 15^4=50625
> modelling variables. These conditions are needed to enable the
> before[] variable, where before[a,b]=1 means that task a will be
> completed before task b.

> The variable position[] is working correctly (position[5]=3 means
> that task five will be done third). I could eliminate the huge amount
> of work being done in the "before1" and "before2" conditions if I
> could make use of these position variables. Could anyone advise me how
> I can achieve the following, please?

Your problem is to find an optimal linear ordering, and it may have
many formulations depending on the objective and other constraints.

The following article may be helpful for you:

C.-H. Pan, "A study of integer programming formulations for scheduling
problems", Intl. J. of System Science, 1997, v.28, no.1, pp.33-41.
http://www.informaworld.com/smpp/content~content=a776492152&db=all