Título
[pt] COMBINANDO METAURÍSTICAS COM RESOLVEDORES MIP, COM APLICAÇÕES AO GENERALIZED ASSIGNMENT PROBLEM (GAP)
Título
[en] COMBINING METAHEURISTICS WITH MP SOLVERS, WITH APPLICATIONS TO THE GENERALIZED ASSIGNMENT PROBLEM (GAP)
Autor
[pt] DANIEL AMARAL DE MEDEIROS ROCHA
Vocabulário
[pt] OTIMIZACAO COMBINATORIA
Vocabulário
[pt] PROGRAMACAO INTEIRA MISTA
Vocabulário
[pt] METAEURISTICA
Vocabulário
[en] COMBINATORIAL OPTIMIZATION
Vocabulário
[en] MIXED INTEGER PROGRAMMING
Vocabulário
[en] METAHEURISTIC
Resumo
[pt] Métodos que combinam estratégias normalmente encontradas em algoritmos metaeurísticos com técnicas para resolver problemas de programação inteira mista (MIP) têm apresentado ótimos resultados nos últimos anos. Este trabalho propõe dois novos algoritmos nessa linha: um algoritmo que faz pós-processamento nas soluções encontradas pelo resolvedor MIP. Os dois algoritmos utilizam um novo tipo de vizinhança, chamada de vizinhança elipsoidal, que possui fortes semelhanças com as técnicas de relinking de algoritmos PR e que neste trabalho é generalizada e extendida para múltiplas soluções. O problema generalizado de alocação (GAP) é usado para os experimentos. São testados também um resolvedor MIP puro (ILOG CPLEX versão 11) e um algoritmo branch and price que utiliza as heurísticas RINS e guided dives. Os algoritmos testados são comparados entre e com heurísticas específicas para o GAP. Os resultados são satisfatórios e indicam que as vizinhanças elipsoidais conseguem frequentemente melhorar as soluções encontradas pelo resolvedor MIP, encontrando a melhor solução para algumas instâncias.
Resumo
[en] Methods that mix strategies usually found in metaheristic algorithms with techniques to solve mixed integer programming problems (MIPs) have had great results over the past few years. This wprk proposes two new algorithms in this philosophy: one is based on the Path Relink (PR) metaheuristc, while the other one is a simple algorithm that does post-processing in the solutions found by the MIP solver. Both algorithms use a new neighborhood structure, called ellipsoidal neighborhood, that has strong resemblances with the relinking step from PR algorithms and that, in this work, is generalized and extended for multiple solutions. The generalized assignment problem (GAP) is used for the computational experiments. Also tested are MIP solver (ILOG CPLEX version 11) and a branch and price algorithm that uses the RINS and guides dives heuristics. The tested algorithms are compared among themselves and with GAP-specific heuristics. The results are satisfactory and show that the ellipsoidal neighborhood can frequently improve the solutions found by the MIP solver, even finding the best result for some instances.
Orientador(es)
MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO
Banca
MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO
Banca
EDUARDO SANY LABER
Banca
LORENZA LEAO OLIVEIRA MORENO
Catalogação
2010-03-08
Apresentação
2009-08-11
Tipo
[pt] TEXTO
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Idioma(s)
PORTUGUÊS
Referência [pt]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=15363@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=15363@2
Referência DOI
https://doi.org/10.17771/PUCRio.acad.15363
Arquivos do conteúdo
CAPA, AGRADECIMENTOS, RESUMO, ABSTRACT, SUMÁRIO E LISTAS PDF CAPÍTULO 1 PDF CAPÍTULO 2 PDF CAPÍTULO 3 PDF CAPÍTULO 4 PDF CAPÍTULO 5 PDF CAPÍTULO 6 PDF CAPÍTULO 7 PDF CAPÍTULO 8 PDF CAPÍTULO 9 PDF REFERÊNCIAS BIBLIOGRÁFICAS PDF