Solving Large‐Scale Weapon Target Assignment Problems in Seconds Using Branch‐Price‐And‐Cut

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.