|
|
|
|
|
|
|
Modelos para problemas de árvores com restrições de salto e de diâmetro
|
| |
| |
|
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):
|
|
Date: |
|
| Start Time: |
14:30 |
|
Speaker: |
Luis Gouveia (Universidade de Lisboa)
|
|
Place: |
Room 5.5
|
| Research Groups: |
-Numerical Analysis and Optimization
|
|
See more:
|
<Main>
|
|
| |
|
|
|
|
|
|
|
|
|
