On nn-step MIR and partition inequalities for integer knapsack and single-node capacitated flow sets

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] have introduced the nn-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 nn-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, nn-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 nn-step MIR gives facets for the integer knapsack set with arbitrary coefficients that either dominate or are not obtainable by the partition inequalities. Also, using the nn-step MIR, we introduce families of facets for the two capacitated flow sets with arbitrary coefficients for the first time. Our results provide a new perspective based on nn-step MIR into the polyhedral properties of these three substructures, extend them to the case of arbitrary coefficients, and underscore the power of nn-step MIR to easily generate strong valid inequalities.