Separation, dimension, and facet algorithms for node flow polyhedra

Production planning problems such as an Available to Promise (ATP) model of Chen et al. (2002) can involve material compatibility constraints that specify when components from various suppliers can be feasibly assembled into a final product. In a companion paper to Chen et al. (2002), Ball et al. (2003) showed that in many cases such constraints can be modeled as the set of feasible source-sink flows through an acyclic network. The flow through a node is the sum of the flows on all paths containing it. The number of paths is often exponential in the number of nodes, and so it is more computationally tractable to consider the set of node flows in place of that of path flows. Here nodes represent components and paths represent product configurations. In the context of NP hard Mixed Integer Programming models such as the ATP model, when the description of the set of node flows is too complicated to be explicitly written out, the material compatibility constraints can be handled in a cutting plane framework by using a separation algorithm. Ball et al. characterized the polyhedron of node flows for some special cases. We extend this work in various practical and theoretical directions: we allow arbitrary directed networks, we allow both upper and lower bounds on flows, we characterize whin valid inequalities are facets, we give fast algorithms for separation, violation, and dimension, and we put all the pieces together into an algorithm for facet-separation. All algorithms are very efficient, as they are based on max flow and min-cost flow subroutines.