An Exact Algorithm for the Dynamic Two-Stage Weapon-Target Assignment Problem

The Weapon-Target Assignment (WTA) problem seeks to compute an optimal assignment of m weapons to n targets such that the expected total survival possibility of the targets is minimized (or equivalently, the expected total damage of the targets is maximized). The WTA problem is known to be NP-complete and was commonly formulated as nonlinear models. Recently, a column enumeration (CE) algorithm which formulates the WTA as a linear model without sacrificing the optimality was developed, and the scalability of this CE algorithm well exceeded the previous WTA solutions. Beyond the classic WTA in which the information of the weapons and the targets is known before the assignment, the so-called dynamic WTA (DWTA) assumes to know only partially the information of the future-incoming targets at the time of decision. The DWTA is more difficult to solve, and its solutions often have to be subjected to either solution approximation or problem simplification. In this paper, by extending the CE algorithm, we show that an exact algorithm with good scalability can be developed for an important special version of the DWTA, the two-stage WTA, by formulating it with stochastic programming. Computational experiments show that our proposed two-stage WTA algorithm is efficient, and the manageable scale of the algorithm is sufficiently good for practical usages after slightly sacrificing a very small solution accuracy for extremely hard cases