Extremal Solutions for Network Flow with Differential Constraints

Abstract In network flow problems, there is a well-known one-to-one relationship between extreme points of the feasibility region and trees in the associated undirected graph. The same is true for the dual differential problem. In this paper, we study a problem variant with both differential constraints and constraints on flow conservation at every node, which we call differential flow . This variant is motivated by an application in the expansion planning of energy networks. We show that all extreme points in the differential flow polytope still directly correspond to graph-theoretical structures in the underlying network, namely a generalization of spanning trees. The reverse is generally also true except in very special cases where the network parameters satisfy a set of particular equations. We furthermore show that these exceptional cases can never occur in cactus graphs and present additional, sufficient criteria for when the one-to-one correspondence between extreme points and graph-theoretical structures holds. Finally, we show that it is generally NP-hard to decide for a specific network whether the graph-theoretical characterization holds for all extreme points.