An out-of-kilter method for submodular flows (Q1095780)

The paper extends the out-of-kilter algorithm to the problem of computing a minimum-cost submodular network flow. Submodular flows generalize the classical flows by replacing the ordinary equality constraints on the source and sink nodes by more general inequality constraints on subset of nodes. This generalization is possible if the subsets are suitably chosen to belong to the class of crossing families, and the bounds to the class of submodular functions on these families. Most of the notions defined for the out-of-kilter method can be extended to this context. There are two kilter numbers, one measuring non- feasibility with respect to the source and sink constraints, and the other the non-feasibility with respect to the ordinary arc capacity constraints. First, the author shows that a submodular flow is optimal if the kilter numbers vanish. The generalized out-of-kilter operates by changing the flows in such a way that at each iteration, no kilter number increases, and at least one of them decreases. This decrease is at least one if the problem data are integer, which guarantees the convergence of the method. The complexity of the algorithm is of the order of the size of the sum of the initial kilter numbers and the number of vertices in the graph. As with the standard out-of-kilter method, this generalization would be particularly useful to carry out a sensitivity analysis for an existing solution.