6533b828fe1ef96bd12881d7
RESEARCH PRODUCT
Finding all optimal solutions to the network flow problem
Nicos ChristofidesV. Vallssubject
Mathematical optimizationFlow (mathematics)Linear programmingComputer scienceCirculation problemMinimum-cost flow problemFlow networkMulti-commodity flow problemZero (linguistics)Electronic circuitdescription
The problem examined in this paper is as follows: Given a feasible optimum basic solution (f.o.b.s) of the minimum cost network flow problem, find all the f.o.b.s of this problem. The existence of alternative f.o.b.s is characterized by means of elementary circuits of zero cost and length greater than two in the incremental graph associated to the given f.o.b.s. It is shown that any alternative f.o.b.s. can be obtained from the original one by circulating flow through elementary circuits belonging to a succession of incremental graphs. This result leads to the construction of an efficient algorithm to obtain all f.o.b.s. of the network flow problem.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1986-01-01 |