-

 

 

 




Optimization Online





 

n-step Conic Mixed Integer Rounding Inequalities

Sina Masihabadi (si136364***at***neo.tamu.edu)
Sujeevraja Sanjeevi (sujeevraja***at***tamu.edu)
Kiavash Kianfar (kianfar***at***tamu.edu)

Abstract: We introduce the n-step conic MIR inequalities for the so-called polyhedral second-order conic (PSOC) mixed integer sets. PSOC sets arise in the polyhedral reformulation of the second-order conic mixed integer programs. Moreover, they are an equivalent representation for any mixed integer set defined by two linear constraints. The simple conic MIR inequalities of Atamtürk and Narayanan (Math Program 122:1-20, 2010) and the n-step MIR inequalities of Kianfar and Fathi (Math Program 120:313-346, 2009) are special cases of the n-step conic MIR inequalities. We first derive the n-step conic MIR inequality for a PSOC set with n integer variables and prove that all the 1-step to n-step conic MIR inequalities are facet-defining for the convex hull of this set. We also provide necessary and sufficient conditions for the polyhedral second-order conic form of this inequality to be valid. Then we use the aforementioned n-step conic MIR facet to derive the n-step conic MIR inequality for a general PSOC set and provide conditions for it to be facet-defining. These inequalities are generated using functions which we refer to as the n-step conic MIR functions. We further show that the n-step conic MIR inequality for a general PSOC set strictly dominates the n-step MIR inequalities written for the two linear constraints that define the PSOC set. We also prove that the n-step MIR inequality for a linear mixed integer constraint is a special case of the n-step conic MIR inequality.

Keywords: n-step conic MIR; n-step MIR; conic mixed integer programming; valid inequality; facet

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

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

Category 3: Integer Programming (Cutting Plane Approaches )

Citation:

Download:

Entry Submitted: 11/22/2011
Entry Accepted: 11/22/2011
Entry Last Modified: 04/28/2012

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
Mathematical Optimization Society