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
_______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
