Gainfree Leontief substitution flow problems

Gainfree Leontief substitution flow problems

0.00 Avg rating0 Votes
Article ID: iaor19931944
Country: Netherlands
Volume: 57
Issue: 3
Start Page Number: 375
End Page Number: 414
Publication Date: Dec 1992
Journal: Mathematical Programming (Series A)
Authors: , , ,
Keywords: graphs, calculus of variations
Abstract:

Leontief substitution systems have been studied by economists and operations researchers for many years. The authors 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. They 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, the authors show how the Leontief flow paradigm links polyhedral combinatorics, expert systems, mixed integer model formulation, and some problems in graph optimization.

Reviews

Required fields are marked *. Your email address will not be published.