|
|
|
|
|
|
|
Modelos para o problema da árvore de suporte com restrições de diâmetro ímpar
|
| |
| |
|
Description: |
O problema da Árvore de Suporte de Custo Mínimo com restrições de Diâmetro (ASCM-D) consiste em determinar a árvore de suporte de menor custo tal que para cada par de nodos o único caminho que os une tem um limite máximo D (diâmetro) no seu comprimento. Este é um problema NP-difícil quando D$\geq$4. Num estudo prévio do problema usando formulações de fluxos em redes Gouveia e Magnanti (2003) obtiveram piores resultados para o problema ASCM-D quando o parâmetro D é ímpar.
Apresentamos várias abordagens que nos permitem obter modelos para o caso particular do problema com diâmetro ímpar. Discutiremos, em particular, um modelo obtido usando técnicas de programação disjuntiva. A programação disjuntiva é aplicada a um subproblema relacionado com o problema da selecção da aresta central. O modelo para o subproblema fornece uma descrição estendida do envolvente convexo do conjunto das soluções inteiras. Combinando este modelo para o subproblema com um modelo básico para o problema obtemos um novo modelo para o problema ASCM-D quando D é ímpar cuja relaxação linear é mais forte.
Os resultados computacionais que apresentamos indicam que os gaps para o novo modelo são muito melhores que os obtidos pelo modelo de Gouveia e Magnanti (2003). Além disso fomos capazes de resolver instâncias Euclideanas que não tinham sido resolvidas pelo modelo anterior.
Area(s):
|
|
Date: |
|
| Start Time: |
14.30 |
|
Speaker: |
Cristina Agra (Universidade de Aveiro)
|
|
Place: |
Room 5.5
|
| Research Groups: |
-Numerical Analysis and Optimization
|
|
See more:
|
<Main>
|
|
| |
|
|
|
|
|
|
© 2012 Centre for Mathematics, University of Coimbra, funded by
Powered by: rdOnWeb
v1.4 | technical support
|
|
|
|
