删除或更新信息,请邮件至freekaoyan#163.com(#换成@)

基于交替方向乘子法的大规模线性多商品流问题求解算法

本站小编 Free考研考试/2021-12-27

徐薇, 吴钰炜, 陈彩华
南京大学工程管理学院, 南京 210093
收稿日期:2017-12-12出版日期:2018-12-15发布日期:2018-11-20


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


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
Received:2017-12-12Online:2018-12-15Published:2018-11-20







摘要



编辑推荐
-->


企业的商品流通配送问题是典型的线性多商品流问题.由于经营规模的扩大和全球化运营模式的推行,企业所面临的问题规模正变得空前巨大,数据存储也越来越分散,传统方法已无法适应求解需求.本文基于交替方向乘子法(ADMM)的可分解性,提出一类随机ADMM算法,将大规模的问题分解成多个、规模比较小的问题,并采取随机顺序去求解这些小问题以及对偶问题,最终得到原问题的最优解.算法克服了ADMM的直接拓展求解多块问题时可能发散的缺点,并采用MnetGen生成器随机生成的多个规模不同的线性多商品流问题对算法进行了测试,验证了算法的有效性和高效的求解效率.
MR(2010)主题分类:
65E05

分享此文:


()

[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]胡宏伶, 陈传淼, 谢资清. 外推瀑布多网格法(EXCMG)---大规模求解椭圆问题的新算法[J]. 计算数学, 2009, 31(3): 261-274.
[5]孙清滢; 崔彬; 王长钰. 新非单调线搜索规则的Lampariello修正对角稀疏拟牛顿算法[J]. 计算数学, 2008, 30(3): 255-268.
[6]王周宏. 一个无约束有限内存信赖域方法及其实现[J]. 计算数学, 2005, 27(4): 395-404.
[7]孙清滢. 初始点任意的解非线性不等式约束优化问题的结合共轭梯度参数的超记忆梯度广义投影算法[J]. 计算数学, 2004, 26(4): 401-412.
[8]燕子宗,费浦生. 线性规划流动等值面算法[J]. 计算数学, 2004, 26(4): 437-444.
[9]孙清滢,刘新海. 结合广义Armijo步长搜索的一类新的三项共轭梯度算法及其收敛特征[J]. 计算数学, 2004, 26(1): 25-36.
[10]谷同祥,刘兴平,迟学斌. 对称正定问题多搜索方向共轭梯度法的收敛性理论[J]. 计算数学, 2004, 26(1): 117-128.
[11]张菊亮,章祥荪,卓新建. 无正则性条件下的一个信赖域方法的全局收敛性[J]. 计算数学, 2002, 24(4): 437-450.
[12]阮国桢,成央金,朱书尚. 线性规划的对偶基线算法[J]. 计算数学, 2002, 24(3): 257-264.
[13]阮国桢. 线性规划基线算法的基本概念[J]. 计算数学, 1999, 21(4): 441-450.
[14]孙丰荣,田发中. 关于多点源势函数的快速计算[J]. 计算数学, 1999, 21(1): 81-88.

--> -->
阅读次数
全文







摘要





Cited

Shared






PDF全文下载地址:

http://www.computmath.com/jssx/CN/article/downloadArticleFile.do?attachType=PDF&id=277
相关话题/计算 数学 推荐 技术 投资