A computational study of cuts derived from the Chvatal-Gomory cut for interger programming problems / Um estudo computacional de cortes derivados do corte Chvatal-Gomory para problemas de programação inteira
AUTOR(ES)
Sara Luisa de Andrade Fonseca
DATA DE PUBLICAÇÃO
2007
RESUMO
Em 1958, Gomory propôs uma desigualdade válida ou corte a partir do tableau do método simplex para programação linear, que foi utilizado no primeiro método genérico para resolução de problemas de programação inteira. Em 1960, o corte foi estendido para problemas de programação inteira mista. Em 1973, Chvátal sugeriu um corte derivado da formulação original do problema de programação inteira, e devido à equivalência com o corte de Gomory, este passou a ser chamado de corte de Chvátal-Gomory. A importância do corte de Gomory só foi reconhecida em 1996 dentro do contexto do método branch-and-cut para resolução de problemas de programação inteira e programação inteira mista. Desde então, este corte é utilizado em resolvedores comerciais de otimização. Recentemente, diversos cortes novos derivados do corte de Chvátal-Gomory foram propostos na literatura para programação inteira. Este trabalho trata do desenvolvimento de algoritmos para alguns destes cortes, e implementação computacional em um contexto de branch-and-cut, no ambiente do resolvedor CPLEX. A eficácia dos cortes é testada em instâncias dos problemas da mochila multidimensional, designação generalizada e da biblioteca MIPLIB.
ASSUNTO(S)
branch-and-cut integer programming programação linear cuts valid inequalities pesquisa operacional chvatal-gomory programação inteira algoritmos
ACESSO AO ARTIGO
http://libdigi.unicamp.br/document/?code=vtls000429131Documentos Relacionados
- Algoritmos relax-and-cut para problemas de programação inteira 0-1
- Um algoritmo genético para a solução de problemas específicos de programação inteira.
- INTEGER PROGRAMMING PROBLEMS ON TELECOMMUNICATIONS OPTICAL NETWORKS
- RESOLUÇÃO DE PROBLEMAS DE LOGÍSTICA FERROVIÁRIA UTILIZANDO PROGRAMAÇÃO INTEIRA
- Metodo heuristico eficiente para problemas de programação linear inteira com dimensão completa