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

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.