《武器目标分配问题：精确和近似解法算法》

武器-目标分配（WTA）问题旨在将一组武器分配给若干资产（目标），从而使幸存目标的期望值最小。WTA 问题是一个非线性组合优化问题，已知具有 NP 难度。本文应用了几种现有技术来线性化 WTA 问题。其中一种线性化技术（Camm 等人，2002 年）通过凸片断线性函数逼近 WTA 问题的非线性项，并为 WTA 问题提供启发式解决方案。不过，从计算角度来看，这种近似问题相对容易解决，即使对于大规模问题实例也是如此。O'Hanley 等人（2013 年）提出的另一种方法将 WTA 问题精确线性化，但代价是要加入大量额外的变量和约束条件，这使得许多大规模问题实例变得难以解决。受这些现有求解方法计算实验结果的启发，我们开发了一种专门的新精确求解方法，即分支-调整法。所提出的求解方法涉及 WTA 目标函数的紧凑片线性凸下逼近，并能精确求解 WTA 问题。该算法建立在任何现有的分支-切割或分支-约束算法之上，可以使用最先进的混合整数线性规划求解器提供的工具来实现。数值实验证明，所提出的专门算法能够处理多达 1,500 件武器和 1,000 个目标的超大规模问题实例，并能在两个小时的计算运行时间内获得最优性差距高达 2.0% 的解决方案。

武器与资产（目标）的最佳位置问题被称为 "武器-目标分配（WTA）"问题，是一个与国防作战研究特别相关的问题。该问题属于非线性分配问题的一个大家族，由其他各种问题组成，如设施定位问题（Camm 等人，2002 年；O'Hanley 等人，2013 年）、媒体分配问题（Cetin 和 Esen，2006 年）和辐射处理问题（Esen 等人，2008 年）。这意味着，在一个应用领域中开发和使用的现有解决方法可应用于该系列中的其他问题。

1.1. 文献回顾

WTA 问题可追溯到 20 世纪 50 年代末，此后一直被广泛研究。在 Merrill Flood 于 1957 年 3 月 13-15 日在普林斯顿大学线性规划会议上对该问题进行非正式描述后，Manne（1958 年）正式提出了该问题。曼恩在论文中指出，在所有可用武器都相同的假设条件下，可以设计出该问题的线性规划方案。不久之后，小登布罗德等人（1959 年）开发了一种算法，通过将武器依次分配给生存概率边际递减最大的目标，对曼恩提出的问题进行了最优分配。这种算法被称为最大边际收益算法。戴伊（1966 年）对问题的维度和复杂性进行了进一步研究，通过将分配问题分解为较小的目标选择问题，为解决较大的目标选择问题提供了信息，从而大大降低了问题的维度。

到 20 世纪 60 年代末，Matlin（1970 年）对这一问题及其变体的文献进行了全面回顾，对各种模型假设的复杂性进行了分类。作为补充，Eckler 和 Burr（1972 年）以及 Murphey（2000 年）进一步详细介绍了其变体，并描述了 WTA 的进攻和防御形式，以及如何将所有武器的单一分配（称为静态 WTA）扩展到动态 WTA，即在几个离散的时间点进行分配。Chang 等人（1987 年）提出了一种算法，用于获得大规模武器目标分配问题的近似最优解。假设每个目标最多只能分配到一种武器，那么就可以得到整个问题的近最优分配。Wacholder （1989 年）对基于神经网络的静态 WTA 算法进行了模拟，结果证明，该算法的收敛结果非常接近全局最优解。

Metler 等人（1990 年）提出了一套求解算法，使用启发式算法将问题分解为两个阶段的子问题分别求解。随后，Ahuja 等人（2007 年）提出了几种下界方案作为构造启发式算法，并通过大规模邻域搜索加以改进。针对 WTA 问题还提出了其他各种启发式求解算法，参见 Sonuc 等人（2017 年）及其中的参考文献。最近，Lu 和 Chen（2021）提出了一种基于列生成思想的 WTA 问题精确解算法。关于武器目标分配模型和求解算法的全面综述可参见 Kline 等人（2019）。

1.2. 问题描述

文献中对 WTA 问题有多种表述，每种表述都有细微的修改和不同的假设。Matlin （1970 年）对各种 WTA 问题进行了全面评述，他在评述中表达了简化完整模型的必要性。他还解释了假设如何决定模型之间的差异。他将问题分为四个子模型：武器系统、目标综合体、交战和损伤模型。在每个子模型中，都有不同的假设。

武器系统子模型描述了可用的武器类型是单一还是多种。它还定义了是否所有武器都能到达每个目标，以及武器的伤害是确定性的还是概率性的。目标综合体以目标类型为特征。类型取决于单一武器能否攻击目标，以及目标的值或权重。例如，目标可能具有相等或不相等的值，也可能按优先级排序。伤害子模型决定伤害是部分伤害还是整体伤害（确定性伤害还是概率性伤害）。当目标值可能部分累积时，就会出现部分损害。当可以观察到目标在攻击后要么存活要么被摧毁的状态时，就会使用全面损坏假设。交战子模型定义了武器摧毁目标的概率。该概率取决于武器和目标，以及防御系统，即可能拦截指定武器攻击的系统。

WTA 问题可以在防御或进攻环境下提出。对于防御性问题的表述，可以考虑资产受到攻击的情况。需要用防御武器拦截进攻性武器，从而保护资产。在这种情况下，目标可能是通过将防御武器分配给攻击资产的导弹，最大限度地降低资产的预期损失。这里假设每种防御武器都有特定的可靠性，即成功拦截攻击武器的概率。同样，未被拦截的武器也可能以某种其他概率摧毁资产。显然，在这个问题的最简单例子中，防御者可以先观察哪些资产受到攻击，并找出相应资产的生存概率，然后再将防御武器分配给进攻武器。这样，防御者就能更有把握地保存最有价值的资产。这个问题的变种包括不知道哪些资产正在受到攻击或不知道未拦截武器将造成的预期破坏的情况。

对于进攻型问题，可以考虑将一系列不同类型的可用武器发射到某些目标上。假定提供了每个目标的数值以及用每种类型的单一武器摧毁每个目标的概率。然后，我们的目标是确定将哪些武器分配给哪些目标，从而在不超出可用武器数量的情况下，使预期造成的破坏最大化。这就是本文所要解决的问题。该问题的一个变种可能包括关于统一武器的假设，即假设所有可用武器都是相同的。正如小 denBroeder 等人（1959 年）所证明的那样，这一假设简化了求解过程。另一种更现实的模型可能会为每种武器引入适当的射程，这样并非所有武器都能击中所有目标。

在上述防御和进攻问题的表述中，隐含的意思是它们是静态的。考虑到概率，如果首先观测到资产或目标的价值，然后再分配武器以优化目标，那么问题就是静态的。因此，只需解决单一时间段内的单一分配问题。但在动态 WTA 问题中，分配是在多个时间段内进行的（Murphey，2000 年）。这种问题的一个例子是 "射击-观察-射击 "战略，在分配了全部可用武器的一个子集后，可以在分配剩余武器之前观察其影响。这样，攻击者就可以观察目标是否在第一次攻击中幸存下来，并为幸存的优先目标分配新的武器，同时对任何不准确的射击进行调整。

1.3. 本文的贡献

本文在以下方面对文献有所贡献。鉴于 WTA 问题是一个非线性整数优化问题，本文简要介绍了如何应用现有的几种方法将该问题线性化，并比较了它们的优缺点。最重要的是，本文进一步开发了一种专门的精确算法，仅使用非线性目标函数的紧凑凸下逼近来解决 WTA 问题。该算法的主要创新思想是使用 WTA 目标函数的紧凑片面线性下近似值来寻找下界和引导分支，同时在分支-约束框架中求助于非线性 WTA 目标的精确值来进行约束。因此，只需在现任节点上对目标函数进行简单的手动调整，就能在任何分支与边界算法的基础上构建该算法。因此，该算法更准确的名称应该是 "分支-调整-约束"，为简洁起见，我们将其简化为 "分支-调整"。所提出的求解方法可以使用最先进的混合整数线性优化软件来实现，并能处理非常大规模的 WTA 问题实例。当它不能在规定的时间内将问题实例求解到最优时，它提供了一个非常合理的最优保证，即在获得的最佳解上有一个很小的最优差距。据报道，Lu 和 Chen（2021 年）的求解方法可处理多达 400 种武器和 400 个目标的问题实例，与之相比，我们实验中提出的算法可在几分钟的计算机时间内将多达 400 种武器和 800 个目标的实例求解到最优，并在两小时的计算机时间内将更大的实例求解到差距很小的次最优。此外，所提出的求解方法具有通用性，可成功应用于 WTA 以外的其他应用领域。

本文的组织结构如下。第 2 节将 WTA 定义为非线性优化问题，第 3 节和第 4 节介绍了该问题的两种线性化方法，第 5 节提出了一种混合线性化方法，该方法融合了现有的两种线性化方法。最后，第 6 节介绍了一种解决 WTA 问题的新精确算法，第 7 节展示了解决 WTA 问题实例的所有计算实验结果。第 8 节为结论。