  


On nstep MIR and Partition Inequalities for Integer Knapsack and Singlenode Capacitated Flow Sets
Kiavash Kianfar (kianfartamu.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) 5774] 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 singlenode 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) 313346] introduced the nstep mixed integer rounding (MIR) inequalities for the mixedinteger knapsack set with arbitrary coefficients through a generalization of MIR. In this paper, we show that the nstep MIR generates facetdefining 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, nstep MIR directly generates the partition inequalities for all three sets (and in some cases stronger inequalities for one of the sets). We show that nstep 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 nstep MIR. Our results provide a new perspective based on nstep MIR into the polyhedral properties of these three substructures, extend them to the case of arbitrary coefficients, and underscore the power of nstep MIR to easily generate strong valid inequalities. Keywords: nstep 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 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  