Detalhes bibliográficos
| Ano de defesa: |
2023 |
| Autor(a) principal: |
Castelo, Emanuel Elias Silva |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
eng |
| Instituição de defesa: |
Não Informado pela instituição
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
http://www.repositorio.ufc.br/handle/riufc/73496
|
Resumo: |
Given a digraph D = (V,A), where all arcs (i, j) ∈ A have an associated cost d(i, j) ∈ R+ and a color c(i, j), a positive integer k, a source s, and a destination t, the k-Color Shortest Path Problem is an NP-Hard problem that consists in finding the shortest (s,t)-path in D while using at most k distinct colors. We propose valid inequalities for the problem that proved to strengthen the linear relaxation of an existing Integer Linear Programming formulation. An exponential set of valid inequalities defines a new formulation for the problem and is solved by using a branch-and-cut algorithm. We introduce more challenging instances of the problem and present numerical experiments for both benchmark and the new instances. Finally, we evaluate the individual and the collective use of the valid inequalities. Computational results for the proposed ideas and for existing solution approaches for the problem showed the effectiveness of the new inequalities in handling the new instances both in terms of execution times and improving their linear relaxed solutions. |
