[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: Thu, 21 Jan 2010 18:26:55 +0300

> Indeed. Adding constraints to remove cycles from the solution space
> reduces the time about another 30% at the cost of increased memory
> requirements. I #39;m experimenting a bit right now, should have an
> example model ready shortly.

There are O(n^3) transitivity constraints (xij + xjk + xki <= 2), most
of which are inactive at the optimum, so row generation is very
efficient for the LOP. Moreover, transitivity constraints are
facet-inducing, so MIP formulation having only these constraints (and
irreflexivity constraints xij + xji = 1, if no preprocessing is used)
in most cases even does not require branching.

reply via email to

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