Skip to content

Latest commit

 

History

History
69 lines (50 loc) · 7.6 KB

README.md

File metadata and controls

69 lines (50 loc) · 7.6 KB
Raw

admMATLAB

admMATLAB is a MATLAB interface, which allows for decomposed optimization of any linear optimization problem. The decomposition is based on the consensus-based alternating direction method of multipliers (ADMM).

eXtremOS project

The admMATLAB interface has been developed within the scope of the BMWi (German Federal Ministry of Economics and Energy) funded research project eXtremOS. It is integrated to the energy system modelling framework ISAaR of the Forschungsstelle für Energiewirtschaft e.V. (FfE), in order to regionally decompose the energy system models built with it in order to investigate the runtime and working memory benefits of decomposition.

Contributors

The admMATLAB interface is developed by Soner Candas.

Functionality

Problem Input: As input, admMATLAB interface takes an arbitrary linear optimization problem in its matrix/vector form, and applies the decomposition according to an accompanying annotation vectors of its variables. The annotation vectors are a pair of vectors each with the length of the number of variables in the original optimiziation problem, and denote which variables belong internally to certain clusters, and which are the coupling variables between which clusters. For example, an annotation such as:

would define three clusters (1, 2 and 3), with:

  • the first two variables being internal variables to cluster 1,
  • the third and fourth variables being coupling variables between clusters 1 and 2,
  • the fifth variable being an internal variable to cluster 2,
  • the sixth and seventh varaibles being coupling variables between clusters 2 and 3 and
  • the eight variable being an internal variable to cluster 3.

The first and the second rows of this annotation matrix is defined as the variables cluster_id_from and cluster_id_to.

These inputs (problem definition and annotation) are set in the define_input() function.

**ADMM input: ** Besides the problem definition, ADMM-specific parameters have to be input on the runme script.

**ADMM modes: ** In this interface, four ADMM modes can be chosen from. These are categorized as follows:

  1. Regular ADMM (sequential): Subproblems are created for each cluster, which are solved after one another during each iteration. To activate this mode, use solver = 1 and num_threads = 1 as the first and third input arguments of the runme function.
  2. Regular ADMM (parallel): Subproblems are created for each cluster, which are solved in parallel during each iteration. To activate this mode, use solver = 1 and a num_threads > 1 as the first and third input arguments of the runme function.
  3. ADMM with bin packing algorithm (parallel): Groups of subproblems are collected in "bins". During each iteration, each subproblem within a given bin is solved after one another, and bins are solved in parallel to another. This method is developed as a countermeasure to the straggling effect, where the ADMM routine might lag because of a single, larger cluster requiring much longer to solve compared to the other clusters. To activate this mode, use solver = 2 and a num_threads > 1 as the first and third input arguments of the runme function.
  4. Asynchronous ADMM (parallel): Subproblems are created for each cluster, which are solved asynchronously. This way, each subproblem have their "local" iteration counters, and they can move onto the next iteration by receiving information from only one neighbor. Similar to the bin packing algorithm, this method is also developed as a countermeasure to the straggling effect. To activate this mode, use solver = 3 and a num_threads > 1 as the first and third input arguments of the runme function. For the details of this method, refer to the following paper: Asynchronous ADMM for Distributed Non-Convex Optimization in Power Systems
Regular ADMM (sequential) Regular ADMM (parallel) ADMM with bin packing Asynchronous ADMM
solver 1 1 2 3
num_threads higher than 1 higher than 1 higher than 1 higher than 1

**ADMM update methods: ** Moreover, five ADMM update methods can be chosen from. These are the following:

  1. Constant quadratic penalty: The quadratic penalty term is not adjusted between iterations (denoted in code as Gabay_constant_rho). To activate this update method, use admm_option = 1 as the second input argument of runme function.
  2. Adaptive quadratic penalty: By using absolute residuals, the quadratic penalty term is adjusted between iterations to improve convergence (denoted in code as Gabay_constant_rho). To activate this update method, use admm_option = 2 as the second input argument of runme function.
  3. Local quadratic penalty: By using their respective absolute residuals, the quadratic penalty terms for each cluster are adjusted between iterations to improve convergence separately (denoted in code as Gabay_constant_rho). To activate this update method, use admm_option = 3 as the second input argument of runme function.
  4. Restart method: To improve convergence, the quadratic penalty term is reset by a certain criterion (denoted in code as Gabay_constant_rho). To activate this update method, use admm_option = 4 as the second input argument of runme function.
  5. Relative residuals: By using the relative residuals, the quadratic penalty term is adjusted between iterations to improve convergence (denoted in code as Gabay_constant_rho). To activate this update method, use admm_option = 5 as the second input argument of runme function.

Requirements

This interface has been developed and tested on MATLAB R2019b. Additionally, the Optimization Toolbox and Parallel Computing Toolbox have to be installed.

Copyright

Copyright (C) 2021 TUM ENS

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/