Optimization Online


On n-step MIR and Partition Inequalities for Integer Knapsack and Single-node Capacitated Flow Sets

Kiavash Kianfar (kianfar***at***tamu.edu)

Abstract: Pochet and Wolsey [Y. Pochet, L.A. Wolsey, Integer knapsack and flow covers with divisible coefficients: polyhedra, optimization and separation. Discrete Applied Mathematics 59(1995) 57-74] introduced partition inequalities for three substructures arising in various mixed integer programs, namely the integer knapsack set with nonnegative divisible/arbitrary coefficients and two forms of single-node capacitated flow set with divisible coefficients. They developed the partition inequalities by proving properties of the optimal solution in optimizing a linear function over these sets. More recently, the author and Fathi [K. Kianfar, Y. Fathi: Generalized mixed integer rounding inequalities: facets for infinite group polyhedra. Mathematical Programming 120(2009) 313-346] introduced the n-step mixed integer rounding (MIR) inequalities for the mixed-integer knapsack set with arbitrary coefficients through a generalization of MIR. In this paper, we show that the n-step MIR generates facet-defining inequalities not only for the three sets considered by Pochet and Wolsey but also for their generalization to the case where coefficients are not necessarily divisible. In the case of divisible coefficients, n-step MIR directly generates the partition inequalities for all three sets (and in some cases stronger inequalities for one of the sets). We show that n-step MIR gives facets for the integer knapsack set with arbitrary coefficients that either dominate or are not obtainable by the partition inequalities. We also derive new (the first) facets for the two capacitated flow sets with arbitrary coefficients using n-step MIR. Our results provide a new perspective based on n-step MIR into the polyhedral properties of these three substructures, extend them to the case of arbitrary coefficients, and underscore the power of n-step MIR to easily generate strong valid inequalities.

Keywords: n-step mixed integer rounding; partition inequality; integer knapsack set; capacitated flow set; valid inequality; facet

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

Citation: Research Report Department of Industrial and Systems Engineering Texas A&M University

Download: [PDF]

Entry Submitted: 03/13/2011
Entry Accepted: 03/14/2011
Entry Last Modified: 03/14/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