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.
Citation
Research Report Department of Industrial and Systems Engineering Texas A&M University