Integer programming methods for solving binary interdiction games

Ningji Wei and Jose L. Walteros

European Journal of Operational Research, 2022, vol. 302, issue 2, 456-469

Abstract: This paper studies a general class of interdiction problems in which the solution space of both the leader and follower are characterized by two discrete sets denoted the leader’s strategy set and the follower’s structure set. In this setting, the interaction between any strategy-structure pair is assumed to be binary, in the sense that the strategy selected by the leader either interacts or not with the follower’s choice of structure and, if it does, then the structure becomes unavailable for the follower. There are many interdiction games defined by this setup, including problems where the leader wishes to attack some type of network structures, such as shortest paths, minimum spanning trees, and minimum dominating sets, among others. We study a general set-covering type of formulation that can be used for solving this class of problems and analyze several properties of the convex hull of its solutions. We develop a wide class of valid inequalities that generalizes and extends several others that have appeared in the literature in recent years. We provide conditions for them to be facet-defining and conclude with a general discussion about their separation. Several examples of problems in the context of network interdiction are presented to help with the exposition.

Keywords: Integer programming; Interdiction; Network optimization; Polyhedral analysis; Attacker-Defender (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722000091
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:302:y:2022:i:2:p:456-469

DOI: 10.1016/j.ejor.2022.01.009

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().