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.
. 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.
George B. A new era for global leadership development. Harvard Business Review, 2012.
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.
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.
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.
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.
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.
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.
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.
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.
Dean J, Ghemawat S. Mapreduce:simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1):107-113.
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.