Existing algorithms for several ye.
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.
- non-linear programming
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.
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)
The basic components of linear programming are as follows:
Decision variables ()—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. is called profit or cost coefficients, are the constraint coefficients and 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
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 . 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.
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.
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.
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  and Day  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.
|Researchers||Year||Proposed Algorithms||Implementation WTA|
|Galat and Simaan||2007||Tabu||Dynamic single-objective|
|Xin et al.||2010||VP + Tabu||Dynamic single-objective|
|Li and Dong||2010||DPSO+SA||Dynamic single-objective|
|Chen et al.||2010||SA||Static single-objective|
|Fei et al.||2012||Auction Algorithm||Static single-objective|
|Liu et al.||2013||MOPSO||Static multi-objective|
|Zhang et al.||2014||MOEA/D||Static multi-objective|
|Ahner and Parson||2015||Dynamic Programming||Dynamic multi-objective|
|Li et al.||2015||NSGA-II, MOEA/D||Static multi-objective|
|Driik et al.||2015||MILP||Dynamic multi-objective|
|Liang and Kang||2016||CSA||Static single-objective|
|Li et al.||2016||MDE||Dynamic multi-objective|
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 . 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 :
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:
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:
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:
: The number of Weapon types.
: The number of targets that must be assigned by weapons.
: The military value of the target s. This is determined during the weapon assignment and used to priorities target engagement.
: The number of weapons of type available to be assigned to targets.
: The minimum number of weapons required to target .
: The destroying probability of target by weapon of type , also expressed as the kill probability for weapon type on target . It’s given for all weapons and targets.
: An integer decision variable indicating the number of weapons of type assigned to target
: That is, how many numbers of weapons of type should be assigned to target to maximize the expected damage value of targets.
Let there be targets numbered as and weapon types numbered . 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 as the destroying probability by weapons of type on target , therefore the term denotes the survival probability for target if weapon assigned to it. By the over-all assignment of weapons of all types, the expected damage to target is . 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 and . 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 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 . AS an NP-complete problem, with the number increasing in weapon units and targets, the solution space shows the trend of the combined explosion .
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.
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 , 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 . Since the algorithm uses randomization it is a nondeterministic algorithm. The genetic algorithm is given as follows :
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:
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:
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 weapon to 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:
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.
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:
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 weapon systems have to engage a number of 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 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 .
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.
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 . We have presented the result of the WTAP by using our developed method in Table 2. Bracken et al.  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.
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 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.
Here be the number of kinds of advertisements,
be the number of segments,
be the available number of advertisements of type ,
be the minimum required number of ads for the target audience s,
be the relative segment weights.
be the number of advertisements of type assigned to target ,
be the probability of reaching the target audience by a single ad type .
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 vehicles||Morning time (1)||Afternoon time (2)||Prime time (3)||Night time (4)||Ad capacities|
|Somoy News (1)||0.21||0.12||0.12||0.23||8|
|Channel I (3)||0.19||0.04||0||0.19||9|
|ATN News (6)||0.24||0.14||0.22||0.09||8|
|Radio Today (8)||0.39||0.17||0.47||0||10|
|Radio Foorti (9)||0.24||0.31||0.14||0.43||15|
|Prothom Alo (11)||0.12||0.11||0.03||0.09||8|
|Number of ads required||16||18||25||10|
Probability Matrix ():
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.
3.16 Comparison of media allocation result with other existing solution
This hypothetical example was given and solved by using MS Excel  and meta-heuristic genetic algorithm  previously. We have used our proposed algorithm to solve the media allocation problem. The solutions obtained by using genetic algorithm  and MS Excel  are shown in Tables 3 and 4, respectively .
|Media vehicles||Morning time (1)||Afternoon time (2)||Prime time (3)||Night time (4)|
|Somoy News (1)||0||0||0||0|
|Channel I (3)||6||1||0||2|
|ATN News (6)||2||0||5||0|
|Radio Today (8)||2||0||8||0|
|Radio Foorti (9)||0||14||0||1|
|Prothom Alo (11)||2||2||2||2|
|Total no of ads||23||26||25||21|
|Media vehicles||Morning time (1)||Afternoon time (2)||Prime time (3)||Night time (4)|
|Somoy news (1)||1||0||0||0|
|Channel I (3)||7||0||0||2|
|ATN news (6)||0||0||5||0|
|Radio today (8)||2||0||8||0|
|Radio foorti (9)||0||15||0||0|
|Prothom Alo (11)||2||2||2||2|
|Total no. of ads||23||26||25||20|
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.
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.
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
Manne AS. A target-assignment problem. Operations Research. 1958; 6(3):346-351
Day H. Allocating weapons to target complexes by means of nonlinear programming. Operations Research. 1966; 14(6):992-1013
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
Tokgoz A, Bulkan S. Weapon target assignment with combinatorial optimization techniques. International Journal of Advanced Research in Artificial Intelligence. 2013; 2(7):39-50
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
Hammond L. Application of a Dynamic Programming Algorithm for Weapon Target Assignment. Weapons and Combat Systems Division; 2016
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
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
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
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
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
ACM, Karasakal O. Air defense missile-target allocation models for a naval task group. Computers & Operations Research. 2008; 35(6):1759-1770
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
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
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
Mylander WC III. Applied mathematical programming. In: Proc. U.S. Army operations Res. Symp., Part 1. March; 1965
Bracken J, McCormick G. Selected Application of Nonlinear Programming. New York: John Wiley & Sons; 1980
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
Çetin E, Esen ST. A weapon-target assignment approach to media allocation. Applied Mathematics and Computation. 2006; 175(2):1266-1275
Timur K, Cetin E. A genetic algorithm meta heuristic for the weapon-target based media allocation problem. Alphanumeric Journal. 2015; 3(1)
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