ABSTRACT

The weapon-target assignment (WTA) problem arises in the modeling of combat operations where we wish to maximize the total expected damage caused to the enemy’s target using limited number of weapons. In the WTA problem, there are n targets, numbered 1, 2, …, n, and m weapon types, numbered 1, 2, …, m. Let Vj denote the value of the target j, and Wi denote the number of weapons of type i available to be assigned to targets. Let pij denote the probability of destroying target j by a single weapon of type i. Hence qij1 pij denotes the probability of survival of target j if a single weapon of type i is assigned to it. Observe that if we assign xij number of weapons of type i to target j, then the survival probability of target j is given by qij xij . A target may be assigned weapons of different types. The WTA problem is to determine the number of weapons xij of type i to be assigned to target j to minimize the total expected survival value of all targets. This problem can be formulated as the following nonlinear integer programming problem:

Minimize V qj j

£ £¤¦¥

³

subject to

, for all i1, 2, …, m, (7.1b)

xij≥0 and integer, for all i1, 2, …, m, and for all j1, 2, …, n. (7.1c)

In the above formulation, we minimize the expected survival value of the targets while ensuring that the total number of weapons used is no more than those available. This formulation presents a simplified version of the WTA problem. In more practical versions, we may consider adding additional constraints, such as (i) lower and/or upper bounds on the number of weapons of type i assigned to a target j; (ii) lower and/or upper bounds on the total number of weapons assigned to target j; or (iii) a lower bound on the survival value of the target j. The algorithms proposed in this chapter can be easily modified to handle these additional constraints.