COMBINING METAHEURISTICS WITH MP SOLVERS, WITH APPLICATIONS TO THE GENERALIZED ASSIGNMENT PROBLEM (GAP) / COMBINANDO METAURÍSTICAS COM RESOLVEDORES MIP, COM APLICAÇÕES AO GENERALIZED ASSIGNMENT PROBLEM (GAP)

AUTOR(ES)

DANIEL AMARAL DE MEDEIROS ROCHA

DATA DE PUBLICAÇÃO

2009

RESUMO

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.

ASSUNTO(S)

combinatorial optimization metaheuristic otimizacao combinatoria metaeuristica

Documentos Relacionados

• INTEGRATING METAHEURISTICS WITH MIP SOLVERS TO THE CAPACITATED VEHICLE ROUTING PROBLEM
• MODELOS E ALGORITMOS PARA O PROBLEMA DE ALOCAÇÃO GENERALIZADA (PAG) E APLICAÇÕES
• Modelos de regressão para variáveis categóricas ordinais com aplicações ao problema de classificação
• DNA sequence of mip, a Legionella pneumophila gene associated with macrophage infectivity.
• Groups of diverse problem solvers can outperform groups of high-ability problem solvers