|
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):
|
