Logo PUC-Rio Logo Maxwell
ETDs @PUC-Rio
Estatística
Título: THE MULTI-PERIOD PRIZE-COLLECTING STEINER TREE PROBLEM WITH BUDGET CONSTRAINTS
Autor: LARISSA FIGUEIREDO TERRA DE FARIA
Colaborador(es): HELIO CORTES VIEIRA LOPES - Orientador
DAVID SOTELO PINHEIRO DA SILVA - Coorientador
Catalogação: 26/JAN/2021 Língua(s): ENGLISH - UNITED STATES
Tipo: TEXT Subtipo: THESIS
Notas: [pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
[en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio.
Referência(s): [pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=51356&idi=1
[en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=51356&idi=2
DOI: https://doi.org/10.17771/PUCRio.acad.51356
Resumo:
This thesis generalizes the multi-period variant of the classical Prizecollecting Steiner Tree Problem, which aims at finding a connected subgraph that maximizes the revenues collected from connected nodes minus the costs to utilize the connecting edges. This work additionally: (a) allows vertices to be added to the tree at different time periods; (b) imposes a predefined budget on edges selected over a specific horizon of time periods; and (c) limits the total length of edges that can be added over a time period. A branch-and-cut algorithm is provided for this problem, satisfactorily evaluating benchmark instances from the literature, adapted to a multi-period setting, up to approximately 2000 vertices and 200 terminals in reasonable time.
Descrição: Arquivo:   
COMPLETE PDF