Network Interdiction Goes Neural

网络截击问题是组合优化问题，涉及两个玩家：一个旨在解决网络上的优化问题，而另一个则试图修改网络以挫败第一个玩家的目标。这种问题通常出现在攻击者和防御者的背景下，涵盖军事行动、疾病传播分析和通信网络管理等领域。网络截击的主要瓶颈在于使用传统的精确求解器的高时间复杂度和设计高效启发式求解器所面临的挑战。作为一种前沿的方法，GNN已经在解决单层图上的组合优化问题方面表现出显著的有效性，例如旅行商问题、图匹配和图编辑距离。然而，网络截击提出了一个双层优化挑战，当前的GNN难以处理。为了解决这一差距，我们将网络截击问题表示为混合整数线性规划（MILP）实例，然后应用具有足够表示能力的多部分GNN来学习这些公式。这种方法确保了我们的神经网络更兼容于设计用于解决网络截击问题的数学算法，从而提高了泛化能力。通过两个不同的任务，我们证明了我们提出的方法优于理论基准模型，并提供了传统精确求解器的优势。

该论文旨在解决网络干扰问题的双层优化挑战，其中一个玩家试图在网络上解决优化问题，而另一个玩家试图修改网络以阻止第一个玩家的目标。

该论文的关键思路是将网络干扰问题表示为混合整数线性规划（MILP）实例，然后应用具有足够表示能力的多部分图GNN来学习这些公式。这种方法确保了我们的神经网络更兼容设计用于解决网络干扰问题的数学算法，从而提高了泛化能力。

该论文通过两个不同的任务展示了所提出的方法优于理论基线模型，并提供了传统精确求解器的优势。该论文使用开源数据集，并提供了代码。

最近的相关研究包括使用GNN解决单层CO问题，以及使用传统方法解决网络干扰问题的研究。