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.
|
|||||||||||||
|