首页 | 本学科首页   官方微博 | 高级检索  
     


A Dynamic Domain Contraction Algorithm for Nonconvex Piecewise Linear Network Flow Problems*
Authors:Dukwon Kim  Panos M. Pardalos
Affiliation:(1) Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville
Abstract:We consider the Nonconvex Piecewise Linear Network Flow Problem (NPLNFP) which is known to be 
$$mathcal{N}{text{ }}P$$
-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 heuristic approach is in need to solve large scale problems appearing in many practical applications including transportation, production-inventory management, supply chain, facility expansion and location decision, and logistics. In this paper, we present a new approach for solving the general NPLNFP in a continuous formulation by adapting a dynamic domain contraction. A Dynamic Domain Contraction (DDC) algorithm is presented and preliminary computational 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.
Keywords:Domain contraction  Dynamic slope scaling procedure  Fixed charge  Nonconvex piecewise linear network flow problem
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号