  


nstep Mingling Inequalities: New Facets for the MixedInteger Knapsack Set
Alper Atamturk (atamturkberkeley.edu) Abstract: The nstep mixed integer rounding (MIR) inequalities of Kianfar and Fathi are valid inequalities for the mixedinteger knapsack set that are derived by using periodic nstep MIR functions and define facets for group problems. The mingling and 2step mingling inequalities of Atamturk and Gunluk are also derived based on MIR and they incorporate upper bounds on the integer variables. It has been shown that these inequalities are facetdefining for the mixed integer knapsack set under certain conditions and generalize several wellknown valid inequalities. In this paper, we introduce new classes of valid inequalities for the mixedinteger knapsack set with bounded integer variables, which we call nstep mingling inequalities (for positive integer n). These inequalities incorporate upper bounds on integer variables into nstep MIR and, therefore, unify the concepts of nstep MIR and mingling in a single class of inequalities. Furthermore, we show that for each n, the nstep mingling inequality defines a facet for the mixed integer knapsack set under certain conditions. For n=2, we extend the results of Atamturk and Gunluk on facetdefining properties of 2step mingling inequalities. For n>=3, we present new facets for the mixed integer knapsack set. We also derive as a special case conditions under which the nstep MIR inequalities define facets for the mixed integer knapsack set. In addition, we show that nstep mingling can be used to generate new valid inequalities and facets based on covers and packs defined for mixed integer knapsack sets. Keywords: Mixed Integer Rounding  Mixed Integer Programming  Mingling  Valid Inequality  Facet Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Citation: Download: Entry Submitted: 11/19/2009 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  