Solving Large‐Scale Weapon Target Assignment Problems in Seconds Using Branch‐Price‐And‐Cut
提出基于分支定价切割的框架，将武器目标分配问题转化为列生成形式，在笔记本电脑上数秒内精确求解含10000个目标和武器的实例，而此前需数小时。
ABSTRACT This paper proposes a framework based on branch‐price‐and‐cut to solve the weapon target assignment (WTA) problem, a popular class of non‐linear assignment problems that has received significant attention over the past several decades. We first reformulate the WTA into a form amenable to column generation and then derive efficient algorithms for initializing the column generation, solving the pricing problem, generating clique cuts, and managing the branch‐and‐bound. Through significant experimentation, we display the framework's efficiency – which scales to solve problems with 10000 targets and weapons on a laptop and exactly solves problems in seconds, which previously took hours to solve. We also discuss extensions to common WTA variants and more general non‐linear assignment problems in hopes of motivating algorithmic developments.