GAINFREE LEONTIEF SUBSTITUTION FLOW PROBLEMS

Leontief substitution systems have been studied by economists and operations researchers for many rears. We show how such linear systems are naturally viewed as Leontief substitution flow problems on directed hypergraphs, and that important solution properties follow from structural characteristics of the hypergraphs. We give a strongly polynomial, non-simplex algorithm for Leontief substitution flow problems that satisfy a gainfree property leading to acyclic extreme solutions. Integrality conditions follow easily from this algorithm. Another structural property, support disjoint reachability, leads to necessary and sufficient conditions for extreme solutions to be binary. In a survey of applications, we show how the Leontief flow paradigm links polyhedral combinatorics, expert systems, mixed integer model formulation, and some problems in graph optimization.