文章基本信息

标题：A Dynamic Method to Solve the Fixed Charge Network Flow Problem ⁎
本地全文：下载
作者：Zhibin Nie ; Shuning Wang
期刊名称：IFAC PapersOnLine
印刷版ISSN：2405-8963
出版年度：2020
卷号：53
期号：2
页码：11231-11236
DOI：10.1016/j.ifacol.2020.12.344
语种：English
出版社：Elsevier
摘要：AbstractThis paper studies the widely applied fixed charge network ow problem (FCNFP), which is NP-hard. We approximate the FCNFP with a bilinear programming problem that is determined by a parameter ɛ. When ɛ is small enough, the optimal solution to the bilinear programming problem is the same as the optimal solution to the FCNFP. Therefore, solving the FCNFP can be transformed into solving a series of bilinear programming problems with decreasing ɛ. In this paper, these bilinear programming problems are solved by alternately solving two coupled linear programming problems. A dynamic method is proposed to update ɛ after solving one of the linear programming problems rather than solving the whole bilinear programming problem. Numerical experiments show the performance of the proposed method.
关键词：KeywordsNetwork flow problemFixed chargeBilinear programmingDynamic method