  


Generalized Mixed Integer Rounding Valid Inequalities
Kiavash Kianfar (kianfartamu.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 2step 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 nstep MIR facet, can be used to generate a family of valid inequalities for the feasible set of a general (mixed) IP constraint, the nstep MIR inequalities. The Gomory Mixed Integer Cut and the 2step MIR inequality of Dash and Günlük (2006) are simply the first two families corresponding to n=1,2, respectively. The nstep MIR inequalities are easily produced using closedform periodic functions, which we refer to as the nstep MIR functions. None of these functions dominates the other on its whole period. Moreover, for any n, the nstep MIR inequalities define new families of twoslope 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 20061, North Carolina State University Download: Entry Submitted: 06/17/2006 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  