02 May 2024
14:00 Master's Defense Room 53 of IC2
Theme
Exact and Heuristic Methods for the Minimum Diameter Subgraph Problem
Student
Arthur Pratti Dadalto
Advisor / Teacher
Fábio Luiz Usberti - Co-supervisor: Mário César San Felice
Brief summary
This dissertation addresses the Minimum Subgraph Problem (MSDP), an NP-hard combinatorial optimization problem with applications in network design. Given an undirected graph with edge lengths and costs, the objective of MSDP is to find a generating subgraph with total cost limited by a specified budget, such that the diameter of the subgraph is minimal. Exact methodologies and heuristics for MSDP are proposed, and an instance benchmark is designed to evaluate the methodologies in an extensive computational study. In the exact approach, a Mixed Integer Linear Programming (MILP) formulation for the MSDP is proposed, with two families of valid inequalities generalizing coverage and cutoff inequalities, which form the basis of the first exact approaches for the MSDP. These are complemented by an approach to apply “lazy constraints” in MILP and a heuristic to generate upper bounds from fractional solutions. The benchmark results show the effectiveness of each contribution in reducing optimality gaps and computation times. In the heuristic approach, a metaheuristic approach for MSDP is presented using a Biased Random Key Genetic Algorithm (BRKGA), with three decoders, cache of diameter computations and starting solutions. The benchmark results show that the proposed methods contribute to reducing the known optimality gaps and are better than the exact methods for large instances in terms of the quality of the solutions obtained.
Examination Board
Headlines:
| Fábio Luiz Usberti | IC / UNICAMP |
| Pedro Augusto Munari Junior | CCET/UFSCar |
| Maycon Sambinelli | CMCC / UFABC |
Substitutes:
| Lehilton Lelis Chaves Pedrosa | IC / UNICAMP |
| Petra Maria Bartmeyer | FEEC / UNICAMP |