the weapon target assignment problem

Open Access is an initiative that aims to make scientific research freely available to all. To date our community has made over 100 million downloads. It’s based on principles of collaboration, unobstructed discovery, and, most importantly, scientific progression. As PhD students, we found it difficult to access the research we needed, so we decided to create a new Open Access publisher that levels the playing field for scientists across the world. How? By making research easy to access, and puts the academic needs of the researchers before the business interests of publishers.

We are a community of more than 103,000 authors and editors from 3,291 institutions spanning 160 countries, including Nobel Prize winners and some of the world’s most-cited researchers. Publishing on IntechOpen allows authors to earn citations and find new collaborators, meaning more people see your work not only from your own field of study, but from other related fields too.

Brief introduction to this section that descibes Open Access especially from an IntechOpen perspective

Want to get in touch? Contact our London head office or media team here

Our team is growing all the time, so we’re always on the lookout for smart people who want to help us reshape the world of scientific publishing.

Home > Books > Concepts, Applications and Emerging Opportunities in Industrial Engineering

Weapon Target Assignment

Submitted: 26 May 2020 Reviewed: 20 August 2020 Published: 06 October 2020

DOI: 10.5772/intechopen.93665

Cite this chapter

There are two ways to cite this chapter:

From the Edited Volume

Concepts, Applications and Emerging Opportunities in Industrial Engineering

Edited by Gary Moynihan

To purchase hard copies of this book, please contact the representative in India: CBS Publishers & Distributors Pvt. Ltd. www.cbspd.com | [email protected]

Chapter metrics overview

693 Chapter Downloads

Impact of this chapter

Total Chapter Downloads on intechopen.com

Total Chapter Views on intechopen.com

This chapter is mainly based on an important sector of operation research-weapon’s assignment (WTA) problem which is a well-known application of optimization techniques. While we discuss about WTA, we need some common terms to be discussed first. In this section, we first introduce WTA problem and then we present some prerequisites such as optimization model, its classification, LP, NLP, SP and their classifications, and applications of SP. We also discuss some relevant software tools we use to optimize the problems. The weapon target assignment problem (WTA) is a class of combinatorial optimization problems present in the fields of optimization and operations research. It consists of finding an optimal assignment of a set of weapons of various types to a set of targets in order to maximize the total expected damage done to the opponent. The WTA problem can be formulated as a nonlinear integer programming problem and is known to be NP-complete. There are constraints on weapons available of various types and on the minimum number of weapons by type to be assigned to various targets. The constraints are linear, and the objective function is nonlinear. The objective function is formulated in terms of probability of damage of various targets weighted by their military value.

• transportation
• non-linear programming

Author Information

Mohammad babul hasan *.

• Department of Mathematics, University of Dhaka, Bangladesh

Yaindrila Barua

• Daffodil International University, Bangladesh

*Address all correspondence to: [email protected]

1. Introduction

This Chapter is mainly based on an important sector of operation research-weapon’s target assignment (WTA) problem which is a well-known application of optimization techniques. While we discuss about WTA, we need some common terms to be discussed first. In this section, we first introduce WTA problem and then we present some prerequisites such as optimization model, its classification, LP, NLP, SP and their classifications, and applications of SP. We also discuss some relevant software tools we use to optimize the problems.

1.1 Weapon target assignment

The weapon target assignment problem (WTA) is a class of combinatorial optimization problems present in the fields of optimization and operations research. It consists of finding an optimal assignment of a set of weapons of various types to a set of targets in order to maximize the total expected damage done to the opponent. The WTA problem can be formulated as a nonlinear integer programming problem and is known to be NP-complete. There are constraints on weapons available of various types and on the minimum number of weapons by type to be assigned to various targets. The constraints are linear, and the objective function is nonlinear. The objective function is formulated in terms of probability of damage of various targets weighted by their military value.

1.2 Preliminaries

In the current section, we discuss some preliminaries of the terms we mention in the chapter.

1.2.1 Optimization model

Optimization means ‘the action of finding the best solution’. Optimization modeling is also known as Mathematical Programming. Mathematical programming is the use of mathematical models, particularly optimizing models, to assist in making decisions. It is a branch of operation research which has wide applications in various areas of human activity. Optimization can help solve problems where there are two situations as (1) many ways of doing something or (2) limited resource available.

1.3 Classification of optimization problem

Any real-world optimization problem may be characterized by five qualities. The problem function may all be linear or be nonlinear. The functional relationships may be known i.e. deterministic, or there may be uncertainty about them i.e. probabilistic. The optimization may take place at a fixed point in time (static) or it may be an optimization over time (dynamic). The variables may be continuous or discrete. And lastly, the problem functions may all be continuously differentiable (smooth) or may have points where the functions are non-differentiable (non-smooth).

1.4 Linear programming (LP)

Linear programming is an optimization technique of a linear objective function, subject to linear equality and linear inequality constraints. It is a mathematical method that is used to determine the best possible outcome or solution from a given set of parameters or a list of requirements, which are represented in the form of linear relationships. It is most often used in computer modeling or simulation in order to find the best solution in allocating finite resources such as money, energy, manpower, machine resources, time, space and many other variables. In most cases, the “best outcome” needed from linear programming is maximum profit or lowest cost. It was first developed by Soviet mathematician and economist Leonid Kantorvich in 1937 during the second world-war.

1.5 Standard form of LP

Here we present the standard form of linear programming. A linear programming problem may be defined as the problem of maximizing or minimizing.

The standard linear programming problem can be expressed in a compact form as:

Maximize (or Minimize)

Decision variables ( x j )—These are the quantities to be determined.

The objective function (1) —This represents how each decision variable would affect the cost, or, simply, the value that needs to be optimized.

Constraints (2) —These represent how each decision variable would use limited amounts of resources.

Data—These quantify the relationships between the objective function and the constraints. c i is called profit or cost coefficients, a ij are the constraint coefficients and b i are the availability of resources or minimum requirement.

1.6 Stochastic programming (SP)

The aim of stochastic programming is to find optimal decisions in problems which involve uncertain data. For optimization under uncertainty stochastic programming is one of the best techniques. That is, stochastic programming is mathematical programs that include data that is not known with certainty but is approximated by probability distributions. Stochastic programming extends the scope of linear and nonlinear programming to include probabilistic or statistical information about one or more uncertain problem parameters. Similarly, when all the input data used in the mathematical formulation of the mathematical program is known with certainty then the corresponding models are called deterministic models.

1.7 Types of SP problem

Stochastic programming offers a solution by eliminating uncertainty and characterizing it using probability distributions. There exist many different types of stochastic problems. The most famous type of stochastic programming model is recourse problems. Another form of a stochastic problem is the chance-constrained programming problem. In this type of stochastic programming model, the constraints to be optimized depend on probabilities. The classification of SP problems is shown in Figure 1 .

Codification of SP problems.

1.8 Applications of stochastic programming

Stochastic programming has been applied to a wide variety of areas. Some of the specific problems are part of the Stochastic Programming test set. Other applications are listed as follows: Manufacturing Production Planning, Manufacturing production capacity planning, Machine Scheduling, Freight scheduling, Dairy Farm Expansion planning, Macroeconomic modeling and planning, Timber management, Asset Liability Management, Portfolio selection, Traffic management, Optimal truss design, Automobile Dealership inventory management, Lake level management.

1.9 Software tools

Nowadays computerized techniques are widely used to solve various types of problems in the world. Sometimes some problems become difficult to solve and time-consuming by hand calculation. So by using different software tools, we can solve problems from small to large scale problem optimally in a short time. There are so many computer-based mathematical programming languages have been used worldwide. Some of the tools that are used to solve optimization problems are LINDO, LINGO, AMPL, MATLAB, MATHEMATICA, MAPLE, MS EXCEL SOLVER and TORA, etc. In this chapter, we use AMPL and LINGO.

AMPL, an acronym for “A Mathematical Programming Language” is a comprehensive and powerful algebraic modeling language for linear and nonlinear optimization problems, with discrete or continuous variables. It is a language for solving high complexity problems for large scale mathematical computation. It was developed by Robert Fourier, David Gay and Brian Kernighan at Bell Laboratories [ 1 ]. By using AMPL, we can get the solution of a problem in which the model of the formulation with sets, variables, parameters, constraints, etc. are written in a mod. file and the data of the formulation are written in a dat. file. Then the solution is found after running the program in the console window.

1.9.2 LINGO

LINGO is designed to solve a wide range of optimization problems, including linear programs, mixed integer programs, quadratic programs, stochastic, and general nonlinear non-convex programs faster, easier and more efficient. It provides a completely integrated package that includes a powerful language for expressing optimization models, a full-featured environment for building and editing problems, and a set of fast built-in solvers.

1.10 Motivation

First one is based on weapons assignment in which the engagement of a target by a weapon is modeled as a stochastic event. In this type of problem, we develop a general computer oriented algorithm so that we can solve this type of problems for small scales to large scales problems in a single framework. To show the effectiveness of our developed model we present numerical examples of WTAP and compare our result with different existing results.

1.11 Outline of the chapter

In Section 1, we discuss some prerequisites that are required for WTA problem. We also discuss about the types of optimization models, software tools that we use in this chapter.

In Section 2, we review some relevant papers about weapon’s assignment problem.

In Section 3, we discuss the weapon target assignment problem. We formulate the WTA problem. Some existing algorithms are also presented in this chapter. We discuss the real-life applications and present numerical examples of WTAP. We develop a new computer technique by using programming language AMPL to solve all type of WTA problem in a single framework. Then finally compare the results we get from AMPL to previously solved results of the examples.

In Section 4, we draw a conclusion about our whole chapter.

1.12 Conclusion

In this Section, we discussed the relevant preliminaries. In the next Section, we will review some literature about weapons assignment and chance-constrained problem.

In this section, we will review some admissible research articles on Weapon Target Assignment Problem. Since the 1950s, the optimal assignment problem of weapons to targets has always been concerned by many countries. The study of WTA problem can be traced back to the 1950s and 1960s when Manne [ 2 ] and Day [ 3 ] built the model of WTA problem. The present research work on WTA is focused on models and algorithms. In the research on models of WTA, the static WTA models are mainly studied and the dynamic WTA are not fully studied indeed. In the research on algorithms of WTA, the intelligent algorithms are often used to solve the WTA problem.

There are so many proposed algorithms on WTA problem [ 4 , 5 ]. So we present the summary of variant heuristic algorithms and the implementation of various WTA have been proposed for several years is shown in Table 1 .

Existing algorithms for several ye.

2. Weapon’s target assignment

Various combinatorial optimization techniques are currently available. Most of these techniques have not been thoroughly tested on realistic problems. In this chapter, we consider a class of non-linear assignment problems collectively referred to as Target-based Weapon Target Assignment (WTA). We first briefly discuss the weapon target assignment problem. We also include the basic concepts and models of WTA and the mathematical nature of the WTA models is also analyzed. We present some real-life applications of WTA here. There does not exist any exact methods for the WTA problem even relatively small size problems, and much research has focused on developing heuristic algorithms based on meta-heuristic techniques. The main focus of this chapter is our new developed optimization algorithm for the WTA problem based on the kill probabilities.

3. Weapon target assignment (WTA) problem

The assignment problem is one of the fundamental constrained combinatorial optimization problems in the branch of optimization or operation research in Mathematics. This problem is mainly used in decision making. Here we consider a special type of problem which is a combination of transportation problem and assignment problem. By the name of weapon-target assignment problem, it is clear that we have to assign weapons to targets. It is a defense-related application in operation research and is slightly different from the more general optimal resource allocation problem. The main aim of weapon-target assignment problem is to find a set of solution of the number of available weapons to a set of required targets so that the expected rewards of the sequential engagement is maximized [ 6 ]. The engagement of a target by a weapon is modeled as a stochastic event, with a probability of kill assigned to each weapon-target pair (this is the probability that the interceptor weapon will destroy the target if assigned to it). The engagement of a weapon-target pair is independent of all other weapons and targets. This is an integer optimization problem in that fractional weapon assignments are not allowed.

3.1 Basic factors of WTA

A number of different approaches have been applied to the WTA problem. When considering a WTA problem, a number of factors need to be considered. Some of these factors are discussed below [ 7 ]:

3.1.1 Linear versus non-linear assignment problem

The generalized linear assignment problem (LAP) of allocating weapons to targets is a fundamental problem of combinatorial optimization. In the simplest case, the number of weapons and targets are equal, with only one weapon being assigned to any one target in an allocation. LAP’s can also be represented in a bipartite graph shown in Figure 2 (a) . In the LAP graph, weapons cannot be assigned to more than one target. But, when targets are assigned to more than one targets or targets, are assigned to more one weapon, then the assignment problem becomes nonlinear as presented by the bipartite graph in Figure 2 (b) .

A linear and a nonlinear bipartite graph.

Weapon target assignments are generally viewed as nonlinear assignment problems (non-LAP). That is, the optimal solution is nonlinear but is still considered to integer values as in the LAP case.

3.1.2 Asset-based versus Target-based

A WTA problem can be viewed from either a target-based or an asset-based perspective. In the target-based, values are assigned to each target to cause damage to the defended asset. The objective of the target-based WTA solution is to maximize the damage value of the incoming targets.

Conversely, in an asset-based perspective values are assigned to the assets rather than the targets. This WTA problem is where weapons are assigned such that the combined value of assets is maximized. The asset-based approach requires information on which targets are approaching the defended assets. But a target-based approach is more appropriate than the asset-based. The approach which is discussed in this chapter is the target-based perspective.

3.1.3 Static versus dynamic

Dynamic WTA

Static WTA: In the static version, all of the inputs (i.e., weapons, targets, desired effects, engagement time, etc.) to the problem are fixed, and all weapons are engaged to targets in a single stage. The damage assessment is made when all the weapons are engaged to the targets completely. Thus the main objective of SWTA [ 8 ] is to find the proper assignment of a temporary defense task. That is, in static WTA the optimal assignment of weapons to targets only allowed a single weapon to be assigned to a single target. Then the static one can be considered as a constrained resource assignment problem. The static version of the problem is a special case of the dynamic one.

Dynamic WTA: Dynamic WTA problem is originally proposed by Hosein and Athans in 1990 [ 9 ], and attract much more attention from researchers in recent years. The goal of DWTA is to find a global optimal assignment for the whole defense process in which the engagement occasion of weapons must be taken into account. The dynamic WTA can also be expressed as a succession of static WTA. That is, in dynamic WTA there are no restrictions as discussed before in SWTA problem. Many weapons can be assigned to a single target. This satisfies the real scenario of a defense system. When the scale is large, the DWTA models are comparatively more complex than the SWTA models. In this paper, we mainly focus on the dynamic weapon-target assignment problem.

In addition, considering the different missions, each version includes the asset-based problem and the target-based problem. In the asset-based problem, the task is to maximize the expected total value of assets which are defended by the defensive weapons. In the target-based problem, the task is to minimize the expected total value of targets which are not destroyed by the defensive weapons after the engagement. The target-based problem can be considered as a special case of the asset-based problem.

3.1.4 Properties of dynamic WTA

NP-Complete (Non-deterministic polynomial), that is one must essentially resort to complete enumeration to find the optimal solution.

Discrete (fractional weapons assignment are not allowed)

Dynamic (the results of previous engagements are observed before making present assignments)

Nonlinear (the objective function is convex)

Stochastic (weapon-target engagements are modeled as stochastic events)

Large-Scale (the number of weapons and targets is large, making enumeration techniques impractical).

These properties of the problem rule out any hope of obtaining efficient optimal algorithms.

3.2 Mathematical formulation of WTA

To present the dynamic weapon-target assignment problem, we need the following parameters and variables to be introduced:

Symbols: Descriptions.

W : The number of Weapon types.

T : The number of targets that must be assigned by weapons.

u j : The military value of the target j s. This is determined during the weapon assignment and used to priorities target engagement.

w i : The number of weapons of type i available to be assigned to targets.

t j : The minimum number of weapons required to target j .

p ij kill : The destroying probability of target j by weapon of type i , also expressed as the kill probability for weapon type i on target j . It’s given for all weapons and targets.

x ij : An integer decision variable indicating the number of weapons of type i assigned to target

j : That is, how many numbers of weapons of type i should be assigned to target j to maximize the expected damage value of targets.

Let there be T targets numbered as 1 , 2 , … , T and W weapon types numbered 1 , 2 , … , W . Then we can now formulate the objective function in terms of probability of damage of various targets weighted by their military value. So the weapon target assignment may now be modeled as the following nonlinear integer programming formulation in terms of the above-introduced variables,

Here we consider p ij kill as the destroying probability by weapons of type i on target j , therefore the term 1 − p ij kill denotes the survival probability for target j if weapon i assigned to it. By the over-all assignment of weapons of all types, ∑ i = 1 W x ij the expected damage to target j is 1 − ∏ i = 1 W 1 − p ij kill x ij . The maximization of the probability of the total expected damaged value of the targets is being represented by the objective function (3) . Limitations on the number of weapons assigned are specified in terms of w i and t j . The constraints represented above by Eqs. (4) and (5) are on weapons available of various types and on the minimum number of weapons to be assigned to various targets. By the Eq. (4) , we can assure that the total number of weapons used does not exceed the available capacity, and as well as the Eq. (5) ensures that the total number of weapons should exceed the minimum number of weapons required for target j s. Eq. (6) provides the non-negativity of decision variables. Here we observe that the resulting problem has non-linear objective function and linear constraints.

3.2.1 Applications of WTA

The WTA problem has wide applications in real life. Some of them are discussed in the current section:

3.3 Air missile system

In an air missile defense system [ 10 , 11 ], missiles are regarded as the major weapon in modern warfare, and missile defense technology becomes a hot research topic for military and information expert. The reasonable target assignment strategy and optimization algorithm for weapon-target assignment improve operational effectiveness greatly. According to target threat degree and air combat priority index of target intercepted, the relative weigh for weapon unit of target attack is definite, the combined effect on target assignment result is weighed, which ensure high target interception as far as possible. In multi-fighter air combat, the weapon target assignment problem is a challenge in information warfare, the air defense command system can assign weapon reasonably for eliminating the threat from enemy targets in time. The selection rules of target function include the facts such as less resource and energy loss for fighter, the minimum threat degree and the minimum number of targets remaining, different selection rule reflect different decision intention, which decided different target function form and combat strategy [ 12 ]. AS an NP-complete problem, with the number increasing in weapon units and targets, the solution space shows the trend of the combined explosion [ 13 ].

3.4 WTA approach to media allocation

In management science, the word advertisement is the most significant term. In advertising, media allocation is a very important task for advertisers. Communication vehicles such as television, newspapers, internet, radio and etc. are referred by the term media in advertising. To convey the commercial messages to target the potential customers, advertisers use the above-mentioned vehicles. In order to maximize the effectiveness of advertising effort, media planning is the process of selecting time and space in various media for advertising. The best media plans provide the target audiences with an optimum level of coverage and opportunities to see the campaign. So, media allocation is to find the proper assignment of number of ads in each vehicle. This allocation problem can be developed as an optimization model, which can also be considered as the WTA problem of military operation research, that allocates media to target audiences.

This problem is an integer nonlinear programming problem which is independent of the duration of an advertising campaign also schedules advertisements during a day. This is an appropriate example of military operations research models that can be adapted to contemporary business world applications.

3.5 Various existing algorithms

Several exact and heuristic algorithms have been proposed to solve the Weapon-Target Assignment problem for several years. Some of them are described briefly below:

3.5.1 Maximum marginal return (MMR) algorithm

Maximum marginal return algorithms are algorithms that assign weapons sequentially with each weapon being assigned to the target which results in the maximum decrease (marginal return) in the objective function value. In other words, in maximum marginal return algorithms, a weapon is always assigned to the target with maximum improvement in the objective function value. Maximum marginal return algorithms are heuristic algorithms, they are easy to implement and efficient algorithms. Although these algorithms do not give the optimal or best solution it is known that these algorithms give near-optimal solutions.

Algorithm : MMR Algorithm

1: solution. Allocations ← {}

2: solution. Value ← MaxValue

3: allocated Weapon Count ← 0

4: while allocated Weapon Count < =no Of Weapons do

5:    max Decrease ← Min Value

6:    k ← 1

7:   while k < unallocated Weapons. Count do

8:    i ← 1

9:    while i < no Of Targets do

10:    decrease ← target Values [i] * kill Probabilities [i][k]

11:    if decrease > max Decrease then

12:     max Decrease ← decrease

13:     allocated Target ← i

14:     allocated Target ← k

15:    end if

16: i ← i +  1

17:   end while

18:    k ← k +  1

19:   end while

20:   unallocated Weapons. Remove (allocated Weapon)

21:   solution. Allocations [ k ] ← allocated Target

22: target Values [ allocated Target ] ← target Values [ allocated Target ]- max Decrease

23:   allocated Weapon Count ← allocated Weapon Count  + 1

24: end while

25: solution. Value ← Calculate Solution Value (solution. allocations)

26: return solution

3.5.2 Genetic algorithms (GA)

A genetic algorithm with greedy eugenics that takes into account a probability of kill value for each weapon is suggested [ 14 ], and compared to MMR algorithm. Although MMR algorithm runs much faster than GA, GA tends to find better solutions than MMR algorithm. And, GA efficiency increases as the number of targets and weapons increases. Also in GA if a set of weapons can also hit a group of targets, meaning that grouping of weapons and targets is possible, this leads to faster and more optimal solutions [ 15 ]. Since the algorithm uses randomization it is a nondeterministic algorithm. The genetic algorithm is given as follows [ 16 ]:

Algorithm : Genetic Algorithm

1: start Time ← Now

2: end Time ← start Time + allowed Search Time

3: solution. Allocations ← {}

4: solution.value ← MaxValue

5: if no Of Targets > no Of Weapons then

6: no Of Individuals ← no Of Targets

8: no Of Individuals ← no Of Weapons

10: population ← Generate Initial Population (no Of Individuals)

11: while end Time < Now do

12: individual No ← 1

13: while individual No < =no Of Individuals do

14:    sol From Indv ← population [individual No]

15:    sol Value From Indv ← Calculate Solution Value (sol From Indv)

16:    if sol Value From Indv < solution. Value then

17:      solution ← sol From Indv

18:    end if

19:    individual No ← individual No +  1

20:    end while

21:    parents ← Select Parents (population)

22:    population ← CrossOver (parents)

23:    population ← Mutate (population)

25: return solution

3.5.3 Ant colony optimization algorithm

Ant-colony optimization takes inspiration from the foraging behavior of ant colonies. Initially all of the ants search for the food randomly. When an ant finds a food, it starts to deposit a chemical substance produced and released into the environment called pheromone on the ground while returning back to the colony. By depositing pheromone on the ground, they mark the path to the food that should be followed by other members of the colony. If an ant comes across a path with pheromone, it stops searching for the food randomly and starts to follow the path marked with pheromone. If it reaches the food, it starts to deposit pheromone on the path back to the colony also. This positive feedback strengthens the pheromone trail on the same path and causes all of the ants to follow a single path. On the other hand, if the path is not followed by other colony members, the pheromone evaporates in time and eventually, the path disappears [ 1 , 16 ].

Ants create solutions.

Created solutions are improved through a local search. This process is also known as daemon actions and it is an optional process.

Pheromone update is applied to increase the pheromone values that are associated with good solutions and to decrease the pheromone values that are associated with bad solutions (pheromone evaporation).

The description of the algorithm is given below:

Algorithm : Ant Colony Optimization Algorithm.

4: solution. value ← MaxValue

6:   no Of Ants ← no Of Targets

8:   no Of Ants ← no Of Weapons

10: Calculate Heuristic Values ()

11: Calculate Pheromone Values ()

12: while end Time < Now do

13:   min Solution Value ← Max Value

14: ant No ← 1

15: while ant No < =no Of Ants do

16:    constructed Sol ← Construct Solution ()

17:    if constructed sol.solution Value < min Solution. Value then

18:    best sol value ← constructed Sol solution Value

19:    iteration Best Sol. Alloc ← constructed Sol. allocations

20:    if constructed Sol. Solution Value < solution. Solution Value then

21:     solution ← constructed sol

22:    end if

23:    end if

24:    Calculate Heuristic Values ()

25:     ant No ← ant No  + 1

26:    end while

27:    Update Pheromone Values (iteration Best Sol Alloc, best Sol Value)

28:    end while

29: return solution

3.6 WTA on real battle field

On modern battlefields, the task of battle managers is very important to make a proper assignment of weapons to targets to defend own-force assets or to offend the opponent targets. As an example, we now consider a target-based weapon-target assignment model for maximizing the total expected damage value of the targets which satisfies the Eqs. (3) – (5) . Here considering five weapons are to be assigned to 20 targets [ 17 , 18 ]. These targets have different probabilities of killing to platforms which are dependent on the target types. That is, the destroying probabilities of targets by different types of weapons obviously will be different. The probabilities define the effectiveness of the ith weapon to jth destroy the target. Here we get by the weapon-target pair that there are total 100 variables that are to be found out. The upper limits on weapon capacity and lower limits on weapons to be assigned are also given.

Breda-SAFAT machine gun

Spandau machine gun

Vickers machine gun

Blue Danube (nuclear weapon)

Each weapon-target pair survival probabilities are shown in Figure 3 .

Survival probabilities of targets by weapons.

The number of available weapons and the military value of targets is shown in [ 19 ] Figure 4 .

Availability of weapons and target military values.

There are also some requirements for weapons to destroy particular targets. Figure 5 shows the minimum number of weapons that must be assigned to some particular targets.

Minimum requirements of weapons assigned to targets.

3.7 Formulation of battle field example

After having all the values of required parameters, we formulate the model corresponding to the given example for maximizing the total expected target damage value as follows:

subject to,

The linear constraints on the available number of weapons of the five types are,

And the linear constraints on the minimum required assignment of weapons to the seven specified targets that must be engaged are:

3.8 Computational complexity of WTAP

The general WTA problem is the situation where a number of W weapon systems have to engage a number of T targets. All weapon systems and all targets may have different characteristics. Also, different weapon systems may require a different amount of time to engage a target. When T > > W an additional problem occurs. So as the scale of WTA problem grows, its computational requirement grows exponentially. So it is quite impossible to solve this type of large scale WTA problem directly. So, computational algorithms are the best approach to solve the large scale dynamic WTA problem [ 8 ].

3.9 Our solution approach for the WTA model

After formulating the problem, we have the Eqs. (7) – (9) . We observe that we have total 100 variables with a nonlinear exponential objective function and 12 linear constraints, which is quite large. There does not exist any exact methods for the WTA problem even relatively small size problems. As there are so many computer based software tools to solve different types of mathematical problems, we propose a computer oriented algorithm to solve such large scale problems in a short time. Our proposed algorithm not only solve large scale WTA problems but also small problems in a single framework. We develop a computerized algorithm in which all types of target-based WTA problem can be solved in a reasonably fast time to help decision makers to make proper assignment on the battlefield.

3.10 The structure of our proposed algorithm for solving the WTAP

Since no real time exact solutions to WTAs are available, either for static or dynamic versions, alternative approximation methodologies must be considered, including heuristic techniques. We develop our computerized algorithm by using the Mathematical Programming Language AMPL.

Algorithm : Our developed Algorithm in AMPL.

Step I : Initialize parameters N, M > 0 and set integers I, J, K.

Step II: Input number of weapons (M) and number of targets (N) and introduce non-negative integer variables x i j .

Step III: Introduce the parameters w i ≥ 0 , t j ≥ 0 , u j ≥ 0 , 0 ≤ p kill ij ≤ 1 . .

Step IV: Define the non-convex objective function to maximize

Step V: Define a set of equations of constraints,

Step VI: Input data of the defined parameters in the ‘dat’ file.

Step VII: Then run this code in the ‘run’ file to calculate the objective function value that is to be maximized by using the solver option such as MINOS, BARON, BONMIN, MINLP, and CONOPT. By using the command “ EXPAND” we can show the expansion of objective function and constraints in the console.

Step VIII: Display the solution value in the console.

Using the new developed algorithm by AMPL, we can solve the WTAP for the large numbers of weapons and targets using the single model file with different data values according to the different scale problems.

3.11 Results of the WTAP using our developed method

As our developed method is based on computerized tools, so we first develop the general code in AMPL. Then update the data file for the Eqs. (7) – (9) . And finally run the AMPL code, then we get our desired result as an output file (Appendix-A) in AMPL. Subsequent to adjusting the quantity of weapons to the closest whole numbers, the outcomes have appeared in.

3.12 Comparison between two results of the WTAP

For several years this type of weapon-target assignment has been performed at the Research analysis. Here we have taken the numerical problem presented in [ 18 ]. We have presented the result of the WTAP by using our developed method in Table 2 . Bracken et al. [ 18 ] solved this problem and got a set of solution of the number of weapons assigned to targets shown in Figure 6 .

Number of weapons assigned to targets.

Now to check the efficiency of our model we compare the two results of the problem graphically. Then for the both results we calculate the objective function that is to be maximized. Here the graphical representation of total number of weapons assigned to targets of the results are shown in Figure 7 .

Comparison of the results between the two methods.

Objective Function (Existing Solution): Max z = 1733.81

Objective Function (Our Result): Max z = 1735.57

Comparing the above two results, we have the better result than the existing result. That is, we have the maximum objective function. This concludes that our proposed method gives the effective result. Our developed AMPL code studied in this Chapter improved the existing solution by 0.1%.

3.13 Numerical example of media allocation

Comparing media allocation with the WTA problem, we can consider the weapons as media vehicles to be advertised when the military targets as target audiences to be intended to reach. People exposed by media vehicles at different times of the day are given as target audiences. The weapon numbers x ij are determined as the number of ads.

The number of ads refers to the number of times within a given period time an audience is exposed to a media schedule. The mathematical programming model is as follows under the assumption that the target audience is constant to be exposed by such media vehicles in given period time.

We formulate the media allocation as the weapon-target assignment model which satisfies the Eqs. (3) – (6) .

Here i = 1 , 2 , … , W be the number of kinds of advertisements,

j = 1 , 2 , … , T be the number of segments,

w i be the available number of advertisements of type i ,

t j be the minimum required number of ads for the target audience j s,

u j be the relative segment weights.

x ij be the number of advertisements of type i assigned to target j ,

p kill ij be the probability of reaching the target audience j by a single ad type i .

So here the objective is to maximize the total probability of reaching the target audiences.

Suppose a company is planning to start an advertising campaign for a particular product. That company takes four target audiences as morning, afternoon, prime and night time of the day. Also, they take 15 vehicles such as somoy news, BTV, Channel I, NTV, ETV, ATN News, GTV, Radio Today, Radio Foorti, Facebook, Prothom Alo, Ittefaq, Billboard, Printings, and E-mail. That company knows the percentages of reaching the target audiences in different time partitions according to the mentioned media vehicles. The probabilities of reaching target audiences are shown in the following table. In Table 2 , we can see that some vehicles have 0 probability to reach some targets. Prime time is the most important segment, as night time is the least important segment for the product. Moreover, the segment weights facilitate marketers to give relative importance with respect to product or service characteristics. The weights can be changed with respect to the features of the product.

The probability of reaching target audiences.

Probability Matrix ( p kill ij ):

3.14 Formulation of media allocation problem

Our objective is to make a proper assignment of ads to targets for maximizing the effectiveness of advertising. The objective function along with total 19 constraints (15 supply constraints for media vehicles and 4 demand constraints for target audiences) are given below:

Maximize, z =

Subject to, the linear constraints on the available number ads of 15 media types are,

And, the linear constraints on the minimum required ads of media vehicles to the four specified target audiences that must be engaged are:

3.15 Solution of the media allocation problem

We develop a near optimization model which allocate media vehicles to predetermined target segments. As this media allocation problem is formulated by using weapon-target assignment problem with 60 decision variables. By using our algorithm, we have solved the Media Allocation problem in a short time. In this case, we only change the data values in the ‘dat’ file, use the same mod.file and run.file. The result is given in Figure 8 .

Number of ads reaching to target audiences.

3.16 Comparison of media allocation result with other existing solution

This hypothetical example was given and solved by using MS Excel [ 20 ] and meta-heuristic genetic algorithm [ 21 ] previously. We have used our proposed algorithm to solve the media allocation problem. The solutions obtained by using genetic algorithm [ 21 ] and MS Excel [ 20 ] are shown in Tables 3 and 4 , respectively [ 22 ].

Media allocation solution by genetic algorithm.

Media allocation solution by MS excel solver.

To check the efficiency of our model, we need to calculate the objective function for all the existing solution that is to be maximized. So the graphical representation of the existing solutions of Media Allocation and objective function value for the corresponding results is shown in Figure 9 .

Comparison the results between the three solving methods.

In Figure 9 it is clear that, our model gives the best result compared to other two methods. By analyzing the values of the objective function, we can see that the Genetic algorithm improved the solution using MS Excel by 0.004%. Thus, the AMPL algorithm employed in this study improved the previous solution using Genetic Algorithm and MS Excel Solver 0.033% and 0.037% respectively.

In this effort, we have proposed the AMPL program code as a meta-heuristic tool for the solution of all type of dynamic weapon-target assignment problem. We have discussed two numerical examples and we have compared the results of the problems with previously solved results. We have observed that our proposed computational algorithm is easy to compute and gives a nearby optimal solution than other methods in a short time. We believe that AMPL program approach is a good and feasible alternative for the solution of this type class of problems. As further research, we may employ our developed AMPL program approach for the problem with many targets, many weapons or advertising tools as well.

4. Conclusions

This chapter is performed on two types of optimization such as the weapon’s assignment problem.

In a warfare scenario, weapons allocation is very important. Since no exact algorithm is available to solve the WTAP, it is quite unavailable to estimate the quality of solutions produced by heuristic methods. The purpose of this chapter was to develop a new computerized algorithm to find a feasible solution in a reasonably fast time to help decision makers to make a proper assignment on the battlefield. We have developed a new computer-oriented algorithm by using AMPL to avoid the computational problems and solve this type of large scale problems. Our algorithm has been applied in two numerical examples of WTA problem and we have compared the complete outputs of the specified large scale problems with the outputs of the existing algorithms. We have concluded that our developed algorithm gives us the better result than others.

Finally, we conclude that the programming language AMPL is an effective technique to compute different types of optimization problems which will reduce the computational time for large scale problems. Overall, we have developed computer-oriented algorithms to solve the mentioned applications of optimization problems.

• 1. Lee Z-J, Lee C-Y, Su S-F. An immunity-based ant colony optimization algorithm for solving weapon–target assignment problem. Applied Soft Computing. 2002; 2 (1):39-47
• 2. Manne AS. A target-assignment problem. Operations Research. 1958; 6 (3):346-351
• 3. Day H. Allocating weapons to target complexes by means of nonlinear programming. Operations Research. 1966; 14 (6):992-1013
• 4. Li Y, Kou Y, Li Z, Xu A, Chang Y. A modified Pareto ant colony optimization approach to solve bi-objective weapon-target assignment problem. International Journal of Aerospace Engineering. 2017; 2017 :1746124, 14 pages
• 5. Tokgoz A, Bulkan S. Weapon target assignment with combinatorial optimization techniques. International Journal of Advanced Research in Artificial Intelligence. 2013; 2 (7):39-50
• 6. Zhang Y, Rennong Y, Zuo J, Xiaoning J. Improved MOEA/D for dynamic weapon target assignment problem. Journal of Harbin Institute of Technology. 2015; 22 (6):121-128
• 7. Hammond L. Application of a Dynamic Programming Algorithm for Weapon Target Assignment. Weapons and Combat Systems Division; 2016
• 8. Li X, Zhou D, Pan Q, Tang Y, Huang J. Weapon-Target Assignment Problem by Multi-objective Evolutionary Algorithm Based on Decomposition, Complexity. 2018; 2018 :19
• 9. Hosein PA, Athans M. Some analytical results for the dynamic weapon-target allocation problem. In: MIT Laboratory for Information and Decision Systems with Partial Support, Cambridge, MA, Tech. Rep. LIDS-p-1944. 1990
• 10. Ma Y, Chou C. Weapon Target Assignment Decision Based on Markov Decision Process in Air Defense. In: Xiao T, Zhang L, Ma S editors. System Simulation and Simulation and Scientific Computing. ICSC. Berlin, Heidelberg: Springer; Vol. 327. 2012. pp. 353-360
• 11. Boardman NT, Lunday BJ, Robbins MJ. Heterogeneous surfaceto-air missile defense battery location: A game theoretic approach. Journal of Heuristics. 2017; 23 (6):417-447
• 12. Cai H, Liu J, Chen Y, Wang H. Survey of the research on dynamic weapon-target assignment problem. Journal of Systems Engineering and Electronics. 2006; 17 (3):559-565
• 13. ACM, Karasakal O. Air defense missile-target allocation models for a naval task group. Computers & Operations Research. 2008; 35 (6):1759-1770
• 14. Lee ZJ, Su SF, Lee CY. Efficiently solving general weapon-target assignment problem by genetic algorithms with greedy eugencies. IEEE Transactions on Systems, Man, and Cybernetics. 2003; 33 (1):113-121
• 15. Ahuja RK, Kumar A, Jha KC, Orlin JB. Exact and heuristic algorithms for the weapon-target assignment problem. Operations Research. 2007; 55 (6):1136-1146
• 16. Lee Z-J, Su S-F, Lee C-Y. A genetic algorithm with domain knowledge for weapon-target assignment problems. Journal of the Chinese Institute of Engineers. 2002; 25 (3):287-295
• 17. Mylander WC III. Applied mathematical programming. In: Proc. U.S. Army operations Res. Symp., Part 1. March; 1965
• 18. Bracken J, McCormick G. Selected Application of Nonlinear Programming. New York: John Wiley & Sons; 1980
• 19. Bogdanowicz ZR, Tolano A, Patel K, Coleman NP. Optimization of weapon–target pairings based on kill probabilities. IEEE Transactions on Cybernetics. 2013; 43 (6):1835-1844
• 20. Çetin E, Esen ST. A weapon-target assignment approach to media allocation. Applied Mathematics and Computation. 2006; 175 (2):1266-1275
• 21. Timur K, Cetin E. A genetic algorithm meta heuristic for the weapon-target based media allocation problem. Alphanumeric Journal. 2015; 3 (1)
• 22. Yanxia W, Longjun Q, Zhi G, Lifeng M. Weapon target assignment problem satisfying expected damage probabilities based on ant colony algorithm. Journal of Systems Engineering and Electronics. 2008; 19 (5):939-944

© 2020 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Continue reading from the same book

Published: 07 January 2021

By Suthep Butdee

723 downloads

By Omar Ahmed Al-Shebeeb

760 downloads

By Gary P. Moynihan

858 downloads

A heuristic and metaheuristic approach to the static weapon target assignment problem

• Published: 14 August 2020
• Volume 78 , pages 791–812, ( 2020 )

Cite this article

• Alexander G. Kline   ORCID: orcid.org/0000-0003-1454-1249 1 ,
• Darryl K. Ahner 2 &
• Brian J. Lunday 2  

775 Accesses

7 Citations

Explore all metrics

The weapon target assignment (WTA) problem, which has received much attention in the literature and is of continuing relevance, seeks within an air defense context to assign interceptors (weapons) to incoming missiles (targets) to maximize the probability of destroying the missiles. Kline et al. (J Heuristics 25:1–21, 2018) developed a heuristic algorithm based upon the solution to the Quiz Problem to solve the WTA. This heuristic found solutions within 6% of optimal, on average, for smaller problem instances and, when compared to a leading WTA heuristic from the literature, identified superlative solutions for larger instances within hundredths of a second, in lieu of minutes or hours of computational effort. Herein, we propose and test an improvement to the aforementioned heuristic, wherein a modified implementation iteratively blocks exiting assignments to an initial feasible solution, allowing superior solutions that would otherwise be prevented via a greedy selection process to be found. We compare these results to the optimal solutions as reported by a leading global optimization solver (i.e., BARON) and find solutions that are, at worst, within 2% of optimality and, at best, up to 64% better than the solutions reported to be optimal by BARON. To wit, the developed metaheuristic outperformed BARON in 25% of all instances tested, as BARON reported a suboptimal solution as being optimal for 21.1% of the instances, and it could not identify an optimal solution for the remaining 6.67% of the instances within 2 h of CPU time, a liberally imposed time limit that far exceeds practical usage considerations for this application.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

Weapon-target assignment problem: exact and approximate solution algorithms

Research on Dynamic Photoelectric Weapon-Target Assignment Problem Based on NSGA-II

Fast and Simple Method for Weapon Target Assignment in Air Defense Command and Control System

Ahner, D.K.: Planning and control of unmanned aerial vehicles in a stochastic environment. Doctor of Philosophy dissertation, Boston University (2005)

Ahuja, R.K., Kumar, A., Jha, K.C., Orlin, J.B.: Exact and heuristic algorithms for the weapon-target assignment problem. Oper. Res. 55 (6), 1136–1146 (2007)

Article   MathSciNet   Google Scholar  

BARON Publications: The Optimization Firm. BARON Publications. http://www.minlp.com/baron-publications (2018)

Bertsekas, D.P., Castañon, D.A.: Rollout algorithms for stochastic scheduling problems. J. Heuristics 5 (1), 89–108 (1999)

Article   Google Scholar  

Chang, S.C., James, R.M., Shaw, J.J.: Assignment algorithm for kinetic energy weapons in boost phase defense. In: 26th IEEE Conference on Decision and Control, vol. 26, pp. 1678–1683. IEEE (1987)

Couenne (2016) Couenne, an Exact Solver for Nonconvex MINLPs. https://projects.coin-or.org/Couenne

den Broeder, G., Ellison, R., Emerling, L.: On optimum target assignments. Oper. Res. 7 (3), 322–326 (1959)

Johansson, F., Falkman, G.: An empirical investigation of the static weapon-target allocation problem. In: Proceedings of the 3rd Skövde Workshop on Information Fusion Topics (SWIFT2009), Sweden (2009)

Kline, A.G., Ahner, D.K., Lunday, B.J.: Real-time heuristic algorithms for the static weapon target assignment problem. J. Heuristics 25 , 1–21 (2018)

Google Scholar  

Kolitz, S.E.: Analysis of a maximum marginal return assignment algorithm. In: Proceedings of the 27th IEEE Conference on Decision and Control, pp 2431–2436. IEEE (1988)

Kristensen, H.M.: Norris RS (2018) Chinese nuclear forces. Bull. At. Sci. 74 (4), 289–295 (2018)

Kwon, O., Kang, D., Lee, K., Park, S.: Lagrangian relaxation approach to the targeting problem. Naval Res. Logist. 46 (6), 640–653 (1999)

Lastusilta, T., Bussieck, M.R., Westerlund, T.: An experimental study of the gams/alphaecp minlp solver. Ind. Eng. Chem. Res. 48 (15), 7337–7345 (2009)

Lee, Z.J., Lee, C.Y., Su, S.F.: An immunity-based ant colony optimization algorithm for solving weapon-target assignment problem. Appl. Soft Comput. 2 (1), 39–47 (2002a)

Lee, Z.J., Su, S.F., Lee, C.Y.: A genetic algorithm with domain knowledge for weapon-target assignment problems. J. Chin. Inst. Eng. 25 (3), 287–295 (2002b)

Lee, Z.J., Su, S.F., Lee, C.Y.: Efficiently solving general weapon-target assignment problem by genetic algorithms with greedy eugenics. IEEE Trans. Syst. Man Cybern. Part B (Cybern.) 33 (1), 113–121 (2003)

LINDO: Global Solver Tab. https://www.lindo.com/doc/online_help/ lingo17_0/index.html?global_solver_tab.htm (2019)

Lloyd, S.P., Witsenhausen, H.S.: Weapons allocation is NP-complete. In: 1986 Summer Computer Simulation Conference, pp. 1054–1058 (1986)

Manne, A.S.: A target-assignment problem. Oper. Res. 6 (3), 346–351 (1958)

Neumaier, A., Shcherbina, O., Huyer, W., Vinkó, T.: A comparison of complete global optimization solvers. Math. Program. 103 (2), 335–356 (2005)

SCIP (2019) Scip optimization suite. what is SCIP? https://scip.zib.de/index.php# scipoptsuite

Shang, G., Zaiyue, Z., Xiaoru, Z., Cungen, C.: Immune genetic algorithm for weapon-target assignment problem. In: Workshop on Intelligent Information Technology Application, pp. 145–148. IEEE (2007)

Wacholder, E.: A neural network-based optimization algorithm for the static weapon-target assignment problem. ORSA J. Comput. 1 (4), 232–246 (1989)

Zeng, X., Zhu, Y., Nan, L., Hu, K., Niu, B., He, X.: Solving weapon-target assignment problem using discrete particle swarm optimization. In: The Sixth World Congress on Intelligent Control and Automation, 2006. WCICA 2006, vol. 1, pp. 3562–3565. IEEE (2006)

Download references

Acknowledgements

The authors gratefully thank the Area Editor, the Associate Editor, and an anonymous reviewer for their constructive comments that helped improve the presentation of this paper.

Author information

Authors and affiliations.

US Army, 700 Defense Pentagon, Washington, DC, 20301, USA

Alexander G. Kline

WPAFB, 2950 Hobson Way, Dayton, OH, 45433-7765, USA

Darryl K. Ahner & Brian J. Lunday

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Alexander G. Kline .

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Kline, A.G., Ahner, D.K. & Lunday, B.J. A heuristic and metaheuristic approach to the static weapon target assignment problem. J Glob Optim 78 , 791–812 (2020). https://doi.org/10.1007/s10898-020-00938-4

Download citation

Received : 11 October 2017

Accepted : 02 August 2020

Published : 14 August 2020

Issue Date : December 2020

DOI : https://doi.org/10.1007/s10898-020-00938-4

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Weapon target assignment problem
• Quiz problem
• Find a journal
• Publish with us
• Track your research

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications

Branch-and-adjust for the Weapon Target Assignment Problem

tuliotoffolo/wta

Folders and files, repository files navigation, branch-and-adjust for a nonlinear assignment problem.

Written by Túlio Toffolo and Konstantin Pavlikov .

Please address all contributions, suggestions, and inquiries to the current project administrator.

More information

This repository contains a solver for the Weapon-Target Assignment Problem (WTA).

The developed approach is detailed in the following article :

To cite the code, please use the bibtex above.

• python3 wta_cplex.py data/wta_50x100x1.txt
• python3 wta_cplex.py data/wta_50x100x1.txt -delta 0.00001 -solution solutions/wta_50x100x1.sol -threads 1

Instance and solution files

Instance and solution files are available in the data folder of this repository.

Requirements

The entire code was written in Python 3 using Cplex 12.10 's library. Therefore, Cplex must be installed in your system.

If you have any questions, please feel free to contact us.

• Python 100.0%

MIT Libraries home DSpace@MIT

• DSpace@MIT Home
• Laboratory for Information and Decision Systems (LIDS)
• LIDS Technical Reports

The dynamic weapon-target assignment problem

Description

Date issued, series/report no., collections.

A Reinforcement Learning Method for the Weapon Target Assignment Problem with Unknown Hit Rate

Ieee account.

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.