A bilinear relaxation based algorithm for concave piecewise linear network flow problems
2007
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
11
References
27
Citations
NaN
KQI