Weapon target assignment problem: Difference between revisions

Revision as of 03:27, 30 July 2015

Latest revision as of 00:07, 30 April 2024

(18 intermediate revisions by 12 users not shown)

Line 1:

{{More citations needed|date=April 2024}}

The '''weapon target assignment problem''' ('''WTA)''') is a class of [[combinatorial optimization]] problems present in the fields of [[Optimization (mathematics)|optimization]] and [[operations research]]. It consists of finding an optimal assignment of a set of [[weapon]]s of various types to a set of targets in order to maximize the total expected damage done to the opponent.

The basic problem is as follows:

Line 28 ⟶ 29:

== Algorithms and generalizations ==

It has long been known that assignment problems are [[NP-hard]]{{citation needed|date=September 2013}}. Nonetheless, anAn exact solution can be found using [[branch and bound]] techniques which utilize [[relaxation (approximation)]].<ref>{{cite journal |last1=Andersen |first1=A.C. |last2=Pavlikov |first2=K. |last3=Toffolo |first3=T.A.M. |year=2022 |title=Weapon-Target Assignment Problem: Exact and Approximate Solution Algorithms |journal=Annals of Operations Research |volume=312 |issue=2 |pages=581–606 |doi=10.1007/s10479-022-04525-6|url=https://findresearcher.sdu.dk/ws/files/204132463/WTA.pdf }}</ref> Many [[heuristic algorithm]]s have been proposed which provide near-optimal solutions in [[polynomial time]].<ref>{{cite journal |last1=Ahuja, R|first1=Ravindra K. et|last2=Kumar |first2=Arvind |last3=Jha |first3=Krishna alC. |last4=Orlin |first4=James B. |year=2007 |title=Exact and Heuristic Algorithms for the Weapon-Target Assignment Problem. |journal=Operations Research |volume=55( |issue=6), pp. |pages=1136–1146, 2007|doi=10.1287/opre.1070.0440}}</ref>

==Example==

Line 36 ⟶ 37:

! Weapon Type !! <math> V_{1} = 5 </math> !! <math> V_{2} = 10 </math> !! <math> V_{3} = 20 </math>

|-

| Tank || 0.3 || 0.2 || 0.055

|-

| Aircraft || 0.1 || 0.6 || 0.5

Line 42 ⟶ 43:

| Sea Vessel || 0.4 || 0.5 || 0.4

|}

One feasible solution is to assign the sea vessel and one aircraft to the highest valued target (3). This results in an expected survival value of <math> 20(0.6)(0.5)= 6 </math>. One could then assign the remaining aircraft and 2 tanks to target #2, resulting in expected survival value of <math> 10 (0.4)(0.8)^2 = 2.56 </math>. Finally, the remaining 3 tanks are assigned to target #1 which has an expected survival value of <math> 5 (0.7)^3 = 1.715 </math>. Thus, we have a total expected survival value of <math> 6 + 2.56 + 1.715 = 10.275 </math>. Note that a better solution can be achieved by assigning 3 tanks to target #1, 2 tanks and sea vessel to target #2 and 2 aircraft to target #3, giving an expected survival value of <math> 5(0.7)^3 +10(0.5)(0.8)^2 + 20(0.5)^2 = 9.915 </math>.

==See also==

Line 67 ⟶ 68:

[[Category:Combinatorial optimization]]

[[Category:Matching (graph theory)]]

[[Category:Combat modeling]]