ISSN:
1436-4646
Keywords:
Leontief matrices
;
linear programming
;
integer programming
;
network flows
;
polyhedral combinatorics
;
expert systems
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01581090
Permalink
