Show simple item record

dc.contributor.advisor Hicks, Illya V
dc.creatorBecker, Timothy
dc.date.accessioned 2017-08-01T18:37:58Z
dc.date.available 2017-08-01T18:37:58Z
dc.date.created 2017-05
dc.date.issued 2017-04-18
dc.date.submitted May 2017
dc.identifier.citation Becker, Timothy. "Bilevel Clique Interdiction and Related Problems." (2017) Diss., Rice University. https://hdl.handle.net/1911/96109.
dc.identifier.urihttps://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 specific case for finding 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.mimetype application/pdf
dc.language.iso eng
dc.subjectGraph Theory
Integer Programming
Bilevel Programming
Interdiction
Column Generation
Facets
Valid Inequalities
dc.title Bilevel Clique Interdiction and Related Problems
dc.date.updated 2017-08-01T18:37:58Z
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Computational and Applied Mathematics
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record