Degeneração e estabilização do método de geração de colunas

• Processo: 10/05922-5
• Modalidade de apoio: Bolsas no Exterior - Pesquisa
• Data de Início da vigência: 01 de agosto de 2010
• Data de Término da vigência: 31 de julho de 2011
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Marcos Antonio Pereira
• Beneficiário: Marcos Antonio Pereira
• Pesquisador Anfitrião: Jacques Desrosiers
• Instituição Sede: Faculdade de Engenharia (FEG). Universidade Estadual Paulista (UNESP). Campus de Guaratinguetá. Guaratinguetá , SP, Brasil
• Instituição Anfitriã: École des Hautes Études Commerciales (HEC Montréal), Canadá
• Assunto(s): Otimização combinatória Problemas de localização de facilidades Métodos de geração de colunas
• Palavra(s)-Chave do Pesquisador: Método de Geração de Colunas | Otimização combinatória de grande porte | Problema de localização de máxima cobertura | Técnicas de estabilização | Programação inteira

Resumo

Com os recentes avanços computacionais, os sistemas comerciais de otimização tornaram-se mais rápidos e confiáveis. Com isso, renovou-se o desenvolvimento de métodos baseados na técnica de geração de colunas, permitindo sua aplicação para a obtenção de soluções de problemas de otimização combinatória de grande porte em tempos computacionais razoáveis. A técnica de geração de colunas pode ser aplicada a problemas lineares de grande porte cujo conjunto de variáveis não é totalmente conhecido a priori, ou quando se pretende resolvê-lo com a aplicação da técnica de decomposição de Dantzig-Wolfe. Sabe-se que a aplicação direta dessa técnica produz muitas colunas que não são relevantes na solução final, prejudicando a convergência do processo de solução. Nestes casos, observa-se que ocorre uma oscilação das soluções duais em torno da solução dual ótima, o que justifica a aplicação de algum processo de estabilização para prevenir este comportamento e acelerar o processo de resolução do problema. Este projeto pretende investigar técnicas de estabilização/aceleração para resolver problemas de localização de máxima cobertura, cuja formulação como um problema de particionamento de conjuntos apresenta-se como um grande desafio para a aplicação da técnica de geração de colunas. (AU)