|
Description: |
Para obter modelos fortes para cada um dos problemas propostos, é necessário ter uma boa representação do poliedro associado a um problema de determinação de 1 caminho com um numero máximo de arcos. Descrevem-se formulações estendidas para este subproblema. Em particular, apresenta-se uma formulação compacta que se baseia no facto deste problema
poder ser visto como um problema de determinação de 1 caminho (sem a
restrição adicional), num grafo espandido. O problema com a restrição de diâmetro e (aparentemente) mais dificil, já que envolve a restrição na dimensão dos caminhos entre cada par de nodos, enquanto que o outro problema (com restrições de salto) envolve apenas
restrições entre un nodo especifico e todos os outros. Discutem-se técnicas (basedas no conceito de "centro" de uma árvore) para transformar, em certa medida, o problema com restrições de diâmetro no problema com restrições de salto.
Trabalho conjunto com Thomas Magnanti (MIT) e Cristina Requejo (Univ de Aveiro).
Area(s):
|
