betaFeedback

WorksMathematics

A Graph-Theoretic Framework for Identifying Mathematical Programming Decompositions

Abstract

We develop a framework for identifying combinations of complicating variables and/or constraints that can be used to formulate mathematical programming decompositions. A mathematical program is represented by a graph which accounts for the structural and functional relationship between variables and constraints. Graph projections are used to focus on variable- or constraint-based decompositions. A series of coarsening operations is used to generate a reduced graph based on the original or projected graph. On the reduced graph, we use integer programming to identify different combinations of complicating variables and/or constraints. Specifically, variables and constraints are identified as complicating based on their structural role and/or their functionality (contribution to nonlinearity) in the mathematical program. The framework allows us to assess the viability of different decomposition types (variable, constraint, cross) and identify multiple potential decomposition formulations of the same type (e.g. different combinations of complicating variables for Benders decomposition). The systematic nature of our framework facilitates broader studies into the efficacy of different decompositions across a range of problems including energy markets, process design, and machine learning.

Paper details

vlnc:W_mghcnq5j
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…