A Branch-and-Cut Method for Solving the Bilevel Clique Interdiction Problem
Becker, Timothy J
Master of Arts
I introduce an algorithm to solve the current formulation of the bilevel clique interdiction problem. Interdiction, a military term, describes the removal of enemy resources. The single level clique interdiction problem describes the attempt of an attacker to interdict a maximum number of cliques. The bilevel form of the problem introduces a defender who attempts to minimize the number of cliques interdicted by the attacker. Previous authors have developed algorithms for the single level clique interdiction problem, as well as for bilevel formulations of other problems. However, an algorithm for the bilevel clique interdiction problem has not previously been creatd. The algorithm presented in this thesis uses a branch and cut approach to solve the proposed problem. This algorithm is expected to be usable on any social network, thereby improving the study of many network problems including terrorist cells or marketing strategies.
Clique; Interdiction; Branch-and-Cut; Graph Theory; Integer Programming