Max Collins

Thesis Advisor: Dr. Susan Martonosi (Harvey Mudd College - Department of Mathematics)

Second Reader: Dr. Alice Paul (Brown University - Department of Biostatistics)

Contact: mcollins@hmc.edu

Speeding up Benders Decomposition for the All-Pairs Vitality Maximization Problem through Super-valid and Valid Inequalities

(Abstract) The All-Pairs Vitality Maximization Problem (VIMAX) is a novel network interdiction problem with applications in disruption of criminal networks and robust network design. Prior research has demonstrated that VIMAX can be formulated as a mixed-integer program, but solving this program is often impossible due to constraints on computation time. In this thesis, we develop super-valid and valid inequalities for solving VIMAX through Benders Decomposition. By leveraging structural properties  of VIMAX, we develop an accelerated Benders Decomposition that is capable of solving VIMAX.