Decomposition is a general approach to solving a problem by breaking it up into smaller ones and solving each of the smaller ones separately, either in parallel or sequentially. The logic behind decomposition is to solve iteratively the large-scale complex mixed-integer problems, which can not be efficiently solved altogether by the commercial solvers.
It separates the problem into two related problems (a master problem and subproblem) by classifying the constraints of the problem into “easy constraints” and “difficult constraints”. The master problem typically contains discrete variables with “easy constraints” and provides an upper bound for the original problem. The “difficult constraints” are moved to the subproblem, which gives a lower bound and generates Benders cuts for the master problem. These two problems are solved iteratively in a delayed-constraint-generation fashion and finally, converge to a globally optimal solution.
On the sideline, decomposition has some benefits, especially when there is some coupling or interaction between subproblems and with the master problem such as in the case of market and trading problems. This interaction can be effectively modeled using this decomposition in many problems.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs