Gainfree Leontief substitution flow problems

Leontief substitution systems have been studied by economists and operations researchers for many years. We show how such linear systems are naturally viewed asLeontief 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 againfree 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.Dedicated to the memory of Robert G. JeroslowSee Acknowledgement section.Research supported in part by the ONR (Office of Naval Research) under URI Grant number N00014-86-K-0689, and Center for Operations Research and Econometrics, Universite Catholique de Louvain.