A branch-and-cut algorithm for the Edge Interdiction Clique Problem

Furini, Fabio; Ljubic, Ivana; San Segundo, Pablo; Zhao, Yanlu

doi:10.1016/j.ejor.2021.01.030

A branch-and-cut algorithm for the Edge Interdiction Clique Problem

Furini, Fabio; Ljubic, Ivana; San Segundo, Pablo; Zhao, Yanlu

Authors

Fabio Furini

Ivana Ljubic

Pablo San Segundo

Yanlu Zhao yanlu.zhao@durham.ac.uk
Assistant Professor

Abstract

Given a graph G and an interdiction budget k∈N, the Edge Interdiction Clique Problem (EICP) asks to find a subset of at most k edges to remove from G so that the size of the maximum clique, in the interdicted graph, is minimized. The EICP belongs to the family of interdiction problems with the aim of reducing the clique number of the graph. The EICP optimal solutions, called optimal interdiction policies, determine the subset of most vital edges of a graph which are crucial for preserving its clique number. We propose a new set-covering-based Integer Linear Programming (ILP) formulation for the EICP with an exponential number of constraints, called the clique-covering inequalities. We design a new branch-and-cut algorithm which is enhanced by a tailored separation procedure and by an effective heuristic initialization phase. Thanks to the new exact algorithm, we manage to solve the EICP in several sets of instances from the literature. Extensive tests show that the new exact algorithm greatly outperforms the state-of-the-art approaches for the EICP.

Citation

Furini, F., Ljubic, I., San Segundo, P., & Zhao, Y. (2021). A branch-and-cut algorithm for the Edge Interdiction Clique Problem. European Journal of Operational Research, 294(1), 54-69. https://doi.org/10.1016/j.ejor.2021.01.030

Journal Article Type	Article
Acceptance Date	Jan 18, 2021
Online Publication Date	Jan 21, 2021
Publication Date	Oct 1, 2021
Deposit Date	Jan 19, 2021
Publicly Available Date	Jan 21, 2023
Journal	European Journal of Operational Research
Print ISSN	0377-2217
Publisher	Elsevier
Peer Reviewed	Peer Reviewed
Volume	294
Issue	1
Pages	54-69
DOI	https://doi.org/10.1016/j.ejor.2021.01.030
Keywords	Integer programming, team orienteering problem, diversity, branch-cut-and-price, digital travel industry
Public URL	https://durham-repository.worktribe.com/output/1253336

Files

Accepted Journal Article (448 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/

Copyright Statement
© 2021 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/