| Network models are pervasive and arise in diverse application areas. Today, network flow optimization directly and indirectly influences high-level decision making in various industries, especially those related to transportation, production-inventory, distribution, supply chain, logistics, and communication network design problems.; In this thesis we are concerned with the two issues of piecewise linearity and reducibility in nonconvex network flow problems. The emphasis of this thesis focuses, firstly, on reducing each subclass of Piecewise Linear Network Problems (PLNFP) to a Fixed Charge Network Problem (FCNFP) and, secondly, on developing efficient solution approaches and algorithms for each class of problems.; The thesis consists of an introduction and a series of research papers. The common theme of these papers is the systematic use of the underlying network and the exploiting of piecewise linearities and separability of the cost structure to develop efficient algorithms. We discuss the reducibility of PLNFPs into a fixed charge network flow model which is known to be NP -hard and can be transformed to a 0--1 Mixed Integer Programming (MIP) problem.; Due to the exponentially increasing time and memory requirements for solving exactly such MIP problems, exact solution methods have typically failed to solve large-scale problems efficiently in most cases. Thus developing an effective and efficient heuristic approach is a main focus in this field. This motivates primary research on developing an efficient heuristic approach for the general FCNFP, called Dynamic Slope Scaling Procedure (DSSP). The extensive computational results show that the DSSP algorithm is highly efficient, effective and stable in its performance.; Based on these promising results, the DSSP approach is extended to solve more complicated problems such as pure concave PLNFPs and nonconvex (discontinuous) PLNFPs, incorporating Trust Intervals, Solution Tendency, and Domain Contraction techniques. Due to the flexibility of the algorithm structure, the DSSP can be easily implemented on various types of problems with practical cost structures including, economies of scale and nonconvex piecewise linear costs. As a practical application, a network solution approach for global supply chain management is briefly introduced for future work. |
