A Graph-Based, Distributed Memory, Modeling Abstraction for Optimization

David L. Cole 1 , Jordan Jalving 2 , Jonah Langlieb 3 , Jesse D. Jenkins 1,4 1 Andlinger Center for Energy and Environment Princeton University, Princeton, NJ 08540, USA 2 Artificial Intelligence and Modeling Simulation Atomic Machines Inc., Emeryville, CA 94608, USA 3 Department of Computer Science · 2025

Read A Graph-Based, Distributed Memory, Modeling Abstraction for Optimization by David L. Cole 1 , Jordan Jalving 2 , Jonah Langlieb 3 , Jesse D. Jenkins 1,4 1 Andlinger Center for Energy and Environment Princeton University, Princeton, NJ 08540, USA 2 Artificial Intelligence and Modeling Simulation Atomic Machines Inc., Emeryville, CA 94608, USA 3 Department of Computer Science (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-14966.txt.

Introduction

David L. Cole, Jordan Jalving, and two co-authors extend a graph-based modeling language so optimization problems can live across many computers at once. In the Plasmo framework, a problem is drawn as a hypergraph: nodes hold subproblems with their own variables and goals, and edges hold the constraints that link them. Big real problems, though, spill past one machine's memory.

The new RemoteOptiGraph lets those hypergraphs run in distributed memory, with special edges that manage links spanning different workers. Modelers get one unified way to state a huge problem instead of hand-crafting each distributed version. The abstraction also gives algorithm designers a shared target for methods that exploit the distributed structure.

Catalog record

CREATORDavid L. Cole 1 , Jordan Jalving 2 , Jonah Langlieb 3 , Jesse D. Jenkins 1,4 1 Andlinger Center for Energy and Environment Princeton University, Princeton, NJ 08540, USA 2 Artificial Intelligence and Modeling Simulation Atomic Machines Inc., Emeryville, CA 94608, USA 3 Department of Computer Science
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-14966

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Graph-Based, Distributed Memory, Modeling Abstraction for Optimization David L. Cole 1 , Jordan Jalving 2 , Jonah Langlieb 3 , Jesse D. Jenkins 1,4 1 Andlinger Center for Energy and Environment Princeton University, Princeton, NJ 08540, USA 2 Artificial Intelligence and Modeling Simulation Atomic Machines Inc., Emeryville, CA 94608, USA 3 Department of Computer Science Princeton University, Princeton, NJ 08540, USA 4 Department of Mechanical and Aerospace Engineering Princeton University, Princeton, NJ 08540, USA ∗ Corresponding author email address: [email protected] Abstract We present a general, flexible modeling abstraction for building and working with distributed optimization problems called a RemoteOptiGraph. This abstraction extends the OptiGraph model in Plasmo.jl, where optimization problems are represented as hypergraphs with nodes that define modular subproblems (variables, constraints, and objectives) and edges that encode algebraic linking constraints between nodes. The RemoteOptiGraph allows OptiGraphs to be utilized in distributed memory environments through InterWorkerEdges, which manage linking constraints that span workers. This abstraction offers a unified approach for modeling optimization problems on distributed memory systems (avoiding bespoke modeling approaches), and provides a basis for developing general-purpose meta-algorithms that can exploit distributed memory structure such as Benders or Lagrangian decompositions. We implement this abstraction in the open-source package, Plasmo.jl and we illustrate how it can be used by solving a mixed integer capacity expansion model for the western United States containing over 12 million variables and constraints. The RemoteOptiGraph abstraction together with Benders decomposition performs 7.5 times faster than solving the same problem without decomposition. Keywords : Optimization, Graph Theory, Distributed Memory, Parallel Computing, Julia. 1 Introduction Frontiers in mathematical optimization continue to shift toward ever greater scale and complexity. Practitioners often consider problems with millions (or even billions) of variables driven by demands of applications that span large-scale energy systems [ 26 , 56 ] , enterprise/area-wide scheduling and operations [ 7 , 12 , 29 , 33 ] , or expansive supply chains [ 23 , 42 , 48 ] . Advances in high-performance and cloud computing (HPC and CC) [ 31 , 49 ] have made it possible to solve increasingly larger-scale optimization problems using distributed memory and parallel computation. However, fully exploiting HPC and CC resources requires structure-exploiting optimization algorithms implemented in a distributed manner, which is difficult because it requires integrating optimization modeling tools with distributed memory architectures. To the authors’ knowledge, no generalized distributed modeling framework for implementing such algorithms has yet emerged. Most distributed optimization algorithms today are implemented in an ad-hoc manner, where decomposition strategies are applied on top of existing algebraic modeling languages such as JuMP [ 35 ] , Pyomo [ 10 ] , AMPL [ 21 ] , or GAMS [ 22 ] . In these approaches, the modeling framework itself does not represent distributed structure; instead, developers implement bespoke strategies to partition models, coordinate subproblem solves, and exchange information between them, often using various tools for distributed or parallel processes (e.g., the Message Passing Interface (MPI) [ 24 ] , Dask in Python [ 18 ] , or Distributed.jl in Julia [ 6 ] ). This separation creates a gap: while distributed algorithms exist, the models themselves cannot be authored natively in a distributed form. Consequently, meta-algorithms—such as Benders decomposition [ 3 , 44 ] , alternating direction methods of multipliers (ADMM) [ 8 ] , or progressive hedging [ 45 ] —are often implemented in ways that are specific to the application’s problem structure and chosen modeling language. These bespoke implementations increase programming effort (e.g., repeated implementation of the same meta-algorithms in different contexts), slows the accretion of cumulative improvements in algorithmic performance and limits the broader use of successful algorithms across different contexts. These challenges can be addressed by creating a generalized abstraction for working with distributed optimization problems. The need for a general abstraction for distributed optimization is highlighted by several use cases that arise in literature. First, many problems have an inherent distributed communication structure [ 5 , 57 ] . For example, in many power system and control problems, there is a central planner that is optimizing a larger system with limited knowledge of data on distributed entities within the system [ 39 , 41 , 54 ] . In these cases, subproblems, representing distributed entities, can be solved separately (and sometimes asynchronously) and communicate their results back to the central planner or to other subproblems [ 2 , 5 ] . None of these problems, to our knowledge, use a generalized framework for modeling the distributed structure. Second, many structure-exploiting meta-algorithms [ 16 , 26 ] are necessary for solving distributed problems, but these are typically implemented in a bespoke manner for specific applications. As examples, Benders decomposition [ 3 , 27 , 44 ] , Lagrangian relaxations [ 8 , 11 , 20 , 52 ] , progressive hedging [ 45 , 46 ] , Schur decomposition [ 15 , 30 , 32 , 53 , 55 ] , and Schwarz decomposition [ 28 , 40 , 47 ] have all been implemented in parallel fashions, but in problem-specific ways that hinder general reuse across domains. Generalizing these algorithms within a unified distributed abstraction would simplify their application to new problem domains. Third, some problems are intractable due to problem size (e.g., there can be practical memory limitations such that the solver cannot run all necessary steps to reach optimality; see for example [ 27 , 56 ] ). Solving these then can require decomposing the problem into subproblems that are run on multiple processors, requiring practitioners to integrate distributed memory tools with their algebraic modeling languages – a specialized technical task which can be abstracted over by using a more general modeling framework. A prominent modeling paradigm for providing flexible and general modeling capabilities is to represent optimization problems using graph theoretic concepts where optimization problems are represented by collections of nodes and edges. Multiple approaches have been proposed for capturing problem structure via graphs. Some approaches, proposed by Daoutidis and co-workers [ 1 , 17 , 37 , 38 , 50 , 51 ] , include a variable graph (where each variable is a node and edges connect variable nodes that arise in the same constraint), a constraint graph (where each constraint is a node with edges that connect nodes with a common variable), and a bipartite graph (where variables and constraints are different types of nodes). These graph representations allow for different problem decomposition schemes into subproblems via graph partitioning or community detection algorithms. The resulting subproblems can be used in various decomposition-based solution strategies including Benders decomposition. An alternative approach is presented by Jalving and co-workers [ 28 ] which is based on an abstraction called an OptiGraph, in which nodes contain objectives, variables, and constraints, and hyperedges encapsulate constraints over variables on different nodes. This latter approach is also similar to that used by [ 4 ] . The OptiGraph abstraction, implemented in the open-source package Plasmo.jl, provides significant modeling flexibility as it allows for capturing hierarchical structures, supports restructuring the graph, and supports the aforementioned decomposition capabilities [ 14 ] . In this work, we extend the OptiGraph abstraction for the case of distributed memory applications and introduce a new abstraction called a

Read the complete text