Generalized Mixed Integer Rounding Valid Inequalities

Kiavash Kianfar (kianfartamu.edu)
Yahya Fathi (fathincsu.edu)

Abstract: We present new families of valid inequalities for (mixed) integer programming (MIP) problems. These valid inequalities are based on a generalization of the 2-step mixed integer rounding (MIR), proposed by Dash and Günlük (2006). We prove that for any positive integer n, n facets of a certain (n+1)-dimensional mixed integer set can be obtained through a process which includes n consecutive applications of MIR. We then show that for any n, the last of these facets, the n-step MIR facet, can be used to generate a family of valid inequalities for the feasible set of a general (mixed) IP constraint, the n-step MIR inequalities. The Gomory Mixed Integer Cut and the 2-step MIR inequality of Dash and Günlük (2006) are simply the first two families corresponding to n=1,2, respectively. The n-step MIR inequalities are easily produced using closed-form periodic functions, which we refer to as the n-step MIR functions. None of these functions dominates the other on its whole period. Moreover, for any n, the n-step MIR inequalities define new families of two-slope facets for the finite and the infinite group problems.

Keywords: Mixed Integer Rounding; Valid Inequality; Mixed Integer Programming; Group Problem;

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: Operations Research Technical Report 2006-1, North Carolina State University

Download:

Entry Submitted: 06/17/2006
Entry Accepted: 06/19/2006
Entry Last Modified: 02/27/2008

Modify/Update this entry