A bilinear relaxation based algorithm for concave piecewise linear network flow problems

We present a continuous relaxation technique for the Concave Piecewise Linear Network Flow Problem (CPLNFP), which has a bilinear objective function and network constraints. We show that a global optimum of the resulting problem is a solution of CPLNFP. The theoretical results are generalized for a concave minimization problem with a separable objective function. An efficient and effective Dynamic Cost Updating Procedure (DCUP) is considered to find a local minimum of the relaxation problem, which converges in a finite number of iterations. We show that the CPLNFP is equivalent to a Network Flow Problem with Flow Dependent Cost Functions (NFPwFDCF), and we prove that the solution of the Dynamic Slope Scaling Procedure (DSSP) is an equilibrium solution of the NFPwFDCF. The numerical experiments show that the proposed algorithm can provide a better solution than DSSP using less amount of CPU time and iterations.