Decomposição e agregação em problemas de otimização de grande porte

• Processo: 96/01552-0
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Data de Início da vigência: 01 de novembro de 1996
• Data de Término da vigência: 31 de outubro de 1998
• Área do conhecimento: Ciências Exatas e da Terra - Matemática - Matemática Aplicada
• Pesquisador responsável: Igor Semionovich Litvintchev
• Beneficiário: Igor Semionovich Litvintchev
• Instituição Sede: 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, Brasil
• Auxílio(s) vinculado(s): 98/10032-5 - Necessery conditions of optimality for impulsive differential inclusions., AR.BR; 97/03781-9 - A posteriori bounds for variable aggregation in integer programing., AR.EXT; 97/03782-5 - Nonsmooth continuos-time optimization problems: sufficient conditions., AR.EXT; 96/09705-0 - Marko rojas medar | Inst matemática estatística computação cientifica/unicamp - Brasil, AV.BR
• Assunto(s): Métodos de decomposição Otimização matemática Teoria de sistemas e controle Controle ótimo Programação matemática Programação inteira e fluxos em rede
• Palavra(s)-Chave do Pesquisador: Agregacao | Controle Otimo | Decomposicao | Otimizacao | Programacao Inteira | Subdiferenciabilidade

Resumo

O objetivo do presente projeto é investigar o uso das técnicas de agregação-decomposição para novas classes de problemas tais como: otimização subdiferenciável e programação inteira mista. A idéia principal da técnica de agregação é inicialmente condensar (agregar) o problema original obtendo um problema agregado de menor dimensão. A solução do problema agregado é então "desagregada" e usada como uma solução aproximada Para o problema original. Várias questões se apresentam: a) construir o problema agregado; b) desagregar a solução ótima do problema agregado de forma a obter uma "boa" solução para o problema original; c) estimar a perda de otimalidade devido ao uso da solução do modelo agregado; d) melhorar o modelo agregado se a estimativa obtida acima não for "boa". Esta metodologia é geralmente utilizada em um procedimento iterativo onde a cada iteração as questões a)-c) são respondidas. Além disso, quando aplicado a problemas estruturados o processo de agregação iterativo pode resultar em um processo de decomposição. Logo, existe uma forte relação entre agregação e decomposição. O projeto esta concentrado em três aspectos da teoria de agregação: 1) melhora da estimativa da perda de otimalidade devida a agregação; 2) aplicação da técnica de agregação iterativa a problemas especialmente estruturados e estudo da relação com técnicas de decomposição; 3) aplicação da técnica de agregação a problemas de otimização sub diferenciável e programação inteira mista. No primeiro caso, uma nova forma de construir o problema agregado esta sendo proposta. Na resolução de problemas de programação inteira mista esta sendo investigado o uso do problema agregado no calculo de limitantes e geração de desigualdades válidas para o algoritmo branch and cut. (AU)