This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Dash, S. Articles by Günlük, O.

Two-Step MIR Inequalities for Mixed Integer Programs

IBM T. J. Watson Research Center, Yorktown Heights, New York 10598
School of Business, Universidad Adolfo Ibáñez, Peñalolén, 7941169 Santiago, Chile
IBM T. J. Watson Research Center, Yorktown Heights, New York 10598
sanjeebd{at}us.ibm.com
marcos.goycoolea{at}uai.cl
oktay{at}watson.ibm.com

Two-step mixed integer rounding (MIR) inequalities are valid inequalities derived from a facet of a simple mixed integer set with three variables and one constraint. In this paper we investigate how to effectively use these inequalities as cutting planes for general mixed integer problems. We study the separation problem for single-constraint sets and show that it can be solved in polynomial time when the resulting inequality is required to be sufficiently different from the associated MIR inequalities. We discuss computational issues and present numerical results based on a number of data sets.

Key words: mixed integer rounding; GMI cut; two-step MIR; group polyhedron; separation
History: received October 2007; revised June 2008; accepted March 2009.