Dw. Kim et Pm. Pardalos, A dynamic domain contraction algorithm for nonconvex piecewise linear network flow problems, J GLOB OPT, 17(1-4), 2000, pp. 225-234
We consider the Nonconvex Piecewise Linear Network Flow Problem (NPLNFP) wh
ich is known to be XP-hard. Although exact methods such as branch and bound
have been developed to solve the NPLNFP, their computational requirements
increase exponentially with the size of the problem. Hence, an efficient he
uristic approach is in need to solve large scale problems appearing in many
practical applications including transportation, production-inventory mana
gement, supply chain, facility expansion and location decision, and logisti
cs. In this paper, we present a new approach for solving the general NPLNFP
in a continuous formulation by adapting a dynamic domain contraction. A Dy
namic Domain Contraction (DDC) algorithm is presented and preliminary compu
tational results on a wide range of test problems are reported. The results
show that the proposed algorithm generates solutions within 0 to 0.94 % of
optimality in all instances that the exact solutions are available from a
branch and bound method.