A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
复制标题
DOI：
10.1287/ijoc.2021.1085
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Claudio Contardo;J. Sefair
中科院分区：
文献类型：
--
作者：
Claudio Contardo;J. Sefair
我们提出了一个渐进的近似算法的精确解的几类阻断游戏中，两个非合作的球员（即攻击者和追随者）顺序交互。跟随者必须解决一个优化问题，这个问题之前已经被攻击者领导的一系列攻击行为所扰动。这些攻击行为的目的是增加决策变量的追随者的优化问题的成本。从攻击者的角度来看，目标是选择一种攻击策略，尽可能降低追随者可获得的最优解的质量。渐进逼近机制包括一个拦截问题的迭代解，其中攻击者的行动被限制在整个解空间的一个子集和一个定价子问题，其目的是证明攻击策略的最优性。当跟随者的子问题的最优解与攻击者的决策空间仅在少量决策变量中相交时，该方案特别有用。在这种情况下，渐进近似方法可以解决阻断游戏，否则难以为经典的方法。我们说明了我们的方法的效率上的最短路径，0-1背包和设施位置的封锁游戏。贡献摘要：在这篇文章中，我们提出了一个渐进的近似算法的精确解的几类阻断游戏中，两个非合作的球员（即一个攻击者和一个追随者）顺序交互。我们利用这种阻断游戏的离散性，设计一个有效的算法框架，提高通用求解器的性能。我们的算法结合了数学规划和计算机科学的元素，包括一个元启发式算法，二分查找过程，切割平面算法和超有效不等式。虽然我们说明了我们的结果在三个具体的问题（最短路径，0-1背包，设施位置），我们的算法框架可以扩展到更广泛的一类拦截问题。
We present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. The follower must solve an optimization problem that has been previously perturbed by means of a series of attacking actions led by the attacker. These attacking actions aim at augmenting the cost of the decision variables of the follower’s optimization problem. The objective, from the attacker’s viewpoint, is that of choosing an attacking strategy that reduces as much as possible the quality of the optimal solution attainable by the follower. The progressive approximation mechanism consists of the iterative solution of an interdiction problem in which the attacker actions are restricted to a subset of the whole solution space and a pricing subproblem invoked with the objective of proving the optimality of the attacking strategy. This scheme is especially useful when the optimal solutions to the follower’s subproblem intersect with the decision space of the attacker only in a small number of decision variables. In such cases, the progressive approximation method can solve interdiction games otherwise intractable for classical methods. We illustrate the efficiency of our approach on the shortest path, 0-1 knapsack and facility location interdiction games. Summary of Contribution: In this article, we present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. We exploit the discrete nature of this interdiction game to design an effective algorithmic framework that improves the performance of general-purpose solvers. Our algorithm combines elements from mathematical programming and computer science, including a metaheuristic algorithm, a binary search procedure, a cutting-planes algorithm, and supervalid inequalities. Although we illustrate our results on three specific problems (shortest path, 0-1 knapsack, and facility location), our algorithmic framework can be extended to a broader class of interdiction problems.