Embedded Files
Thesis Advisor: Dr. Susan E. Martonosi (Harvey Mudd College - Department of Mathematics)
Second Reader: Dr. Alice Paul (Brown University - Department of Biostatistics)
Contact: elrogers@g.hmc.edu
Increasing computational efficiently of solving the All-Pairs Vitality Maximization Problem
Increasing computational efficiently of solving the All-Pairs Vitality Maximization Problem
The all-pairs vitality maximization problem (VIMAX) is an NP-Hard network interdiction problem which seeks to maximize flow through a critical node in a network. Previous literature formulated VIMAX as a mixed-integer linear program, and found a general application of Benders Decomposition to have some success when solving the program on small networks. Recent work found that by adding a heuristic to generate initial Benders cuts, and making more efficient cuts using Pareto-optimality, VIMAX could be solved on larger graphs of order 40. This thesis continues to apply accelerations of Benders Decomposition informed by the structure properties of VIMAX.
Report abuse