[Help-glpk] mip formulations and reformulations

[Andrew Makhorin]

There had been some discussions on the list around mip's, which are
hard for glpk due to their structure, and how one could reformulate
the model to make it easier for solving. So I would like to mention
the interesting educational article "Formulations and Reformulations
in Integer Programming" by Prof. Michael Trick. The article is
publically available at http://mat.gsia.cmu.edu/trick/formul04.pdf .

I translated one of the models described in the article from Mosel to
MathProg (please see the attachment). In its initial formulation the
model is absolutely intractable for solving to optimality with glpsol.
After some reformulations suggested in the article the solution time
was reduced signficantly. However, a most amazing effect happened
after including in the model an additional redundant constraint (which
is redundant even for lp relaxation) --- glpsol could solve it to
optimality for one second.

Hope my information will be useful.


Andrew Makhorin

trick.mod
Description: MPEG movie