(51c) Plasmoalgorithms, a Collection of Decomposition Algorithms for Graph-Based Problem Representations

Mathematical programming has been successfully applied to solve decision-making problems in a variety of applications and industries, such as petroleum, chemical, pharmaceutical, and consumer products[1]. The success of the first experiences in these applications has continuously motivated the need for solving larger, and more complex problems. Furthermore, the recent focus on optimization under uncertainty has increased the problem sizes by at least one order of magnitude. At the same time solvers have improved significantly over the years[2], while computing hardware has not increased in speed but in number of parallel cores available. To keep improving and take advantage of this scenario the advancement of decomposition algorithms is necessary.

Currently, implementing and testing decomposition algorithms is a common and time consuming task in Process Systems Engineering (PSE) research. Lagrangean decomposition[3], Benders decomposition[4], and derived algorithms have been the choice for solving large-scale problems. The implementations of these algorithms are usually tailored to the application, there is an absence of general purpose implementations. A few attempts in this direction include the Benders decomposition implementation in CPLEX since version 12.7[5], and DSP[6], an implementation of dual decomposition for solving stochastic programming problems with integer recourse. The first one is a commercial code, while the second one is a complex code written in C++, making them hard to extend and improve.

We present PlasmoAlgorithms, a collection of general decomposition algorithms implemented in Julia programming language, using Plasmo[7] graphs as an input. Plasmo is a Julia package that allows the generation of graphs of models, where each node represents an independent model, and each edge represents a linking constraint. Since the Julia programming language is easy to code, and efficient, PlasmoAlgorithms is a good candidate to become a meeting place for the PSE and Operations Research communities to implement state-of-the-art algorithms, and for testing of novel ideas.

PlasmoAlgorithms currently includes implementations of multilevel Benders decomposition, Lagrangean decomposition, and Cross decomposition. The Benders implementation uses a multicuts, in which an independent cut is generated by each subproblem; and also includes cuts suitable for mixed-integer subproblems. The Lagrangean decomposition implementation includes several options for updating the multipliers, including a probing subgradient method, in which the bound of the candidate step is first probed to decide the length of the step taken. The Cross decomposition implementation follows the algorithm proposed by Mitra et al[8]. All the code is open source, and the implementations are modular enough to allow for easy extension of the algorithms.

References

[1] Grossmann, I.E., 2012. Advances in mathematical programming models for enterprise-wide optimization. Computers & Chemical Engineering, 47, pp.2-18.

[2] Bonami, P., Kilinç, M. and Linderoth, J., 2012. Algorithms and software for convex mixed integer nonlinear programs. In Mixed integer nonlinear programming (pp. 1-39). Springer, New York, NY.

[3] You, F. and Grossmann, I.E., 2013. Multicut Benders decomposition algorithm for process supply chain planning under uncertainty. Annals of Operations Research, 210(1), pp.191-211.

[4] Guignard, M. and Kim, S., 1987. Lagrangean decomposition: A model yielding stronger Lagrangean bounds. Mathematical programming, 39(2), pp.215-228.

[5] CPLEX, IBM ILOG, 12.7, User’s Manual for CPLEX, 2016.

[6] Kim, K. and Zavala, V.M., 2017. Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs. Mathematical Programming Computation, pp.1-42.

[7] Jalving, J., Abhyankar, S., Kim, K., Hereld, M. and Zavala, V.M., 2017. A graph-based computational framework for simulation and optimisation of coupled infrastructure networks. IET Generation, Transmission & Distribution, 11(12), pp.3163-3176.

[8] Mitra, S., Garcia-Herreros, P. and Grossmann, I.E., 2014. A novel cross-decomposition multi-cut scheme for two-stage stochastic programming. In Computer Aided Chemical Engineering (Vol. 33, pp. 241-246). Elsevier.