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

Andrew Allman, Wentao Tang, Prodromos Daoutidis

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

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
Volume20
Issue number4
DOIs
StatePublished - Dec 1 2019

Keywords

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

Fingerprint 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