(51b) Graph-Based Modeling Abstractions and Computational Tools for Complex Systems

Authors: 
Jalving, J., University of Wisconsin Madison
Zavala, V. M., University of Wisconsin-Madison
This talk presents advances in graph-based modeling abstractions and computational tools for complex systems [1]. Under the proposed graph-based abstraction, a complex system is represented as a collection of algebraic optimization models that live on nodes and that are connected through edges representing linking constraints between algebraic models. The graph abstraction can be exploited to create nested/hierarchical graphs in which a node can be a graph model itself. These features can be exploited to model coupled heterogeneous and multi-scale networks (e.g., supply chains, biological networks, and infrastructure networks). The graph abstraction also enables the modeler to perform partitioning, aggregation, and community detection tasks, which are commonly used in the design of decomposition strategies [2]. The graph abstraction also facilitates model processing (e.g., computation of derivatives) and analysis (e.g., visualization and data management) as well as the development of interfaces with existing standard and structured solvers [3,4].

We also show that a graph-based abstraction can be naturally be extended to represent computational workflows. A computational workflow is a virtual graph in which a collection of computational tasks live in nodes and edges represent communication links between tasks. This abstraction generalizes other modeling paradigms such as discrete-event and agent-based simulation, naturally accommodates computational algorithms, and enables the simulation of synchronous and asynchronous computing environments [5]. A computational workflow can be used to simulate the performance of algorithms such as Benders decomposition, decentralized control architectures, markets, and swarm robotic systems under communication and decision-making delays and failures [6,7,8,9]. We discuss an implementation of a graph-based modeling platform in Julia, that we call Plasmo.jl.

[1] Jalving, J., Abhyankar, S., Kim, K.,Hereld, M., Zavala, V. M. A Graph-Based Computational Framework for Simulation and Optimization of Coupled Infrastructure Networks. To Appear in IET Generation, Transmission & Distribution, 2016.

[2] Tang, W., Allman, A., Pourkargar, D. B., & Daoutidis, P. (2017). Optimal decomposition for distributed optimization in nonlinear model predictive control through community detection. Computers & Chemical Engineering, 111, 43–54

[3] N. Chiang, C. G. Petra, and V. M. Zavala. Structured nonconvex optimization of large-scale energy systems using PIPS-NLP. In Proc. of the 18th Power Systems Computation Conference (PSCC), Wroclaw, Poland, 2014.

[4] K. Kim and V. M. Zavala. Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs. Optimization Online, 2015

[5] Cassandras, C. G., & Lafortune, S. Introduction to Discrete Event Systems, (2008).

[6] Ruszczyński, Andrzej P. Nonlinear optimization. Vol. 13. Princeton university press, 2006.

[7] J. B.Rawlings and D. Mayne. Model predictive control: theory and design. Nob Hill Publishing, 2009.

[8] Lopes, Y. K., Trenkwalder, S. M., Leal, A. B., Dodd, T. J., & Groß, R. (2016). Supervisory control theory applied to swarm robotics. Swarm Intelligence, 10(1), 65–97.

[9] Scott, W. Naomi L. (2017). Optimal evasive strategies for groups of interacting agents with motion constraints, (January), 1–12.