Advanced Search
Article Contents
Article Contents

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

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 90C59; Secondary: 90-08.


    \begin{equation} \\ \end{equation}
  • 加载中

Article Metrics

HTML views() PDF downloads(113) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint