计算数学
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  留言板 |  联系我们 |  重点论文 |  在线办公 | 
计算数学  2018, Vol. 40 Issue (4): 436-449    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles  
基于交替方向乘子法的大规模线性多商品流问题求解算法
徐薇, 吴钰炜, 陈彩华
南京大学工程管理学院, 南京 210093
SOLVING THE LARGE-SCALE LINEAR MULTI-COMMODITY FLOW PROBLEM VIA AN ALTERNATING DIRECTION METHOD OF MULTIPLIERS
Xu Wei, Wu Yuwei, Chen Caihua
School of Management and Engineering, Nanjing University, Nanjing 210093, China
 全文: PDF (631 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 企业的商品流通配送问题是典型的线性多商品流问题.由于经营规模的扩大和全球化运营模式的推行,企业所面临的问题规模正变得空前巨大,数据存储也越来越分散,传统方法已无法适应求解需求.本文基于交替方向乘子法(ADMM)的可分解性,提出一类随机ADMM算法,将大规模的问题分解成多个、规模比较小的问题,并采取随机顺序去求解这些小问题以及对偶问题,最终得到原问题的最优解.算法克服了ADMM的直接拓展求解多块问题时可能发散的缺点,并采用MnetGen生成器随机生成的多个规模不同的线性多商品流问题对算法进行了测试,验证了算法的有效性和高效的求解效率.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词线性多商品流   大规模   线性规划   交替方向乘子法   多块分解     
Abstract: The issue of commodity circulation and distribution is a typical linear multi-commodity flow problem (MCFP). Along with the expansion of the operation scale and the implementation of the globalization strategy, the MCFPs faced by corporations are becoming more and more huge. Meanwhile, data storage is more and more distributed. Thus, the traditional methods are unable to solve the large-scale MCFPs efficiently. Based on the decomposition idea of alternating direction method of multipliers (ADMM), this paper proposes a modified algorithm named random ADMM. It divides the large-scale problem into a number of small problems, and solves these problems in a random order as well as the dual problem, and finally arrives at the optimal solution of the original problem. Such a random ADMM overcomes the shortcoming that the direct extension of ADMM might diverge while solving multi-block separable convex optimization problems. Some linear MCFPs in different scales generated by the MnetGen generator are used to test the proposed algorithm. The results exhibit the effectiveness and good efficiency of the algorithm.
Key wordslinear multi-commodity flow   large scale   linear programming   alternating direction method of multipliers   multi-block decomposition   
收稿日期: 2017-12-12;
基金资助:

国家自然科学基金(71271112,71671087,71673130,11401300)和江苏省自然科学基金(BK20181259)资助项目.

引用本文:   
. 基于交替方向乘子法的大规模线性多商品流问题求解算法[J]. 计算数学, 2018, 40(4): 436-449.
. SOLVING THE LARGE-SCALE LINEAR MULTI-COMMODITY FLOW PROBLEM VIA AN ALTERNATING DIRECTION METHOD OF MULTIPLIERS[J]. Mathematica Numerica Sinica, 2018, 40(4): 436-449.
 
[1] George B. A new era for global leadership development. Harvard Business Review, 2012.
[2] Glowinski R, Marroco A. Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problémes de Dirichlet non linéaires[J]. ESAIM:Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique, 1975, 9(R2):41-76.
[3] Gabay D, Bertrand M. A dual algorithm for the solution of nonlinear variational problems via finite element approximation[J]. Computers & Mathematics with Applications, 1976, 2(1):17-40.
[4] Eckstein J, Bertsekas D P. An alternating direction method for linear programming. LIDS-P, no.1967, Cambridge, MA, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, 1990.
[5] Boyd S, Parikh N, Chu E, Peleato B, Eckstein J. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends in Machine Learning, 2011, 3(1):1-122.
[6] Gabay D. Applications of the method of multipliers to variational inequalities. In M. Fortin and R. Glowinski, editors, Augmented Lagrangian Methods:Applications to the Solution of BoundaryValue Problems. North-Holland:Amsterdam, 1983.
[7] Chen C H, He B S, Ye Y Y, Yuan X M. The direct extension of admm for multi-block convex minimization problems is not necessarily convergent[J]. Mathematical Programming, 2016, 155(1):57-79.
[8] Frangioni A, Gallo G. A bundle type dual-ascent approach to linear multicommodity min-cost flow problems[J]. INFORMS Journal on Computing, 1999, 11(4):370-393.
[9] Mamer J W, McBride R D. A decomposition-based pricing procedure for large-scale linear programs:An application to the linear multicommodity flow problem[J]. Management Science, 2000, 46(5):693-709.
[10] Dean J, Ghemawat S. Mapreduce:simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1):107-113.
[11] He B S, Yang H, Wang S L. Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities[J]. Journal of Optimization Theory and Applications, 2000, 106(2):337-356.
[1] 陈圣杰, 戴彧虹, 徐凤敏. 稀疏线性规划研究[J]. 计算数学, 2018, 40(4): 339-353.
[2] 姜帆, 刘雅梅, 蔡邢菊. 一类自适应广义交替方向乘子法[J]. 计算数学, 2018, 40(4): 367-386.
[3] 袁晓, 肖瑾. 受参考价格影响的变质产品销售最优动态价格和保存技术投资的联合策略研究[J]. 计算数学, 2017, 39(4): 363-377.
[4] 乐航睿, 杨庆之. 求解正则化最小二乘问题的一个非精确交替方向乘子法[J]. 计算数学, 2016, 37(3): 223-232.
[5] 郑汉垣, 宋安平, 张武. 基于MIC的GaBP并行算法[J]. 计算数学, 2015, 36(1): 31-41.
[6] 赵海峰,  刘新为. 退化线性规划的一个新的改进的单纯形方法[J]. 计算数学, 2012, 33(2): 109-120.
[7] 胡宏伶, 陈传淼, 谢资清. 外推瀑布多网格法(EXCMG)---大规模求解椭圆问题的新算法[J]. 计算数学, 2009, 31(3): 261-274.
[8] 孙莉, 贺国平, 房亮. 基于求解大规模界约束问题的三种有效集识别策略的比较[J]. 计算数学, 2009, 30(1): 41-47.
[9] 孙清滢; 崔彬; 王长钰. 新非单调线搜索规则的Lampariello修正对角稀疏拟牛顿算法[J]. 计算数学, 2008, 30(3): 255-268.
[10] 王周宏. 一个无约束有限内存信赖域方法及其实现[J]. 计算数学, 2005, 27(4): 395-404.
[11] 燕子宗,费浦生. 线性规划流动等值面算法[J]. 计算数学, 2004, 26(4): 437-444.
[12] 孙清滢. 初始点任意的解非线性不等式约束优化问题的结合共轭梯度参数的超记忆梯度广义投影算法[J]. 计算数学, 2004, 26(4): 401-412.
[13] 谷同祥,刘兴平,迟学斌. 对称正定问题多搜索方向共轭梯度法的收敛性理论[J]. 计算数学, 2004, 26(1): 117-128.
[14] 孙清滢,刘新海. 结合广义Armijo步长搜索的一类新的三项共轭梯度算法及其收敛特征[J]. 计算数学, 2004, 26(1): 25-36.
[15] 张菊亮,章祥荪,卓新建. 无正则性条件下的一个信赖域方法的全局收敛性[J]. 计算数学, 2002, 24(4): 437-450.

Copyright 2008 计算数学 版权所有
中国科学院数学与系统科学研究院 《计算数学》编辑部
北京2719信箱 (100190) Email: gxy@lsec.cc.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发
技术支持: 010-62662699 E-mail:support@magtech.com.cn
京ICP备05002806号-10