Treffer: 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. [ABSTRACT FROM AUTHOR]

Copyright of Naval Research Logistics is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)