SNoGloDe: A Structured Nonlinear Global Decomposition Solver

Stinchfield, Georgia [Carnegie Mellon University (CMU)]; Bhatia, Arsh [Carnegie Mellon University (CMU)]; Bynum, Michael [Sandia National Laboratories (SNL)]; Cao, Yankai [University of British Columbia]; Laird, Carl [Carnegie Mellon University (CMU)]

DOE OSTI · 2575013

SNoGloDe: A Structured Nonlinear Global Decomposition Solver

Stinchfield, Georgia [Carnegie Mellon University (CMU)]·Bhatia, Arsh [Carnegie Mellon University (CMU)]·Bynum, Michael [Sandia National Laboratories (SNL)]·Cao, Yankai [University of British Columbia]·Laird, Carl [Carnegie Mellon University (CMU)]

View original source ↗Read source document ↗Export metadata ↓

Abstract

Large-scale optimization problems often require decomposition strategies and customized algorithms to achieve optimal solutions within a reasonable time. Building on the work of Cao and Zavala (2019) for solving nonlinear two-stage stochastic programs to global optimality, we implement and extend their approach. We generalize to optimization problems reformulated with a block-angular constraint structure (e.g., temporal decomposition). Our framework, written in Python using Pyomo, is highly customizable and enables parallel execution of the decomposition. SNoGloDe allows tailored branching strategies, lower bounding problems, and candidate generators to leverage problem-specific knowledge. To demonstrate effectiveness, we compare SNoGloDe’s performance with Gurobi on a temporally decomposed produced water case study.

Explore related subjects

algorithms optimization planning and scheduling

Keep this discovery

Explore connections, maps & timelines

BibTeX RIS

Stinchfield, Georgia [Carnegie Mellon University (CMU)], Bhatia, Arsh [Carnegie Mellon University (CMU)], Bynum, Michael [Sandia National Laboratories (SNL)], Cao, Yankai [University of British Columbia], Laird, Carl [Carnegie Mellon University (CMU)]. 2025-07-07. SNoGloDe: A Structured Nonlinear Global Decomposition Solver. https://www.osti.gov/biblio/2575013

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related reports

DOE OSTI2025

Extracting scattering amplitudes for arbitrary two-particle systems with one-particle left-hand cuts via lattice QCD

We derive a general formalism that relates the spectrum of two-particle systems in a finite volume to physical scattering amplitudes, taking into account the presence of any left-hand branch cuts due to single-particle exchanges. The method first relates the finite-volume spectrum to an infinite-volume short-range quantity, denoted ${\mathcal{M}}_0$, and then relates the latter to the physical scattering amplitudes via known integral equations. The derivation of both relations is performed using all-orders perturbation theory and is exact up to neglected exponentially suppressed volume dependence. The relations hold for arbitrary two-particle systems with any number of coupled channels, non-identical and non-degenerate particles, and any intrinsic spin.

algorithms↗

DOE OSTI2025

Sempervirens: A Fast Reconstruction Algorithm for Noisy and Incomplete Binary Matrix Representations of Trees

Applications such as reconstructing cell lineage trees (represented as phylogenetic trees) from single-cell sequencing data require reconstructing a {0,1}-matrix that has many errors and missing entries. We introduce Sempervirens, a very fast matrix reconstruction algorithm for noisy and incomplete matrix representations of phylogenetic trees. Sempervirens uses an iterative maximum-likelihood approach to determine the topology tree represented by the corrupted data. We show that Sempervirens is at least three orders of magnitude faster than other methods on thousand by thousand matrices, with the speed gap widening with larger matrices. We also show that Sempervirens matches state-of-the-art methods in reconstruction accuracy. The speed of Sempervirens enables it to be tractably applied to reconstructing much larger matrices than those that other methods can reconstruct. In addition to experimental results, we justify the algorithm with a mathematical treatment of its subprocedures.

algorithms↗

DOE OSTI2025

DONKEY: A Flexible and Accurate Algorithm for Clustering

We propose an accurate clustering algorithm suitable for the varied and multidimensional data sets that correspond to temporal snapshots from on-the-fly nonadiabatic trajectory-based simulations of photoexcited dynamics. The algorithm approximates the underlying probability density function using variable kernel density estimation, with local maxima corresponding to cluster centers. Each data point is then assigned to one of the maxima by employing a maximization procedure. Finally, clusters artificially separated by minor fluctuations in the probability density are merged. The algorithm does not require parameter tuning, which ensures flexibility and reduces the risk of bias. It is tested on several synthetic data sets, where it consistently outperforms conventional clustering algorithms. As a final example, the algorithm is applied to the excited dynamics of the norbornadiene ⇌ quadricyclane (C 7 H 8 ) molecular photoswitch, demonstrating how distinct reaction pathways can be identified.

algorithms↗