2023-07-28 –, 32-155
Many optimization problems can be represented as a graph to provide useful visualization and to allow for manipulating and exploiting problem structure. We use Plasmo.jl (which extends JuMP.jl) to build optimization problems within a graph structure (where optimization model components are stored within the nodes and edges of the graph), and we use the nonlinear interior-point solver, MadNLP.jl, to solve these models and exploit some of these graph structures.
Graph theory can provide a useful scheme for representing and solving some structured optimization problems. Using graph theory, optimization problem components (e.g., variables, constraints, objective functions, or data) are stored within nodes and edges of a graph. This provides convenient visualization of the model, and it can lead to applications of various decomposition schemes to exploit the structure of the model. In this talk, I will present how we use Plasmo.jl and MadNLP.jl for building and solving graph-based optimization problems and how these packages can be used for exploiting some problem structures.
We use the package Plasmo.jl for building graph-based optimization problems [1]. This package extends JuMP.jl, and provides an interface for defining the optimization problem components within nodes and edges of a graph. Plasmo.jl uses an abstract modeling object called an OptiGraph which is composed of OptiNodes (similar to JuMP.jl’s Model object and which can store variables, constraints, objective functions, and data) and OptiEdges (which store constraints for variables on different OptiNodes and which capture connectivity of components).
We also use the package MadNLP.jl for solving graph-based optimization problems [2]. This package is a nonlinear interior-point solver similar to IPOPT. MadNLP.jl can interface with Plasmo.jl to solve problems defined within an OptiGraph, and it has the capability of exploiting OptiGraph structures using different decomposition schemes. Both Schwarz [2] and Schur [3] decompositions are enabled within MadNLP.jl, and these have been shown to reduce solution times. We are also interested in developing further decomposition schemes for graph-structured problems.
- Jalving, J., Shin, S., and Zavala, V.M. 2022. A graph-based modeling abstraction for optimization: concepts and implementation in Plasmo.jl. Math. Prog. Comp. 14: 699-747.
- Shin, S., Coffrin, C., Sundar, K., and Zavala, V.M. 2021. Graph-based modeling and decomposition of energy infrastructures. IFAC-Papers OnLine, 54(3): 693-698.
- Cole, D.L., Shin, S., and Zavala, V.M. 2022. A julia framework for graph-structured nonlinear optimization. Ind. Eng. Chem. Res., 61(26):9366-9380.
I am a 3rd year PhD candidate at the Unviersity of Wisconsin-Madison in chemical and biological engineering working under Professor Victor Zavala. My research interests include graph-based representations and optimization, energy systems, and process systems engineering.