[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Help-glpk] mip formulations and reformulations

From: Andrew Makhorin
Subject: [Help-glpk] mip formulations and reformulations
Date: Mon, 26 Oct 2009 16:58:23 +0300

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 .

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

Attachment: trick.mod
Description: MPEG movie

reply via email to

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