Exact and Heuristic Algorithms for the Weapon-Target Assignment Problem

The weapon-target assignment (WTA) problem is a fundamental problem arising in defense-related applications of operations research. This problem consists of optimally assigning n weapons to m targets so that the total expected survival value of the targets after all the engagements is minimal. The W...

Full description

Saved in:
Bibliographic Details
Published in:Operations research 2007-11, Vol.55 (6), p.1136-1146
Main Authors: Ahuja, Ravindra K, Kumar, Arvind, Jha, Krishna C, Orlin, James B
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Cost allocation
Cost functions
Decision theory. Utility theory
Exact sciences and technology
Flows in networks. Combinatorial problems
Heuristic
Heuristic programming
Heuristics
Integer programming
Integers
Laws, regulations and rules
military
Military weapons
Minimization of cost
Network flow problem
networks
nonlinear
Objective functions
Operational research and scientific management
Operational research. Management science
Optimal solutions
Optimization algorithms
programming
Studies
targeting
Weapons
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The weapon-target assignment (WTA) problem is a fundamental problem arising in defense-related applications of operations research. This problem consists of optimally assigning n weapons to m targets so that the total expected survival value of the targets after all the engagements is minimal. The WTA problem can be formulated as a nonlinear integer programming problem and is known to be NP-complete. No exact methods exist for the WTA problem that can solve even small-size problems (for example, with 20 weapons and 20 targets). Although several heuristic methods have been proposed to solve the WTA problem, due to the absence of exact methods, no estimates are available on the quality of solutions produced by such heuristics. In this paper, we suggest integer programming and network flow-based lower-bounding methods that we obtain using a branch-and-bound algorithm for the WTA problem. We also propose a network flow-based construction heuristic and a very large-scale neighborhood (VLSN) search algorithm. We present computational results of our algorithms, which indicate that we can solve moderately large instances (up to 80 weapons and 80 targets) of the WTA problem optimally and obtain almost optimal solutions of fairly large instances (up to 200 weapons and 200 targets) within a few seconds.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.1070.0440