On supervalid inequalities for binary interdiction games

• 成果类型: Article
• 署名作者: Wei, Ningji; Walteros, Jose L.
• 署名单位: Texas Tech University System; Texas Tech University; State University of New York (SUNY) System; University at Buffalo, SUNY
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02111-1
• 发表日期: 2025
• 页码: 437-478
• 关键词: detecting critical nodes; network interdiction; independent set; algorithm; Knapsack; branch

摘要

Supervalid inequalities are a specific type of constraints often used within the branch-and-cut framework to strengthen the linear relaxation of mixed-integer programs. These inequalities share the particular characteristic of potentially removing feasible integer solutions as long as they are already dominated by an incumbent solution. This paper focuses on supervalid inequalities for solving binary interdiction games. Specifically, we provide a general characterization of inequalities that are derived from bipartitions of the leader's strategy set and develop an algorithmic approach to use them. This includes the design of two verification subroutines that we apply for separation purposes. We provide three general examples in which we apply our results to solve binary interdiction games targeting shortest paths, spanning trees, and vertex covers. Finally, we prove that the separation procedure is efficient for the class of interdiction games defined on greedoids-a type of set system that generalizes many others such as matroids and antimatroids.