A new exact algorithm for the Weapon-Target Assignment problem

摘要

The Weapon-Target Assignment (WTA) problem is of military importance; it computes an optimal assignment of m weapons to n targets such that the expected total damage of the targets is maximized (or equivalently, the expected total survival possibility of the targets is minimized). The WTA problem is known to be NP-complete and was commonly formulated as nonlinear models. In previous studies, the largest WTA problem instances that could be solved exactly were of only moderate sizes (e.g., 80 weapons and 80 targets, with a long execution time of 16.2 h). In this paper, unlike the previous methods that tackled the WTA problem as nonlinear models, we formulate the problem as a linear model, and present a new exact algorithm that is much more efficient for solving the problem. More specifically, our new exact algorithm formulates the WTA problem as an integer linear programming model which has binary columns, and solves the model using column enumeration as well as branch and bound techniques. To drastically reduce the number of columns needed to be enumerated, we propose new methods called weapon number bounding and weapon domination. Extensive computational experiments are conducted, and the results show that our new exact algorithm can solve all the instances considered by previous studies but our solutions take much shorter execution time. In particular, the execution time for exactly solving the instance of 80 weapons and 80 targets is only 0.40 s. Furthermore, we can solve exactly much larger problem instances than previous methods, and the maximum problem size that we can solve exactly is up to 400 weapons and 400 targets, with an average execution time of 4.68 s. In addition, our method can be extended to be applicable to the Assignment of Assets to Tasks (AATT) problem. (C) 2019 Elsevier Ltd. All rights reserved.