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

[Andrew Makhorin]

> 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.