Experimentos computacionais para programação inteira mista

• Processo: 14/02206-8
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Iniciação Científica
• Data de Início da vigência: 15 de maio de 2014
• Data de Término da vigência: 14 de agosto de 2014
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Orlando Lee
• Beneficiário: Allan Sapucaia Barboza
• Supervisor: Ricardo Fukasawa
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Instituição Anfitriã: University of Waterloo, Canadá
• Vinculado à bolsa: 13/12551-1 - Estudo e comparação de algoritmos para problemas de fluxo em redes, BP.IC
• Assunto(s): Otimização combinatória Problema do caixeiro viajante (PCV) Programação linear inteira mista Estágios
• Palavra(s)-Chave do Pesquisador: Approximate Linear Programming | Branch-Cut-and-Price | problema do caixeiro viajante | programação inteira | Otimização Combinatória

Resumo

O problema do caixeiro viajante (TSP, do inglês: traveling salesman problem) pode ser descrito como: dado um conjunto de cidades e custos de viagem entre cada par de cidades, o "caixeiro" deseja visitar todas as cidades uma única vez e retornar à cidade inicial, com o menor custo total possível. O objetivo deste projeto é comparar duas hierarquias de limitantes inferiores sucessivamente mais justos para o TSP: Approximate Linear Programming e Branch-Cut-and-Bound. Isto pode ser feito empiricamente, implementando as duas diferentes famílias de limitantes e comparando os valores em instâncias reais. O estudo também pode ser feito teoricamente, tentando demonstrar que o limitante de uma das famílias sempre será melhor que o da outra, ou produzir contraexemplos mostrando que tal resultado é impossível. (AU)