static weapon target assignment problem

Real-time heuristic algorithms for the static weapon target assignment problem

New citation alert added.

This alert has been successfully added and will be sent to:

You will be notified whenever a record that you have chosen has been cited.

To manage your alert preferences, click on the button below.

New Citation Alert!

Please log in to your account

Information & Contributors

Bibliometrics & citations, view options.

• Altinoz O (2020) Modeling of synchronous weapon target assignment problem for howitzer based defense line 2020 IEEE Congress on Evolutionary Computation (CEC) 10.1109/CEC48606.2020.9185578 (1-8) Online publication date: 19-Jul-2020 https://dl.acm.org/doi/10.1109/CEC48606.2020.9185578

Index Terms

Computing methodologies

Artificial intelligence

Search methodologies

Heuristic function construction

Information systems

Data management systems

Database administration

Data dictionaries

Theory of computation

Design and analysis of algorithms

Mathematical optimization

Recommendations

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

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

Exact and Heuristic Algorithms for the Weapon-Target Assignment Problem

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

Constrained Weapon–Target Assignment: Enhanced Very Large Scale Neighborhood Search Algorithm

Optimization problems solved using very large scale neighborhood (VLSN) search algorithms include scheduling problems, the capacitated minimum spanning tree problem, the traveling salesman problem, and weapon-target assignment (WTA). This correspondence ...

Information

Published in.

Kluwer Academic Publishers

United States

Publication History

Author tags.

• Branch and bound
• Convex programming
• Global optimization
• Quiz problem
• Weapon target assignment problem

Contributors

Other metrics, bibliometrics, article metrics.

• 1 Total Citations View Citations
• 0 Total Downloads
• Downloads (Last 12 months) 0
• Downloads (Last 6 weeks) 0

View options

Login options.

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Share this publication link.

Copying failed.

Share on social media

Affiliations, export citations.

• Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
• Download citation
• Copy citation

We are preparing your search results for download ...

We will inform you here when the file is ready.

Your file of search results citations is now ready.

Your search export query has expired. Please try again.

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

727 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

756 downloads

By Omar Ahmed Al-Shebeeb

799 downloads

By Gary P. Moynihan

897 downloads

IntechOpen Author/Editor? To get your discount, log in .

Discounts available on purchase of multiple copies. View rates

Local taxes (VAT) are calculated in later steps, if applicable.

Support: [email protected]

Real-time heuristic algorithms for the static weapon target assignment problem

• Journal of Heuristics 25(6)

• Air Force Institute of Technology

Abstract and Figures

Discover the world's research

• 25+ million members
• 160+ million publication pages
• 2.3+ billion citations
• Adnan Ahmad
• Rawan Amjad

• Ali Ezad Abbas
• APPL SOFT COMPUT

• Shuangfei Xu
• Shizheng Zhang
• Qingling Wang

• Xiaojie Jin
• Tianyan Zhou
• Changsheng Gao

• Zhengzhuo Liang
• COMPUT IND ENG

• Mingfang Ni

• Kang Fengju
• David W. Walkup
• M. D. MacLaren
• R. E. Ellison
• L. Emerling

• Zhou Bing-hai
• Richard H. Day

• Recruit researchers
• Join for free
• Login Email Tip: Most researchers use their institutional email address as their ResearchGate login Password Forgot password? Keep me logged in Log in or Continue with Google Welcome back! Please log in. Email · Hint Tip: Most researchers use their institutional email address as their ResearchGate login Password Forgot password? Keep me logged in Log in or Continue with Google No account? Sign up

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

The Weapon-Target Assignment Problem

SUMMARY Various combinatorial optimization techniques are currently available. Most of these techniques have not been thourougly tested on realistic problems. The EUCLID (EUropean Cooperation for the Long term In Defence) CALMA (Combinatorial Algorithms for Military Applications) RTP (Research and Technology Project) 6.4 project has the main objective to investigate the relevance of various existing algorithmic optimization techniques to the actual solution of complex combinatorial problems arising in military applications.

Related Papers

International Journal of Advanced Research in Artificial Intelligence

Serol Bulkan

Operations Research-Baltimore

krishna jha

Jay Rosenberger

Antonios Tsourdos

The weapon target assignment (WTA) problem has been designed to match the Command & Control (C2) requirement in military context, of which the goal is to find an allocation plan enabling to treat a specific scenario in assigning available weapons to oncoming targets. The WTA always get into situation weapons defending an area or assets from an enemy aiming to destroy it. Because of the uniqueness of each situation, this problem must be solved in real-time and evolve accordingly to the aerial/ground situation. By the past, the WTA was solved by an operator taking all the decisions, but because of the complexity of the modern warfare, the resolution of the WTA in using the power of computation is inevitable to make possible the resolution in real time of very complex scenarii involving different type of targets. Nowadays, in most of the C2 this process is designed in order to be as a support for a human operator and in helping him in the decision making process. The operator will give its final green light to proceed the intervention.

Istanbul University - DergiPark

Elif Bozkaya

Dr. Mohammad Babul Hasan

This chapter is mainly based on an important sector of operation researchweapon’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 availa...

Proceedings of the 3rd Skövde Workshop on …

Göran Falkman

Abstract—The allocation of weapons to targets (such as missiles and hostile aircrafts) is a well-known resource allocation problem within the field of operations research. It has been proven that this problem, in general, is NP-complete. For this reason, optimal solutions to ...

Lloyd Hammond

Patrick Hosein

International Journal of Advanced Computer Science and Applications

Safak Bayir

Loading Preview

Sorry, preview is currently unavailable. You can download the paper by clicking the button above.

RELATED PAPERS

Tehnicki vjesnik - Technical Gazette

Dr. İsa AVCI

Lecture Notes in Electrical Engineering

Gokturk Ucoluk

kemal leblebicioglu

Fred Glover

Applied Soft Computing

Gopalakrishnan N

Computers & Industrial Engineering

Mehmet Fatih Hocaoğlu

Anurag Ningwal

Knowledge Based Systems

Asif Masood

Gerald G. Brown

Magnus Hindsberger

Mathematical Problems in Engineering

Heungseob Kim

Signal and Data Processing of Small Targets 2008

Erik Blasch

Defence Science Journal

SANJAY BISHT

Journal of Intelligent & …

Craig Tovey

International Journal of Information Technology & Decision Making

Adel Guitouni

Neural Processing Letters

Mohammad Eshaghnezhad

Applied Mathematics and Computation

Seda Tolun Tayalı

kusum yadav

Sungsoo Park

IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans

Dimitri Bertsekas

Applied Mathematical Modelling

Dr. K.R. Guruprasad MED

Journal of the Operational Research Society

Afshan Naseem

Nick Coleman

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024

• DOI: 10.1016/j.cor.2018.10.015
• Corpus ID: 71142897

The Weapon-Target Assignment Problem

• Alexander G. Kline , D. Ahner , R. Hill
• Published in Computers & Operations… 1 May 2019
• Engineering, Mathematics

64 Citations

Weapon-target assignment problem: exact and approximate solution algorithms, bi-objective dynamic weapon-target assignment problem with stability measure, weapon–target assignment using a whale optimization algorithm, a novel genetic algorithm for the synthetical sensor-weapon-target assignment problem, constrained multi-objective weapon target assignment for area targets by efficient evolutionary algorithm, a performance comparison of utility functions for game theory based weapon-target assignment, a study on the weapon–target assignment problem considering heading error, multi-weapon multi-target assignment based on hybrid genetic algorithm in uncertain environment, opposition-based memetic algorithm for the shared weapon target assignment problem, a multi-objective sparse evolutionary framework for large-scale weapon target assignment based on a reward strategy, 78 references, the dynamic weapon-target assignment problem, dynamic weapon-target assignment problems with vulnerable c2 nodes, 2 exact and heuristic algorithms for the weapon target assignment problem, the generalized weapon target assignment problem, efficient heuristic approach to the weapon-target assignment problem, weapon target assignment with combinatorial optimization techniques, an empirical investigation of the static weapon-target allocation problem, a heuristic and metaheuristic approach to the static weapon target assignment problem, an approximate algorithm for a weapon target assignment stochastic program, a two-step optimisation method for dynamic weapon target assignment problem, related papers.

Showing 1 through 3 of 0 Related Papers

Weapon-target assignment problem: exact and approximate solution algorithms

• Original Research
• Published: 13 January 2022
• Volume 312 , pages 581–606, ( 2022 )

Cite this article

• Alexandre Colaers Andersen 1 ,
• Konstantin Pavlikov   ORCID: orcid.org/0000-0002-3345-5058 1 &
• Túlio A. M. Toffolo 2  

2185 Accesses

15 Citations

3 Altmetric

Explore all metrics

The Weapon-Target Assignment (WTA) problem aims to assign a set of weapons to a number of assets (targets), such that the expected value of survived targets is minimized. The WTA problem is a nonlinear combinatorial optimization problem known to be NP-hard. This paper applies several existing techniques to linearize the WTA problem. One linearization technique (Camm et al. in Oper Res 50(6):946–955, 2002) approximates the nonlinear terms of the WTA problem via convex piecewise linear functions and provides heuristic solutions to the WTA problem. Such approximation problems are, though, relatively easy to solve from the computational point of view even for large-scale problem instances. Another approach proposed by O’Hanley et al. (Eur J Oper Res 230(1):63–75, 2013) linearizes the WTA problem exactly at the expense of incorporating a significant number of additional variables and constraints, which makes many large-scale problem instances intractable. Motivated by the results of computational experiments with these existing solution approaches, a specialized new exact solution approach is developed, which is called branch-and-adjust. The proposed solution approach involves the compact piecewise linear convex under-approximation of the WTA objective function and solves the WTA problem exactly. The algorithm builds on top of any existing branch-and-cut or branch-and-bound algorithm and can be implemented using the tools provided by state-of-the-art mixed integer linear programming solvers. Numerical experiments demonstrate that the proposed specialized algorithm is capable of handling very large scale problem instances with up to 1500 weapons and 1000 targets, obtaining solutions with optimality gaps of up to \(2.0\%\) within 2 h of computational runtime.

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

Access this article

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime

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

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

Real-time heuristic algorithms for the static weapon target assignment problem

Optimal multi-stage allocation of weapons to targets using adaptive dynamic programming.

For more information concerning the callback functions, the reader is directed to IBM and ILOG ( 2020 ).

Source code available at https://github.com/tuliotoffolo/wta .

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

Article   Google Scholar  

Camm, J. D., Norman, S. K., Polasky, S., & Solow, A. R. (2002). Nature reserve site selection to maximize expected species covered. Operations Research, 50 (6), 946–955.

Cetin, E., & Esen, S. T. (2006). A weapon-target assignment approach to media allocation. Applied Mathematics and Computation, 175 (2), 1266–1275.

Chang, S.-c., James, R. M., & Shaw, J. J. (1987). Assignment algorithm for kinetic energy weapons in boost phase defence. In 26th IEEE conference on decision and control (Vol. 26, pp. 1678–1683), IEEE.

Day, R. H. (1966). Allocating weapons to target complexes by means of nonlinear programming. Operations Research, 14 (6), 992–1013.

denBroeder Jr, G., Ellison, R., & Emerling, L. (1959). On optimum target assignments. Operations Research, 7 (3), 322–326.

Eckler, A. R., & Burr, S. A. (1972). Mathematical models of target coverage and missile allocation . Technical report, Military Operations Research Society Alexandria, VA.

Esen, Ö., Çetin, E., & Esen, S. T. (2008). A mathematical immunochemoradiotherapy model: A multiobjective approach. Nonlinear Analysis: Real World Applications, 9 (2), 511–517.

Glover, F. (1975). Improved linear integer programming formulations of nonlinear integer problems. Management Science, 22 (4), 455–460.

IBM, ILOG. (2020). CPLEX optimization studio user manual.

Kline, A., Ahner, D., & Hill, R. (2019). The weapon-target assignment problem. Computers&amp; Operations Research, 105, 226–236.

Lu, Y., & Chen, D. Z. (2021). A new exact algorithm for the weapon-target assignment problem. Omega, 98, 102138.

Manne, A. S. (1958). A target-assignment problem. Operations Research, 6 (3), 346–351.

Matlin, S. (1970). A review of the literature on the missile-allocation problem. Operations Research, 18 (2), 334–373.

Metler, W. A., Preston, F. L., & Hofmann, J. (1990). A suite of weapon assignment algorithms for a SDI mid-course battle manager . Technical report, Naval Research Lab Washington, DC.

Murphey, R. A., (2000). Target-based weapon target assignment problems. In Nonlinear assignment problems (pp. 39–53), Springer.

O’Hanley, J. R., Scaparra, M. P., & García, S. (2013). Probability chains: A general linearization technique for modeling reliability in facility location and related problems. European Journal of Operational Research, 230 (1), 63–75.

Sonuc, E., Sen, B., & Bayir, S. (2017). A parallel simulated annealing algorithm for weapon-target assignment problem. International Journal of Advanced Computer Science and Applications, 8 (4), 87–92.

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

Download references

Author information

Authors and affiliations.

Department of Business and Management, University of Southern Denmark, Campusvej 55, 5230, Odense M, Denmark

Alexandre Colaers Andersen & Konstantin Pavlikov

Department of Computing, Federal University of Ouro Preto, Campus Universitário Morro do Cruzeiro, Ouro Preto, MG, 35400-000, Brazil

Túlio A. M. Toffolo

You can also search for this author in PubMed   Google Scholar

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

Andersen, A.C., Pavlikov, K. & Toffolo, T.A.M. Weapon-target assignment problem: exact and approximate solution algorithms. Ann Oper Res 312 , 581–606 (2022). https://doi.org/10.1007/s10479-022-04525-6

Download citation

Accepted : 03 January 2022

Published : 13 January 2022

Issue Date : May 2022

DOI : https://doi.org/10.1007/s10479-022-04525-6

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

• Branch-and-adjust
• Integer programming
• Weapon-target assignment problem
• Probability chains
• Find a journal
• Publish with us
• Track your research

• Stack Overflow for Teams Where developers & technologists share private knowledge with coworkers
• Advertising & Talent Reach devs & technologists worldwide about your product, service or employer brand
• OverflowAI GenAI features for Teams
• OverflowAPI Train & fine-tune LLMs
• Labs The future of collective knowledge sharing
• About the company Visit the blog

Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Get early access and see previews of new features.

Can you solve the Static Weapon Target Assignment problem in CVXPY?

I am trying to analyse the static weapon target assignment (WTA) problem with CVXPY. My first goal is to get a small instance of the problem running in order to test that I have implemented the objective function and constraints correctly (and subsequently scale up and add parameters), but I am encountering errors that I do not know how to resolve.

The problem description is as follows:

My code is below (please forgive any poor coding, I am a relative novice). Here, I am only considering two weapons and two targets and I have specified notional probability values. The decision variable is boolean because each weapon can only be assigned once to each target.

Weapon 1 should be assigned to target 2 and weapon 2 to target 1. However, when I run my code, I receive the following error message:

I have tried various other CVXPY solvers (CBC, CPLEX, GLPK_MI, GUROBI, XPRESS) and have encountered the same error message.

If I add an additional constraint to limit the number of weapons that can be aimed at a target (see below), the error remains.

I suspect there is an issue with my objective function because if I interchange it with something simpler (see below for an example), the problem can be solved. However, this does not reflect the objective function of the static WTA problem. In my code, I have attempted to capture the x_{ij} decision variable as an exponent in the objective function, but this may be causing the issues. I am not sure how else the objective function can be specified whilst working within the constraints of CVXPY.

Does anyone know how I can get my code to run in CVXPY according to the problem that I am considering? Should the objective function be specified differently? Is the problem incompatible with CVXPY?

• assignment-problem

• Your formulation requires a solver that can do both mixed-integer and exponential cone and that, correct me if I'm wrong, is only MOSEK according to cvxpy.org/tutorial/advanced/index.html#choosing-a-solver –  Michal Adamaszek Commented Mar 3, 2023 at 9:02
• Thanks for the reply - I am able to get my code to run with MOSEK. –  BRavos Commented Mar 7, 2023 at 7:10
• Where does the printscreen come from? –  Rodrigo de Azevedo Commented Mar 8, 2023 at 6:46
• From a paper I am writing. I figured printscreening it was easier than trying to re-write the maths. –  BRavos Commented Mar 8, 2023 at 6:55
• No need for reference, then. Easier than re-writing, but search engines cannot understand PNG files as well as plain text. In the future, you may want to post related questions at or.stackexchange.com –  Rodrigo de Azevedo Commented Mar 8, 2023 at 7:15

With CPLEX (outside of cvxpy) you could use constraint programming and write:

with the OPL API.

Which gives

You can do the same within python through docplex cplex python API

Your Answer

Reminder: Answers generated by artificial intelligence tools are not allowed on Stack Overflow. Learn more

Sign up or log in

Post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged python cvxpy assignment-problem or ask your own question .

• The Overflow Blog
• This developer tool is 40 years old: can it be improved?
• Unpacking the 2024 Developer Survey results
• Featured on Meta
• We've made changes to our Terms of Service & Privacy Policy - July 2024
• Introducing an accessibility dashboard and some upcoming changes to display...
• Tag hover experiment wrap-up and next steps

Hot Network Questions

• When can a citizen's arrest of an Interpol fugitive be legal in Washington D.C.?
• Tips/strategies to managing my debt
• What would "doctor shoes" have looked like in "Man on the Moon"?
• What does "No camping 10-21" mean?
• How can I select all pair of two points A and B has integer coordinates and length of AB is also integer?
• Did Einstein say the one-way speed-of-light is "not a fact of nature"?
• Why do most published papers hit the maximum page limit exactly?
• New job, reporting manager is not replying to me after a few days: how to proceed?
• What is an external IDE 37 DBI pin device?
• Set all numbers greater than "X" bold, for decimal numbers
• Set up GeForce GT 620 for Ubuntu 24.04
• Can a wizard learn a spell from a cleric or druid?
• Is threatening to go to the police blackmailing?
• Reference for the proof that Möbius transformations extend to isometries of hyperbolic 3-space
• Is there a pre-defined compiler macro for legacy Microsoft C 5.10 to get the compiler's name and version number?
• A spaceship travelling at speed of light
• How important is a "no reflection" strategy for 1 Hz systems?
• What does the circuit shown in the picture do?
• What is "were't"?
• Is it OK to call a person "sempai" who is actually much younger than you?
• Fundamental group of a compact Riemannian manifold whose universal covering is not compact
• High-precision solution for the area of a region
• English equivalent to the famous Hindi proverb "the marriage sweetmeat: those who eat it regret, and those who don't eat it also regret"?
• Possible downsides of not dealing with the souls of the dead

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.