DeCODe: a community-based algorithm for generating high-quality decompositions of optimization problems

Andrew Allman, Wentao Tang, Prodromos Daoutidis

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


Nonconvex optimization problems, such as those often seen in chemical engineering applications due to integer decisions and inherent system physics, are known to scale poorly with problem size. Decomposition methods, such as Benders or Lagrangean decomposition, offer much promise for improving solution efficiency. However, automatically identifying subproblems for use with these solution methods remains an open problem. Herein, a general algorithmic framework entitled Detection of Communities for Optimization Decomposition (DeCODe) is presented. DeCODe uses community detection, a concept originating from network theory, to generate optimization subproblems which are strongly interacting within individual subproblems but weakly interacting between different ones. The importance of communities in solving problems using decomposition solution methods is showcased via a least squares regression problem. The ability of DeCODe to identify nontrivial decompositions of optimization problems is demonstrated through a large renewable energy and chemical production optimal design problem and two mixed integer nonlinear program test problems.

Original languageEnglish (US)
Pages (from-to)1067-1084
Number of pages18
JournalOptimization and Engineering
Issue number4
StatePublished - Dec 1 2019

Bibliographical note

Funding Information:
Financial support from the National Science Foundation and the University of Minnesota Initiative for Renewable Energy and the Environment (IREE) is gratefully acknowledged.

Publisher Copyright:
© 2019, Springer Science+Business Media, LLC, part of Springer Nature.


  • Automated subproblem generation
  • Community detection
  • Decomposition
  • Structure detection
  • Variable–constraint graph


Dive into the research topics of 'DeCODe: a community-based algorithm for generating high-quality decompositions of optimization problems'. Together they form a unique fingerprint.

Cite this