Two step MIR inequalities for mixed-integer programs

Sanjeeb Dash (sanjeebdus.ibm.com)
Marcos Goycoolea (mgoycoolisye.gatech.edu )
Oktay Gunluk (gunlukus.ibm.com)

Abstract: Two-step mixed-integer rounding 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 inequality. We discuss computational issues and present numerical results based on a number of data sets.

Keywords: integer programming, mixed-integer rounding, separation

Category 1: Integer Programming (Cutting Plane Approaches )

Citation:

Download: [Postscript][PDF]

Entry Submitted: 07/10/2006
Entry Accepted: 07/11/2006
Entry Last Modified: 07/12/2006

Modify/Update this entry