Parametric max flow problems in a class of networks with series-parallel structure

Parametric max flow problems in a class of networks with series-parallel structure

0.00 Avg rating0 Votes
Article ID: iaor1995711
Country: United Kingdom
Volume: 21
Issue: 7
Start Page Number: 769
End Page Number: 776
Publication Date: Aug 1994
Journal: Computers and Operations Research
Authors: ,
Abstract:

This paper considers a parametric max flow network problem where arc capacities are not fixed but stated as unknown variables to be determined optimally such that the corresponding max flow satisfies flow requirement between source and sink. For the problem, a max flow algorithm may be adapted as a subroutine to be used recursively in an enumerative solution search until finding the optimal solution. However, such an enumerative approach is not practical because it is not guaranteed to solve the problem in a finite number of steps. Therefore, this paper pays attention to the instance defined in a special class of networks, called basically-series-parallel networks, for which all minimal cutsets can easily be enumerated in polynomial time by introducing a set of network reduction methods, called 2-neighbor-node, parallel and source-delta reductions, while such minimal cutset enumeration itself is NP-hard in general. Once all minimal cutsets are found, the associated parametric max flow problem remains simply to solve in a linear programming approach.

Reviews

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