Separation, dimension, and facet algorithms for node flow polyhedra (Q2638390)

The paper deals with production planning problems such as an available to promise (ATP) model. This problem can involve material compatibility constraints that specify when components from various suppliers can be feasibly assembled into a final product. As previously studied in other papers, these 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. The nodes representing components and paths represent product configurations. In this paper, previous work is extended to arbitrary directed networks, both upper and lower bounds for the flow are considered, a characterization of which valid inequalities are facets is given etc. The main contribution of the paper is the development of an efficient algorithm to solve the faced-separation problem for the node flow polyhedron denoted by \(Q^B\). This main problem is divided into subproblems: separation, violation, dimension, and face dimension. Each of these problems is reduced to computing a max flow or a min-cost flow in a special network. So, these algorithms are very efficient both in theory and in practice. The first problem studied in the paper is separation. Hoffman cuts and Hoffman's circulation theorem are presented. The separation problem is solved using a max flow algorithm, but for the separation problem for \(Q^B\) using a subset of the set of directed simple cycles it is proven that it is NP hard. Violation is the converse problem to separation. We want to know if a constraint \(a^{T}x \geq \beta\) is valid for \(Q^{B}\) or not, and if not a value from \(Q^{B}\) that violates it must be produced. The violation problem is solved by using a min-cost flow algorithm. In order to know which Hoffman cuts are facets, the dimension of the node flow polyhedron must be calculated. This dimension is noted by \(\dim(Q^B)\). As shown, \(\dim(Q^B)\) is non-trivial to compute.