Article ID: | iaor19982969 |
Country: | Germany |
Volume: | 20 |
Issue: | 1 |
Start Page Number: | 47 |
End Page Number: | 53 |
Publication Date: | Jan 1998 |
Journal: | OR Spektrum |
Authors: | Horst Reiner, Thoai Nguyen Van |
Keywords: | programming: integer |
Formulating the minimum concave cost capacitated network flow problem as an integer concave minimization problem, we establish finite branch and bound algorithms, in which the branching operation is the so-called integral rectangular partition and the bounding procedure is performed by the classical minimum linear cost flow problem on subnetworks. For the special case that the flow cost function is concave on a fixed number of arcs and linear on the others, an upper bound of the running time is given.