Show simple item record

dc.contributor.authorBecker, Timothy Joseph
dc.date.accessioned 2018-06-19T17:51:22Z
dc.date.available 2018-06-19T17:51:22Z
dc.date.issued 2017-05
dc.identifier.citation Becker, Timothy Joseph. "Bilevel Clique Interdiction and Related Problems." (2017) https://hdl.handle.net/1911/102251.
dc.identifier.urihttps://hdl.handle.net/1911/102251
dc.descriptionThis work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/96109
dc.description.abstract 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 who have a closed form for their vertex cover number, which we use as a specic case for nding a minimum clique transversal. 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 an odd clique with distinct maximal cliques on the edges of one of its spanning cycles. The fourth class contains a clique with distinct maximal cliques on every edge of the initial clique, while the last class is a prism graph with distinct maximal cliques on every edge of the prism.
dc.format.extent 146 pp
dc.title Bilevel Clique Interdiction and Related Problems
dc.type Technical report
dc.date.note May 2017
dc.identifier.digital TR17-05
dc.type.dcmi Text


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record