Decomposition and aggregation in problems of large scale optimization

• Grant number: 96/01552-0
• Support Opportunities: Research Projects - Thematic Grants
• Start date: November 01, 1996
• End date: October 31, 1998
• Field of knowledge: Physical Sciences and Mathematics - Mathematics - Applied Mathematics
• Principal Investigator: Igor Semionovich Litvintchev
• Grantee: Igor Semionovich Litvintchev
• Host Institution: Instituto de Biociências, Letras e Ciências Exatas (IBILCE). Universidade Estadual Paulista (UNESP). Campus de São José do Rio Preto. São José do Rio Preto , SP, Brazil
• Associated research grant(s): 98/10032-5 - Necessery conditions of optimality for impulsive differential inclusions., AR.BR

Abstract

The main idea of aggregation is to condense (aggregate) the original problem into a smaller aggregated one. Then the disaggregated solution of the aggregated problem is used to form the (approximate in some sense) solution of the original one. The crucial questions are: a) construction of the aggregated problem; b) desegregation of the optimal solution of the aggregated problem into a "good" solution of the original one; c) estimation of the loss of optimality due to the use of approximate aggregated model and d) improvement of the aggregated problem, if the above estimate is not good. The above process is often done in a multistep framework, resulting in iterative aggregation. Moreover, many iterative aggregation approaches being applied in a special way to large-scale structured problems result in decomposition techniques as well. So there is a close connection between aggregation and decomposition. The work is currently focused on the following directions: 1) deriving new bounds for the loss of the accuracy due to the use of a small aggregated model; 2) application of iterative aggregation to special-structured, multi-division programming problems and investigation of resulting aggregation-decomposition techniques; 3) application of the aggregation approach to some non smooth optimal control problems and mixed integer programming (MIP). In the former case a new way to construct the (smooth) aggregated problem for impulse optimal control problems is considered. For MIP, the aggregated problem is used to compute bounds in the branch-and-cut framework, as well as to generate valid inequalities. (AU)