TABLE OF CONTENTS Network flow problems are widely studied, especially for those having convex cost functions, fixed-charge cost functions, and concave functions. However, network flow problems with general nonlinear cost functions receive little attention. The problems with step cost functions are important due to the many practical applications. In this paper, these problems are discussed and formulated as equivalent mathematical mixed 0-1 linear programming problems. Computational results on randomly generated test beds for these exact approached solution procedure are reported in the paper.
Keywords:
Nonconvex network problem; lot sizing; minimum-cost network flows.
Given a finite time horizon T and positive demands for a single item, production, inventory, and transportation schedules should be determined to minimize the total cost, including production cost, inventory cost, and transportation cost, on the condition that the demand only be satisfied from production at multiple facilities in the current period or by inventory from the previous periods (Backlogging is not allowed). For convex network flow problems if the local optimal solution is found, then it is also the global optimum. Even large scale problems are still tractable in the convex case. However, it is well known that concave network flow problems are NP-hard problems [11]. In the worst case, it need...
