Graph-Based modeling and decomposition of hierarchical optimization problems

Abstract We present a graph-theoretic modeling approach for hierarchical optimization that leverages the OptiGraph abstraction implemented in the package . We show that the abstraction is flexible and can effectively capture complex hierarchical connectivity that arises from decision-making over multiple spatial and temporal scales (e.g., integration of planning, scheduling, and operations in manufacturing and infrastructures). We also show that the graph abstraction facilitates the conceptualization and implementation of decomposition and approximation schemes. Specifically, we propose a graph-based Benders decomposition (gBD) framework that enables the exploitation of hierarchical (nested) structures and that uses graph aggregation/partitioning procedures to discover such structures. In addition, we provide a implementation of gBD, which we call . We illustrate the capabilities using examples arising in the context of energy and power systems.