RE: [Help-glpk] mip formulations and reformulations

[Meketon, Marc]

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: address@hidden
[mailto:address@hidden On
Behalf Of Andrew Makhorin
Sent: Monday, October 26, 2009 9:58 AM
To: address@hidden
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.
----------------------------------------------------------------------------