Optimization Online


n-step Mingling Inequalities: New Facets for the Mixed-Integer Knapsack Set

Alper Atamturk (atamturk***at***berkeley.edu)
Kiavash Kianfar (kianfar***at***tamu.edu)

Abstract: The n-step mixed integer rounding (MIR) inequalities of Kianfar and Fathi are valid inequalities for the mixed-integer knapsack set that are derived by using periodic n-step MIR functions and define facets for group problems. The mingling and 2-step 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 facet-defining for the mixed integer knapsack set under certain conditions and generalize several well-known valid inequalities. In this paper, we introduce new classes of valid inequalities for the mixed-integer knapsack set with bounded integer variables, which we call n-step mingling inequalities (for positive integer n). These inequalities incorporate upper bounds on integer variables into n-step MIR and, therefore, unify the concepts of n-step MIR and mingling in a single class of inequalities. Furthermore, we show that for each n, the n-step 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 facet-defining properties of 2-step 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 n-step MIR inequalities define facets for the mixed integer knapsack set. In addition, we show that n-step 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 )



Entry Submitted: 11/19/2009
Entry Accepted: 11/20/2009
Entry Last Modified: 03/13/2011

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