本文由Alexandre Colaers Andersen、Konstantin Pavlikov和Túlio A. M. Toffolo共同撰写，发表于2022年1月13日的《Annals of Operations Research》期刊上。研究的主要领域是运筹学中的武器-目标分配问题（Weapon-Target Assignment, WTA）。WTA问题旨在将一组武器分配给多个目标，以最小化目标存活的期望值。该问题是一个非线性的组合优化问题，属于NP难问题。本文的主要贡献在于提出了一种新的精确算法，称为“分支调整”（Branch-and-Adjust），用于解决WTA问题。

研究背景

WTA问题最早可以追溯到20世纪50年代末，经过多年的研究，已经发展出多种解决方法和模型。WTA问题属于非线性分配问题家族，与设施选址问题、媒体分配问题和放射治疗问题等有相似之处。WTA问题的复杂性在于其非线性目标函数和组合性质，尤其是在大规模问题实例中，传统的精确算法往往难以在合理时间内找到最优解。

研究方法

本文首先回顾了几种现有的线性化方法，包括通过凸分段线性函数近似非线性项的启发式方法，以及通过引入大量额外变量和约束来精确线性化的方法。基于这些方法的计算实验结果，作者提出了一种新的精确算法——分支调整算法。该算法基于WTA目标函数的紧凑分段线性凸下近似，能够在分支定界框架内精确求解WTA问题。该算法可以在现有的分支切割或分支定界算法基础上实现，并利用最先进的混合整数线性规划求解器工具。

研究流程

1. 问题描述：WTA问题被形式化为一个非线性整数规划问题，目标是最小化目标存活的期望值。约束条件包括每种武器的最大使用数量和决策变量的非负整数限制。
2. 线性化方法：本文介绍了两种线性化方法。第一种是通过凸分段线性函数近似非线性项，第二种是通过概率链（Probability Chains）精确线性化目标函数。
3. 分支调整算法：该算法利用分段线性下近似函数来求解WTA问题，并在分支定界过程中通过调整目标函数的值来确保解的精确性。算法能够在两小时内处理多达1500种武器和1000个目标的大规模问题实例，并获得最优性差距不超过2.0%的解。

主要结果

通过数值实验，本文展示了所提出算法的有效性。实验结果表明，分支调整算法能够在较短的时间内处理大规模问题实例，并获得高质量的解。与现有的精确线性化方法相比，该算法在计算时间和解的质量上都有显著提升。

结论与意义

本文提出的分支调整算法为WTA问题提供了一种高效的精确求解方法，尤其适用于大规模问题实例。该算法的科学价值在于其创新性地结合了分段线性近似和分支定界框架，能够在保证解的精度的同时显著减少计算时间。此外，该算法具有广泛的应用价值，不仅可以用于军事防御领域，还可以应用于其他类似的非线性组合优化问题。

研究亮点

1. 创新性算法：分支调整算法是本文的核心贡献，其创新之处在于通过分段线性下近似函数来引导分支定界过程，从而在不引入大量额外变量和约束的情况下精确求解WTA问题。
2. 高效性：该算法能够在两小时内处理多达1500种武器和1000个目标的大规模问题实例，并获得最优性差距不超过2.0%的解。
3. 广泛应用：该算法不仅适用于WTA问题，还可以推广到其他非线性组合优化问题，具有广泛的应用前景。

其他有价值的内容

本文还详细讨论了WTA问题的不同变体，包括防御性和进攻性WTA问题，以及静态和动态WTA问题。这些讨论为读者提供了对WTA问题更全面的理解，并为未来的研究提供了方向。

总之，本文通过提出一种新的精确算法，显著提升了WTA问题的求解效率，为该领域的研究和应用提供了重要的理论和方法支持。