A new exact algorithm for the Weapon-Target Assignment problem

Yiping Lu and Danny Z. Chen

Omega, 2021, vol. 98, issue C

Abstract: 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.

Keywords: Weapon-Target Assignment; Integer linear programming; Column enumeration; Assignment of Assets to Tasks (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S030504831930711X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:98:y:2021:i:c:s030504831930711x

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2019.102138

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().