TY - JOUR
T1 - Exact algorithms for the minimum cost vertex blocker clique problem
AU - Nasirian, Farzaneh
AU - Mahdavi Pajouh, Foad
AU - Namayanja, Josephine
N1 - Publisher Copyright:
© 2018 Elsevier Ltd
PY - 2019/3
Y1 - 2019/3
N2 - We study the minimum cost vertex blocker clique problem (CVCP), which is defined as follows. Given a simple undirected graph with weights and costs on its vertices and r > 0, detect a minimum cost subset of vertices to be removed such that the weight of any clique in the remaining graph is at most r. We propose a new characterization of the set of feasible solutions that results in new linear 0–1 programming formulations solved by lazy-fashioned branch-and-cut algorithms. A new set of facet-inducing inequalities for the convex hull of feasible solutions to CVCP are also identified. We also propose new combinatorial bounding schemes and employ them to develop the first combinatorial branch-and-bound algorithm for this problem. The computational performance of these exact algorithms is studied on a test-bed of randomly generated graphs, and real-life instances.
AB - We study the minimum cost vertex blocker clique problem (CVCP), which is defined as follows. Given a simple undirected graph with weights and costs on its vertices and r > 0, detect a minimum cost subset of vertices to be removed such that the weight of any clique in the remaining graph is at most r. We propose a new characterization of the set of feasible solutions that results in new linear 0–1 programming formulations solved by lazy-fashioned branch-and-cut algorithms. A new set of facet-inducing inequalities for the convex hull of feasible solutions to CVCP are also identified. We also propose new combinatorial bounding schemes and employ them to develop the first combinatorial branch-and-bound algorithm for this problem. The computational performance of these exact algorithms is studied on a test-bed of randomly generated graphs, and real-life instances.
KW - Combinatorial branch-and-bound
KW - Interdiction
KW - Lazy-fashioned branch-and-cut
KW - Minimum cost vertex blocker clique problem
UR - http://www.scopus.com/inward/record.url?scp=85057593730&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85057593730&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2018.11.016
DO - 10.1016/j.cor.2018.11.016
M3 - Article
AN - SCOPUS:85057593730
SN - 0305-0548
VL - 103
SP - 296
EP - 309
JO - Computers and Operations Research
JF - Computers and Operations Research
ER -