Decomposition for Large-Scale Optimization Problems: An Overview

Abstract

Formalizing complex processes and phenomena of a real-world problem may require a large number of variables and constraints, resulting in what is termed a large-scale optimization problem. Nowadays, such large-scale optimization problems are solved using computing machines, leading to an enormous computational time being required, which may delay deriving timely solutions. Decomposition methods, which partition a large-scale optimization problem into lower-dimensional subproblems, represent a key approach to addressing time-efficiency issues. There has been significant progress in both applied mathematics and emerging artificial intelligence approaches on this front. This work aims at providing an overview of the decomposition methods from both the mathematics and computer science points of view. We also remark on the state-of-the-art developments and recent applications of the decomposition methods, and discuss the future research and development perspectives.