Open access peer-reviewed chapter

# Weapon Target Assignment

Written By

Mohammad Babul Hasan and Yaindrila Barua

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

DOI: 10.5772/intechopen.93665

From the Edited Volume

## Concepts, Applications and Emerging Opportunities in Industrial Engineering

Edited by Gary Moynihan

Chapter metrics overview

View Full Metrics

## Abstract

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.

### Keywords

• weapon
• assignment
• transportation
• non-linear programming

## 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)

z=i=1ncixiE1
subject toj=1maijxj=bi,i=1,2,,nE2
xj0j=1,2,,m

The basic components of linear programming are as follows:

• Decision variables (xj)—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. ci is called profit or cost coefficients, aij are the constraint coefficients and bi 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.

### 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.

#### 1.9.1 AMPL

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

This chapter contains four sections in total which is organized as follows:

• 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.

ResearchersYearProposed AlgorithmsImplementation WTA
Galat and Simaan2007TabuDynamic single-objective
Lee2010VLSNStatic single-objective
Xin et al.2010VP + TabuDynamic single-objective
Chen et al.2010SAStatic single-objective
Fei et al.2012Auction AlgorithmStatic single-objective
Liu et al.2013MOPSOStatic multi-objective
Zhang et al.2014MOEA/DStatic multi-objective
Ahner and Parson2015Dynamic ProgrammingDynamic multi-objective
Li et al.2015NSGA-II, MOEA/DStatic multi-objective
Driik et al.2015MILPDynamic multi-objective
Liang and Kang2016CSAStatic single-objective
Li et al.2016MDEDynamic multi-objective

### 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).

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

Generally, WTA is categorized into two versions:

1. Static WTA

2. 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

Some relevant properties of the dynamic WTA problem are that it is:

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

2. Discrete (fractional weapons assignment are not allowed)

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

4. Nonlinear (the objective function is convex)

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

6. 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.

uj: The military value of the target js. This is determined during the weapon assignment and used to priorities target engagement.

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

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

pijkill: 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.

xij: 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,

maxj=1Tuj1i=1W1pijkillxij,E3
subject to,j=1Txijwii=1,.,WE4
i=1Wxijtjj=1,.,TE5
xij0,integer,i=1,,Wandj=1,,TE6

Here we consider pijkill as the destroying probability by weapons of type i on target j, therefore the term 1pijkill denotes the survival probability for target j if weapon i assigned to it. By the over-all assignment of weapons of all types, i=1Wxij the expected damage to target j is 1i=1W1pijkillxij. 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 wi and tj. 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 js. 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

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. ValueMaxValue

3: allocated Weapon Count0

4: whileallocated Weapon Count < =no Of Weaponsdo

5:   max DecreaseMin Value

6:   k1

7:  whilek < unallocated Weapons. Countdo

8:   i 1

9:   whilei < no Of Targetsdo

10:   decreasetarget Values [i] * kill Probabilities [i][k]

11:   ifdecrease > max Decreasethen

12:    max Decreasedecrease

13:    allocated Targeti

14:    allocated Targetk

15:   end if

16: ii + 1

17:  end while

18:   kk + 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 Countallocated Weapon Count + 1

24: end while

25: solution. ValueCalculate Solution Value (solution. allocations)

26: returnsolution

#### 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 TimeNow

2: end Timestart Time + allowed Search Time

3: solution. Allocations {}

4: solution.valueMaxValue

5: if no Of Targets > no Of Weaponsthen

6: no Of Individualsno Of Targets

7: else

8: no Of Individualsno Of Weapons

9: end if

10: populationGenerate Initial Population (no Of Individuals)

11: whileend Time < Now do

12: individual No 1

13: whileindividual No < =no Of Individualsdo

14:   sol From Indvpopulation [individual No]

15:   sol Value From IndvCalculate Solution Value (sol From Indv)

16:   ifsol Value From Indv < solution. Valuethen

17:     solutionsol From Indv

18:   end if

19:   individual Noindividual No + 1

20:   end while

21:   parentsSelect Parents (population)

22:   populationCrossOver (parents)

23:   populationMutate (population)

24: end while

25: returnsolution

#### 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].

An Ant-Colony Optimization algorithm basically consists of 3 main steps. After the initialization of pheromone trails, while there is still time, at each iteration:

1. Ants create solutions.

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

3. 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.

1: start TimeNow

2: end Timestart Time + allowed Search Time

3: solution. Allocations {}

4: solution. valueMaxValue

5: if no Of Targets > no Of Weaponsthen

6:  no Of Antsno Of Targets

7: else

8:  no Of Antsno Of Weapons

9: end if

10: Calculate Heuristic Values ()

11: Calculate Pheromone Values ()

12: whileend Time < Now do

13:  min Solution ValueMax Value

14: ant No 1

15: whileant No < =no Of Antsdo

16:   constructed SolConstruct Solution ()

17:   ifconstructed sol.solution Value < min Solution. Valuethen

18:   best sol valueconstructed Sol solution Value

19:   iteration Best Sol. Allocconstructed Sol. allocations

20:   ifconstructed Sol. Solution Value < solution. Solution Valuethen

21:    solutionconstructed sol

22:   end if

23:   end if

24:   Calculate Heuristic Values ()

25:    ant Noant No + 1

26:   end while

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

28:   end while

29: returnsolution

### 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.

The characteristics of the five weapon types could be thought as follows:

1. Breda-SAFAT machine gun

2. Lewis gun

3. Spandau machine gun

4. Vickers machine gun

5. Blue Danube (nuclear weapon)

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

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

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.

### 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:

z=601.001x110.84x210.96x311x410.92x51+501.000.95x120.83x220.95x321x420.94x52+501.001x130.85x230.96x331x430.92x53+751.001x140.84x240.96x341x440.95x54+401.001x150.85x250.96x351x450.95x55+601.000.85x160.81x260.90x361x460.98x56+351.000.90x170.81x270.92x371x470.98x57+301.000.85x180.82x280.91x381x481x58+251.000.80x190.80x290.92x391x491x59+1501.001x1,100.86x2,100.95x3,100.96x4,100.90x5,10+301.001x1,111x2,110.99x3,110.91x4,110.95x5,11+451.001x1,120.98x2,120.98x3,120.92x4,120.96x5,12+1251.001x1,131x2,130.99x3,130.91x4,130.91x5,13+2001.001x1,140.88x2,140.98x3,140.92x4,140.98x5,14+2001.001x1,150.87x2,150.97x3,150.98x4,150.99x5,15+1301.001x1,160.88x2,160.98x3,160.93x4,160.99x5,16+1001.001x1,170.85x2,180.95x3,171x4,171x5,17+1001.000.95x1,180.84x2,180.92x3,181x4,181x5,18+1001.001x1,190.85x2,190.93x3,191x4,191x5,19+1501.001x1,200.85x2,200.92x3,201x4,201x5,20E7

subject to,

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

x11+x12+x+13x14+x15+x16+x17+x18+x19+x1,10+x1,11+x1,12+x1,13+x1,14+x1,15+x1,16+x1,17+x1,18+x1,19+x1,20200x21+x22+x+23x24+x25+x26+x27+x28+x29+x2,10+x2,11+x2,12+x2,13+x2,14+x2,15+x2,16+x2,17+x2,18+x2,19+x2,20100x31+x32+x+33x34+x35+x36+x37+x38+x39+x3,10+x3,11+x3,12+x3,13+x3,14+x3,15+x3,16+x3,17+x3,18+x3,19+x3,20300x41+x42+x+43x44+x45+x46+x47+x48+x49+x4,10+x4,11+x4,12+x4,13+x4,14+x4,15+x4,16+x4,17+x4,18+x4,19+x4,20150x51+x52+x+53x54+x55+x56+x57+x58+x59+x5,10+x5,11+x5,12+x5,13+x5,14+x5,15+x5,16+x5,17+x5,18+x5,19+x5,20250E8

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

x11+x21+x31+x41+x5130x16+x26+x36+x46+x56100x1,10+x2,10+x3,10+x4,10+x5,1040x1,14+x2,14+x3,14+x4,14+x5,1450x1,15+x2,15+x3,15+x4,15+x5,1570x1,16+x2,16+x3,16+x4,16+x5,1635x1,20+x2,20+x3,20+x4,20+x5,2030E9

### 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 variablesxij.

Step III: Introduce the parameterswi0,tj0,uj0,0pkillij1..

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

j=1Juj1i=1I1pkillijijxij

Step V: Define a set of equations of constraints,

j=1Jxijwi;i=1,,M;i=1Ixijtj;i=1,,N;

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.

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.

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 xij 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).

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

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

uj be the relative segment weights.

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

pkillij 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.

Media vehiclesMorning time (1)Afternoon time (2)Prime time (3)Night time (4)Ad capacities
Somoy News (1)0.210.120.120.238
BTV (2)0.350.240.120.077
Channel I (3)0.190.0400.199
NTV (4)00.260.190.135
ETV (5)0.130.190.2506
ATN News (6)0.240.140.220.098
GTV (7)0.0900.180.283
Prothom Alo (11)0.120.110.030.098
Ittefaq (12)0.320.230.090.214
Billboard (13)0.320.10.280.024
Printings (14)0.230.120.080.034
E-mail (15)0.290.070.040.324
Segment weights2341

### Table 2.

The probability of reaching target audiences.

Probability Matrix (pkillij):

### 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 =

2[1.00(0.79x110.65x210.81x311x410.87x510.76x610.91x710.61x810.76x910.9x10,10.88x11,10.68x12,10.68x13,10.77x14,10.71x15,1)]+3[1.00(0.88x120.76x220.96x320.74x420.81x520.86x621x720.83x820.69x920.77x10,20.89x11,20.77x12,20.90x13,20.88x14,20.93x15,2)]+4[1.00(0.88x130.88x231x330.81x430.75x530.78x630.82x730.53x830.86x930.97x10,30.97x11,30.91x12,30.72x13,30.92x14,30.96x15,3)]+1[1.00(0.77x140.93x240.81x340.87x441x540.81x640.72x741x840.57x940.65x10,40.91x11,40.79x12,40.98x13,40.97x14,40.68x15,4)]E10

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

x11+x12+x13+x148x21+x22+x23+x247x31+x32+x33+x349x41+x42+x43+x445x51+x52+x53+x546x61+x62+x63+x648x71+x72+x73+x743x81+x82+x83+x8410x91+x92+x93+x9415x10,1+x10,2+x10,3+x10,412x11,1+x11,2+x11,3+x11,48x12,1+x12,2+x12,3+x12,44x13,1+x13,2+x13,3+x13,44x14,1+x14,2+x14,3+x14,44x15,1+x15,2+x15,3+x15,44E11

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

x11+x21+x31+x41+x51+x61+x71+x81+x91+x10,1+x11,1+x12,1+x13,1+x14,1+x15,116x12+x22+x32+x42+x52+x62+x72+x82+x92+x10,2+x11,2+x12,2+x13,2+x14,2+x15,218x13+x23+x33+x43+x53+x63+x73+x83+x93+x10,3+x11,3+x12,3+x13,3+x14,3+x15,325x14+x24+x34+x44+x54+x64+x74+x84+x94+x10,4+x11,4+x12,4+x13,4+x14,4+x15,410E12

### 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.

### 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 vehiclesMorning time (1)Afternoon time (2)Prime time (3)Night time (4)
Somoy News (1)0000
BTV (2)7000
Channel I (3)6102
NTV (4)0500
ETV (5)0060
ATN News (6)2050
GTV (7)0000
Prothom Alo (11)2222
Ittefaq (12)1111
Billboard (13)1111
Printings (14)1111
E-mail (15)1111

### Table 3.

Media allocation solution by genetic algorithm.

Media vehiclesMorning time (1)Afternoon time (2)Prime time (3)Night time (4)
Somoy news (1)1000
BTV (2)7000
Channel I (3)7002
NTV (4)0500
ETV (5)0060
ATN news (6)0050
GTV (7)0000
Prothom Alo (11)2222
Ittefaq (12)1111
Billboard (13)1111
Printings (14)1111
E-mail (15)1111

### Table 4.

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.

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.

## References

1. 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. 2. Manne AS. A target-assignment problem. Operations Research. 1958;6(3):346-351
3. 3. Day H. Allocating weapons to target complexes by means of nonlinear programming. Operations Research. 1966;14(6):992-1013
4. 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. 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. 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. 7. Hammond L. Application of a Dynamic Programming Algorithm for Weapon Target Assignment. Weapons and Combat Systems Division; 2016
8. 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. 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. 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. 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. 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. 13. ACM, Karasakal O. Air defense missile-target allocation models for a naval task group. Computers & Operations Research. 2008;35(6):1759-1770
14. 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. 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. 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. 17. Mylander WC III. Applied mathematical programming. In: Proc. U.S. Army operations Res. Symp., Part 1. March; 1965
18. 18. Bracken J, McCormick G. Selected Application of Nonlinear Programming. New York: John Wiley & Sons; 1980
19. 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. 20. Çetin E, Esen ST. A weapon-target assignment approach to media allocation. Applied Mathematics and Computation. 2006;175(2):1266-1275
21. 21. Timur K, Cetin E. A genetic algorithm meta heuristic for the weapon-target based media allocation problem. Alphanumeric Journal. 2015;3(1)
22. 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

Written By

Mohammad Babul Hasan and Yaindrila Barua

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