Dynamic slope scaling and trust interval techniques for solving concave piecewise linear network flow problems

In this paper, we propose an efficient heuristic approach for solving conca ve Piecewise Linear Network Flow Problems (PLNFP) in which the cost is sepa rable and each are cost is concave piecewise linear function of the total f low along the arcs, The problem is well known to be NP-hard and exact globa l optimization algorithms are of limited use. In this paper, PLNFP is trans formed into an equivalent Fixed-Charge Network Flow Problem (FCNFP) using a n are separation procedure, and we develop an algorithm combining the Dynam ic Slope Scaling Procedure (DSSP) and Trust Interval techniques. Due to the fast growing size of the transformed FCNFP, exact branch-and-bound methods are not able to handle the problems of practical size. Based on the dynami c slope scaling algorithm developed for solving FCNFP in previous work, we add a trust interval technique based on solution tendencies to speed up the algorithm. The numerical experiments show that the proposed algorithm is q uite efficient and its performance is very stable. (C) 2000 John Wiley & So ns, Inc.