O Problema do Caixeiro Viajante Assimétrico: Formulações Naturais versus Formulações Estendidas
Luís Gouveia
Dep. Estatística e Inv. Operacional, Fac. Ciências, Univ. Lisboa

Resumo

Nesta apresentação discutimos várias formulações para o Problema de Caixeiro Viajante Assimétrico (PCVA). Considerando um grafo G = (V,A) com custos associados a cada elemento de A (arcos), o PCVA consiste em determinar o circuito hamiltoniano (circuito que passa uma e uma só vez por cada nodo) de custo mínimo. Formulações para o PCVA podem ser agrupadas em duas grandes classes: formulações "naturais" que contêm apenas uma variável para cada arco do grafo e formulações "estendidas" que envolvem outras variáveis (que podem, ou não, estar também associados aos arcos do grafo) e que contém informação adicional sobre o problema. Estas variáveis adicionais podem ser consideradas supérfluas no sentido em que não são necessárias para formular o problema. Formulações naturais envolvem um número exponencial de restrições. A informação adicional associada às novas variáveis de uma formulação estendida permite escrever formulações válidas para o problema que envolvem apenas um número polinomial de restrições. É de notar que, usualmente, o primeiro contacto de modelação que um investigador tem com um novo problema, se traduz precisamente na idealização de uma formulação estendida. Por projecção, no subespaço das variáveis naturais, do conjunto das soluções admissíveis da relaxação em programação linear da formulação estendida, é possível obter uma formulação natural com relaxação linea equivalente. Contudo, e como foi dito antes, tais formulações envolvem um número exponencial de restrições.
Nesta apresentação, e no contexto do PCVA, tentaremos ilustrar alguns dos conceitos mencionados acima:
i) tentar mostrar que pode não ser fácil encontrar "à primeira" uma formulação natural para um problema de desenho de redes
ii) tentar dar idéias de como "criar" novas variáveis e novas restrições para modelar o problema.
iii) por projecção, obter umas formulação natural que envolve restrições complicadas que à primeira vista, não são fáceis de idealizar
iv) mostrar que após o conhecimento de algumas restrições complicadas, outras (e mais fortes) podem ser obtidas através de truques convencionais de programação linear inteira.
Na ilustração indicada acima, utilizaremos formulações bem conhecidas da literatura do PCVA.

Na parte final, mostraremos como ir além das melhores formulações antes apresentadas utilizando agumas propriedades do problema e o conceito de reformulação de caminhos (que é uma técnica para criar formulações estendidas com relaxações lineares relativamente fortes).

Tarde de Trabalho SPM/CIM em Teoria de Grafos e Combinatória