Graduate and Postdoctoral Studies
Computational and Applied Mathematics
Bilevel Clique Interdiction and Related Problems
Thursday, April 6, 2017
to 11:00 AM
1049 Duncan Hall
I introduce a 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. An algorithm and formulation for the bilevel clique interdiction problem has not previously been investigated. I start by introducing a formulation and a column-generation algorithm to solve the problem of bilevel interdiction of a minimum clique transversal and move forward to the creation of a delayed row-and-column generation algorithm for bilevel clique interdiction.
Next, I introduce a formulation and algorithm to solve the bilevel interdiction of a maximum stable set problem. Bilevel interdiction of a maximum stable set is choosing a maximum stable set, but with a defender who is attempting to minimize the maximum stable set that can be chosen by the interdictor. I introduce a deterministic formulation and a delayed column generation algorithm. Additionally, I introduce a stochastic formulation of the problem. I solve this problem using a cross-decomposition method that involves L-shaped cuts into a master problem as well as new "clique" cuts for the inner problem.
Lastly, I define new classes of valid inequalities and facets for the clique transversal polytope. The valid inequalities come from two graph structures that have a closed form for their minimum vertex cover. The first class of facets are just the maximal clique constraints of the clique transversal polytope. The next class contains an odd hole with distinct cliques on each edge of the hole. Another similar class contains a clique with distinct cliques on |K| edges, where |K| is the number of nodes in the given clique. The fourth class contains a clique with distinct cliques on every edge of the initial clique, while the last class is a prism graph with distinct cliques on every edge of the prism.