Kipp Martin wrote several papers on reformulations of linear/integer programs to obtain tighter bounds and faster optimization times. I have used some of tricks successfully in the past couple of years.
When this email from Andrew first came out, I asked Kipp if there was anything available on the web that contained his work that could be distributed to this group. He graciously created a link for us that contains Chapter 16 of a book he wrote on large-scale linear and integer optimization. This chapter discusses reformulations of the problem to get tighter bounds. I believe many people in this group would find it helpful: http://kipp.chicagobooth.edu/chapter16.pdf Thank you Kipp! -Marc -----Original Message----- From: help-glpk-bounces+marc.meketon=oliverwyman....@gnu.org [mailto:help-glpk-bounces+marc.meketon=oliverwyman....@gnu.org] On Behalf Of Andrew Makhorin Sent: Monday, October 26, 2009 9:58 AM To: help-glpk@gnu.org Subject: [Help-glpk] mip formulations and reformulations 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 ---------------------------------------------------------------------------- This e-mail and any attachments may be confidential or legally privileged. If you received this message in error or are not the intended recipient, you should destroy the e-mail message and any attachments or copies, and you are prohibited from retaining, distributing, disclosing or using any information contained herein. Please inform us of the erroneous delivery by return e-mail. Thank you for your cooperation. ---------------------------------------------------------------------------- _______________________________________________ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk