Weapon target assignment problem

The weapon target assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. It consists of finding an optimal assignment of a group of weapons of potentially various types to a set of targets.

In its most general form, the problem is as follows:

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task. As opposed to the classic assignment problem or the generalized assignment problem, more than one agent can be assigned to each task and not all tasks need agent assigned.

Algorithms and generalizations

The weapon target assignment problem is a special case of the transportation problem, which is a special case of the minimum cost flow problem, which in turn is a special case of a linear program. While it is possible to solve any of these problems using the simplex algorithm, each specialization has more efficient algorithms designed to take advantage of its special structure. If the cost function involves quadratic inequalities it is called the quadratic assignment problem.

Formal mathematical definition

The formal definition of the weapon target assignment problem is

Given two sets, A and T, of equal size, together with a weight function C : A × T → R. Find a bijection f : A → T such that the cost function:

$\sum _{a\in A}C(a,f(a))$

is minimized.

Usually the weight function is viewed as a square real-valued matrix C, so that the cost function is written down as:

$\sum _{a\in A}C_{a,f(a)}$

The problem is "linear" because the cost function to be optimized as well as all the constraints contain only linear terms.

The problem can be expressed as a standard linear program with the objective function

$\sum _{i\in A}\sum _{j\in T}C(i,j)x_{ij}$

subject to the constraints

$\sum _{j\in T}x_{ij}=1{\text{ for }}i\in A,\,$

$\sum _{i\in A}x_{ij}=1{\text{ for }}j\in T,\,$

$x_{ij}\geq 0{\text{ for }}i,j\in A,T.\,$

The variable $x_{ij}$ represents the assignment of agent $i$ to task $j$, taking value 1 if the assignment is done and 0 otherwise. This formulation allows also fractional variable values, but there is always an optimal solution where the variables take integer values. This is because the constraint matrix is totally unimodular. The first constraint requires that every agent is assigned to exactly one task, and the second constraint requires that every task is assigned exactly one agent.

See also

• Stable marriage problem
• Auction algorithm
• Generalized assignment problem
• Linear bottleneck assignment problem
• Quadratic assignment problem

Further reading

• Burkard, Rainer (2009). Assignment Problems. SIAM. ISBN 978-0-898716-63-4. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

External links

• example.com