Bilinear Relaxation Technique and
Solution Algorithm for Concave
Piecewise Linear and Fixed Charge
Network Flow Problems
Artyom Nahapetyan
Dept. of Industrial and Systems Engineering
We consider concave piecewise
linear network flow problems where the mathematical formulation involves binary
variables and belongs to MIP. We propose a bilinear relaxation technique which
can be used in the heuristic, as well as exact algorithms to solve the problem.
In particular, we prove that the global solution of the relaxation problem is
the solution of the initial mixed integer formulation. Based on the theoretical
results, we propose a final convergent dynamic cost updating procedure (DCUP)
to find the local minimum of the relaxation problem. In the numerical
experiments, we compare the solution of DCUP with the exact solution provided
by Cplex as well as with the solution provided by
dynamic slope scaling procedure. In addition, we extend the result and adapt
DCUP to solve fixed charge network flow problems.