Rice University

Events at Rice

Thesis Defense

Graduate and Postdoctoral Studies
Computational and Applied Mathematics

Speaker: Timothy Becker
Doctoral Candidate

Bilevel Clique Interdiction and Related Problems

Thursday, April 6, 2017
9:00 AM  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.

<<   June 2017   >>
S M T W T F S
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30

Search for Events


Quicklinks