We study the interpolation procedure of Gomory and Johnson (1972), which generates cutting planes for general integer programs from facets of cyclic group polyhedra, and has recently been re-considered by Gomory, Johnson and Evans (2003). We compare inequalities generated by this procedure with MIR inequalities and also with the two-step MIR inequalities discussed in Dash and Gunluk (2003). Our results generalize a result of Cornuéjols, Li and Vandenbussche (2003) on comparing the strength of the Gomory mixed-integer cut with related inequalities. We also show that in some cases, given an inequality generated by the interpolation procedure, one can generate stronger inequalities via the MIR principle, and a similar two-step MIR principle.
By: Sanjeeb Dash, Oktay Günlük
Published in: RC22989 in 2003
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .