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

来源：计算数学杂志2018年第4期北京时间：

作者：徐薇, 吴钰炜, 陈彩华

单位：南京大学工程管理学院, 南京 210093

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

关键词：线性多商品流,大规模,线性规划,交替方向乘子法,多块分解

基金资助：<p>国家自然科学基金（71271112，71671087，71673130，11401300）和江苏省自然科学基金（BK20181259）资助项目.</p>