Optimization Online


Generalized Mixed Integer Rounding Valid Inequalities

Kiavash Kianfar (kianfar***at***tamu.edu)
Yahya Fathi (fathi***at***ncsu.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


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society