methods of solving assignment problem

Assignment Problem: Meaning, Methods and Variations | Operations Research

After reading this article you will learn about:- 1. Meaning of Assignment Problem 2. Definition of Assignment Problem 3. Mathematical Formulation 4. Hungarian Method 5. Variations.

Meaning of Assignment Problem:

An assignment problem is a particular case of transportation problem where the objective is to assign a number of resources to an equal number of activities so as to minimise total cost or maximize total profit of allocation.

The problem of assignment arises because available resources such as men, machines etc. have varying degrees of efficiency for performing different activities, therefore, cost, profit or loss of performing the different activities is different.

Thus, the problem is “How should the assignments be made so as to optimize the given objective”. Some of the problem where the assignment technique may be useful are assignment of workers to machines, salesman to different sales areas.

Definition of Assignment Problem:

ADVERTISEMENTS:

Suppose there are n jobs to be performed and n persons are available for doing these jobs. Assume that each person can do each job at a term, though with varying degree of efficiency, let c ij be the cost if the i-th person is assigned to the j-th job. The problem is to find an assignment (which job should be assigned to which person one on-one basis) So that the total cost of performing all jobs is minimum, problem of this kind are known as assignment problem.

The assignment problem can be stated in the form of n x n cost matrix C real members as given in the following table:

For each row of the matrix, find the smallest element and subtract it from every element in its row.
Do the same (as step 1) for all columns.
Cover all zeros in the matrix using minimum number of horizontal and vertical lines.
Test for Optimality: If the minimum number of covering lines is n, an optimal assignment is possible and we are finished. Else if lines are lesser than n, we haven’t found the optimal assignment, and must proceed to step 5.
Determine the smallest entry not covered by any line. Subtract this entry from each uncovered row, and then add it to each covered column. Return to step 3.

Try it before moving to see the solution

Explanation for above simple example:

An example that doesn’t lead to optimal value in first attempt: In the above example, the first check for optimality did give us solution. What if we the number covering lines is less than n.

Time complexity : O(n^3), where n is the number of workers and jobs. This is because the algorithm implements the Hungarian algorithm, which is known to have a time complexity of O(n^3).

Space complexity : O(n^2), where n is the number of workers and jobs. This is because the algorithm uses a 2D cost matrix of size n x n to store the costs of assigning each worker to a job, and additional arrays of size n to store the labels, matches, and auxiliary information needed for the algorithm.

In the next post, we will be discussing implementation of the above algorithm. The implementation requires more steps as we need to find minimum number of lines to cover all 0’s using a program. References: http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf https://www.youtube.com/watch?v=dQDZNHwuuOY

Please Login to comment...

Mathematical
How to Delete Whatsapp Business Account?
Discord vs Zoom: Select The Efficienct One for Virtual Meetings?
Otter AI vs Dragon Speech Recognition: Which is the best AI Transcription Tool?
Google Messages To Let You Send Multiple Photos
30 OOPs Interview Questions and Answers (2024)

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Hungarian Method

The Hungarian method is a computational optimization technique that addresses the assignment problem in polynomial time and foreshadows following primal-dual alternatives. In 1955, Harold Kuhn used the term “Hungarian method” to honour two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry. Let’s go through the steps of the Hungarian method with the help of a solved example.

Hungarian Method to Solve Assignment Problems

The Hungarian method is a simple way to solve assignment problems. Let us first discuss the assignment problems before moving on to learning the Hungarian method.

What is an Assignment Problem?

A transportation problem is a type of assignment problem. The goal is to allocate an equal amount of resources to the same number of activities. As a result, the overall cost of allocation is minimised or the total profit is maximised.

Because available resources such as workers, machines, and other resources have varying degrees of efficiency for executing different activities, and hence the cost, profit, or loss of conducting such activities varies.

Assume we have ‘n’ jobs to do on ‘m’ machines (i.e., one job to one machine). Our goal is to assign jobs to machines for the least amount of money possible (or maximum profit). Based on the notion that each machine can accomplish each task, but at variable levels of efficiency.

Hungarian Method Steps

Check to see if the number of rows and columns are equal; if they are, the assignment problem is considered to be balanced. Then go to step 1. If it is not balanced, it should be balanced before the algorithm is applied.

Step 1 – In the given cost matrix, subtract the least cost element of each row from all the entries in that row. Make sure that each row has at least one zero.

Step 2 – In the resultant cost matrix produced in step 1, subtract the least cost element in each column from all the components in that column, ensuring that each column contains at least one zero.

Step 3 – Assign zeros

Analyse the rows one by one until you find a row with precisely one unmarked zero. Encircle this lonely unmarked zero and assign it a task. All other zeros in the column of this circular zero should be crossed out because they will not be used in any future assignments. Continue in this manner until you’ve gone through all of the rows.
Examine the columns one by one until you find one with precisely one unmarked zero. Encircle this single unmarked zero and cross any other zero in its row to make an assignment to it. Continue until you’ve gone through all of the columns.

Step 4 – Perform the Optimal Test

The present assignment is optimal if each row and column has exactly one encircled zero.
The present assignment is not optimal if at least one row or column is missing an assignment (i.e., if at least one row or column is missing one encircled zero). Continue to step 5. Subtract the least cost element from all the entries in each column of the final cost matrix created in step 1 and ensure that each column has at least one zero.

Step 5 – Draw the least number of straight lines to cover all of the zeros as follows:

(a) Highlight the rows that aren’t assigned.

(b) Label the columns with zeros in marked rows (if they haven’t already been marked).

(d) Continue with (b) and (c) until no further marking is needed.

(f) Simply draw the lines through all rows and columns that are not marked. If the number of these lines equals the order of the matrix, then the solution is optimal; otherwise, it is not.

Step 6 – Find the lowest cost factor that is not covered by the straight lines. Subtract this least-cost component from all the uncovered elements and add it to all the elements that are at the intersection of these straight lines, but leave the rest of the elements alone.

Step 7 – Continue with steps 1 – 6 until you’ve found the highest suitable assignment.

Hungarian Method Example

Use the Hungarian method to solve the given assignment problem stated in the table. The entries in the matrix represent each man’s processing time in hours.

$\begin{array}{l}\begin{bmatrix} & I & II & III & IV & V \\1 & 20 & 15 & 18 & 20 & 25 \\2 & 18 & 20 & 12 & 14 & 15 \\3 & 21 & 23 & 25 & 27 & 25 \\4 & 17 & 18 & 21 & 23 & 20 \\5 & 18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} $

With 5 jobs and 5 men, the stated problem is balanced.

$\begin{array}{l}A = \begin{bmatrix}20 & 15 & 18 & 20 & 25 \\18 & 20 & 12 & 14 & 15 \\21 & 23 & 25 & 27 & 25 \\17 & 18 & 21 & 23 & 20 \\18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} $

Subtract the lowest cost element in each row from all of the elements in the given cost matrix’s row. Make sure that each row has at least one zero.

$\begin{array}{l}A = \begin{bmatrix}5 & 0 & 3 & 5 & 10 \\6 & 8 & 0 & 2 & 3 \\0 & 2 & 4 & 6 & 4 \\0 & 1 & 4 & 6 & 3 \\2 & 2 & 0 & 3 & 4 \\\end{bmatrix}\end{array} $

Subtract the least cost element in each Column from all of the components in the given cost matrix’s Column. Check to see if each column has at least one zero.

$\begin{array}{l}A = \begin{bmatrix}5 & 0 & 3 & 3 & 7 \\6 & 8 & 0 & 0 & 0 \\0 & 2 & 4 & 4 & 1 \\0 & 1 & 4 & 4 & 0 \\2 & 2 & 0 & 1 & 1 \\\end{bmatrix}\end{array} $

When the zeros are assigned, we get the following:

The present assignment is optimal because each row and column contain precisely one encircled zero.

Where 1 to II, 2 to IV, 3 to I, 4 to V, and 5 to III are the best assignments.

Hence, z = 15 + 14 + 21 + 20 + 16 = 86 hours is the optimal time.

Practice Question on Hungarian Method

Use the Hungarian method to solve the following assignment problem shown in table. The matrix entries represent the time it takes for each job to be processed by each machine in hours.

$\begin{array}{l}\begin{bmatrix}J/M & I & II & III & IV & V \\1 & 9 & 22 & 58 & 11 & 19 \\2 & 43 & 78 & 72 & 50 & 63 \\3 & 41 & 28 & 91 & 37 & 45 \\4 & 74 & 42 & 27 & 49 & 39 \\5 & 36 & 11 & 57 & 22 & 25 \\\end{bmatrix}\end{array} $

Stay tuned to BYJU’S – The Learning App and download the app to explore all Maths-related topics.

Frequently Asked Questions on Hungarian Method

What is hungarian method.

The Hungarian method is defined as a combinatorial optimization technique that solves the assignment problems in polynomial time and foreshadowed subsequent primal–dual approaches.

What are the steps involved in Hungarian method?

The following is a quick overview of the Hungarian method: Step 1: Subtract the row minima. Step 2: Subtract the column minimums. Step 3: Use a limited number of lines to cover all zeros. Step 4: Add some more zeros to the equation.

What is the purpose of the Hungarian method?

When workers are assigned to certain activities based on cost, the Hungarian method is beneficial for identifying minimum costs.

Register with BYJU'S & Download Free PDFs

www.springer.com The European Mathematical Society

StatProb Collection
Recent changes
Current events
Random page
Project talk
Request account
What links here
Related changes
Special pages
Printable version
Permanent link
Page information
View source

Assignment problem

The problem of optimally assigning $ m $ individuals to $ m $ jobs. It can be formulated as a linear programming problem that is a special case of the transport problem :

maximize $ \sum _ {i,j } c _ {ij } x _ {ij } $

$$ \sum _ { j } x _ {ij } = a _ {i} , i = 1 \dots m $$

(origins or supply),

$$ \sum _ { i } x _ {ij } = b _ {j} , j = 1 \dots n $$

(destinations or demand), where $ x _ {ij } \geq 0 $ and $ \sum a _ {i} = \sum b _ {j} $, which is called the balance condition. The assignment problem arises when $ m = n $ and all $ a _ {i} $ and $ b _ {j} $ are $ 1 $.

If all $ a _ {i} $ and $ b _ {j} $ in the transposed problem are integers, then there is an optimal solution for which all $ x _ {ij } $ are integers (Dantzig's theorem on integral solutions of the transport problem).

In the assignment problem, for such a solution $ x _ {ij } $ is either zero or one; $ x _ {ij } = 1 $ means that person $ i $ is assigned to job $ j $; the weight $ c _ {ij } $ is the utility of person $ i $ assigned to job $ j $.

The special structure of the transport problem and the assignment problem makes it possible to use algorithms that are more efficient than the simplex method . Some of these use the Hungarian method (see, e.g., [a5] , [a1] , Chapt. 7), which is based on the König–Egervary theorem (see König theorem ), the method of potentials (see [a1] , [a2] ), the out-of-kilter algorithm (see, e.g., [a3] ) or the transportation simplex method.

In turn, the transportation problem is a special case of the network optimization problem.

A totally different assignment problem is the pole assignment problem in control theory.

This page was last edited on 5 April 2020, at 18:48.
Privacy policy
About Encyclopedia of Mathematics
Disclaimers
Impressum-Legal

Google OR-Tools
Español – América Latina
Português – Brasil
Tiếng Việt

Solving an Assignment Problem

This section presents an example that shows how to solve an assignment problem using both the MIP solver and the CP-SAT solver.

In the example there are five workers (numbered 0-4) and four tasks (numbered 0-3). Note that there is one more worker than in the example in the Overview .

The costs of assigning workers to tasks are shown in the following table.

The problem is to assign each worker to at most one task, with no two workers performing the same task, while minimizing the total cost. Since there are more workers than tasks, one worker will not be assigned a task.

MIP solution

The following sections describe how to solve the problem using the MPSolver wrapper .

Import the libraries

The following code imports the required libraries.

Create the data

The following code creates the data for the problem.

The costs array corresponds to the table of costs for assigning workers to tasks, shown above.

Declare the MIP solver

The following code declares the MIP solver.

Create the variables

The following code creates binary integer variables for the problem.

Create the constraints

Create the objective function.

The following code creates the objective function for the problem.

The value of the objective function is the total cost over all variables that are assigned the value 1 by the solver.

Invoke the solver

The following code invokes the solver.

Print the solution

The following code prints the solution to the problem.

Here is the output of the program.

Complete programs

Here are the complete programs for the MIP solution.

CP SAT solution

The following sections describe how to solve the problem using the CP-SAT solver.

Declare the model

The following code declares the CP-SAT model.

The following code sets up the data for the problem.

The following code creates the constraints for the problem.

Here are the complete programs for the CP-SAT solution.

Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License , and code samples are licensed under the Apache 2.0 License . For details, see the Google Developers Site Policies . Java is a registered trademark of Oracle and/or its affiliates.

Last updated 2023-01-02 UTC.

How to Solve the Assignment Problem: A Complete Guide

Table of Contents

Assignment problem is a special type of linear programming problem that deals with assigning a number of resources to an equal number of tasks in the most efficient way. The goal is to minimize the total cost of assignments while ensuring that each task is assigned to only one resource and each resource is assigned to only one task. In this blog, we will discuss the solution of the assignment problem using the Hungarian method, which is a popular algorithm for solving the problem.

Understanding the Assignment Problem

Before we dive into the solution, it is important to understand the problem itself. In the assignment problem, we have a matrix of costs, where each row represents a resource and each column represents a task. The objective is to assign each resource to a task in such a way that the total cost of assignments is minimized. However, there are certain constraints that need to be satisfied – each resource can be assigned to only one task and each task can be assigned to only one resource.

Solving the Assignment Problem

There are various methods for solving the assignment problem, including the Hungarian method, the brute force method, and the auction algorithm. Here, we will focus on the steps involved in solving the assignment problem using the Hungarian method, which is the most commonly used and efficient method.

Step 1: Set up the cost matrix

The first step in solving the assignment problem is to set up the cost matrix, which represents the cost of assigning a task to an agent. The matrix should be square and have the same number of rows and columns as the number of tasks and agents, respectively.

Step 2: Subtract the smallest element from each row and column

To simplify the calculations, we need to reduce the size of the cost matrix by subtracting the smallest element from each row and column. This step is called matrix reduction.

Step 3: Cover all zeros with the minimum number of lines

The next step is to cover all zeros in the matrix with the minimum number of horizontal and vertical lines. This step is called matrix covering.

Step 4: Test for optimality and adjust the matrix

To test for optimality, we need to calculate the minimum number of lines required to cover all zeros in the matrix. If the number of lines equals the number of rows or columns, the solution is optimal. If not, we need to adjust the matrix and repeat steps 3 and 4 until we get an optimal solution.

Step 5: Assign the tasks to the agents

The final step is to assign the tasks to the agents based on the optimal solution obtained in step 4. This will give us the most cost-effective or profit-maximizing assignment.

Solution of the Assignment Problem using the Hungarian Method

The Hungarian method is an algorithm that uses a step-by-step approach to find the optimal assignment. The algorithm consists of the following steps:

Subtract the smallest entry in each row from all the entries of the row.
Subtract the smallest entry in each column from all the entries of the column.
Draw the minimum number of lines to cover all zeros in the matrix. If the number of lines drawn is equal to the number of rows, we have an optimal solution. If not, go to step 4.
Determine the smallest entry not covered by any line. Subtract it from all uncovered entries and add it to all entries covered by two lines. Go to step 3.

The above steps are repeated until an optimal solution is obtained. The optimal solution will have all zeros covered by the minimum number of lines. The assignments can be made by selecting the rows and columns with a single zero in the final matrix.

Applications of the Assignment Problem

The assignment problem has various applications in different fields, including computer science, economics, logistics, and management. In this section, we will provide some examples of how the assignment problem is used in real-life situations.

Applications in Computer Science

The assignment problem can be used in computer science to allocate resources to different tasks, such as allocating memory to processes or assigning threads to processors.

Applications in Economics

The assignment problem can be used in economics to allocate resources to different agents, such as allocating workers to jobs or assigning projects to contractors.

Applications in Logistics

The assignment problem can be used in logistics to allocate resources to different activities, such as allocating vehicles to routes or assigning warehouses to customers.

Applications in Management

The assignment problem can be used in management to allocate resources to different projects, such as allocating employees to tasks or assigning budgets to departments.

Let’s consider the following scenario: a manager needs to assign three employees to three different tasks. Each employee has different skills, and each task requires specific skills. The manager wants to minimize the total time it takes to complete all the tasks. The skills and the time required for each task are given in the table below:

The assignment problem is to determine which employee should be assigned to which task to minimize the total time required. To solve this problem, we can use the Hungarian method, which we discussed in the previous blog.

Using the Hungarian method, we first subtract the smallest entry in each row from all the entries of the row:

Next, we subtract the smallest entry in each column from all the entries of the column:

We draw the minimum number of lines to cover all the zeros in the matrix, which in this case is three:

Since the number of lines is equal to the number of rows, we have an optimal solution. The assignments can be made by selecting the rows and columns with a single zero in the final matrix. In this case, the optimal assignments are:

Emp 1 to Task 3
Emp 2 to Task 2
Emp 3 to Task 1

This assignment results in a total time of 9 units.

I hope this example helps you better understand the assignment problem and how to solve it using the Hungarian method.

Solving the assignment problem may seem daunting, but with the right approach, it can be a straightforward process. By following the steps outlined in this guide, you can confidently tackle any assignment problem that comes your way.

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you! 😔

Let us improve this post!

Tell us how we can improve this post?

Operations Research

1 Operations Research-An Overview

History of O.R.
Approach, Techniques and Tools
Phases and Processes of O.R. Study
Typical Applications of O.R
Limitations of Operations Research
Models in Operations Research
O.R. in real world

2 Linear Programming: Formulation and Graphical Method

General formulation of Linear Programming Problem
Optimisation Models
Basics of Graphic Method
Important steps to draw graph
Multiple, Unbounded Solution and Infeasible Problems
Solving Linear Programming Graphically Using Computer
Application of Linear Programming in Business and Industry

3 Linear Programming-Simplex Method

Principle of Simplex Method
Computational aspect of Simplex Method
Simplex Method with several Decision Variables
Two Phase and M-method
Multiple Solution, Unbounded Solution and Infeasible Problem
Sensitivity Analysis
Dual Linear Programming Problem

4 Transportation Problem

Basic Feasible Solution of a Transportation Problem
Modified Distribution Method
Stepping Stone Method
Unbalanced Transportation Problem
Degenerate Transportation Problem
Transhipment Problem
Maximisation in a Transportation Problem

5 Assignment Problem

Solution of the Assignment Problem
Unbalanced Assignment Problem
Problem with some Infeasible Assignments
Maximisation in an Assignment Problem
Crew Assignment Problem

6 Application of Excel Solver to Solve LPP

Building Excel model for solving LP: An Illustrative Example

7 Goal Programming

Concepts of goal programming
Goal programming model formulation
Graphical method of goal programming
The simplex method of goal programming
Using Excel Solver to Solve Goal Programming Models
Application areas of goal programming

8 Integer Programming

Some Integer Programming Formulation Techniques
Binary Representation of General Integer Variables
Unimodularity
Cutting Plane Method
Branch and Bound Method
Solver Solution

9 Dynamic Programming

Dynamic Programming Methodology: An Example
Definitions and Notations
Dynamic Programming Applications

10 Non-Linear Programming

Solution of a Non-linear Programming Problem
Convex and Concave Functions
Kuhn-Tucker Conditions for Constrained Optimisation
Quadratic Programming
Separable Programming
NLP Models with Solver

11 Introduction to game theory and its Applications

Important terms in Game Theory
Saddle points
Mixed strategies: Games without saddle points
2 x n games
Exploiting an opponent’s mistakes

12 Monte Carlo Simulation

Reasons for using simulation
Monte Carlo simulation
Limitations of simulation
Steps in the simulation process
Some practical applications of simulation
Two typical examples of hand-computed simulation
Computer simulation

13 Queueing Models

Characteristics of a queueing model
Notations and Symbols
Statistical methods in queueing
The M/M/I System
The M/M/C System
The M/Ek/I System
Decision problems in queueing

OPERATIONS RESEARCH

Lesson 9. solution of assignment problem.

Current course

Procedure, Example Solved Problem | Operations Research - Solution of assignment problems (Hungarian Method) | 12th Business Maths and Statistics : Chapter 10 : Operations Research

Chapter: 12th business maths and statistics : chapter 10 : operations research.

Solution of assignment problems (Hungarian Method)

First check whether the number of rows is equal to the numbers of columns, if it is so, the assignment problem is said to be balanced.

Step :1 Choose the least element in each row and subtract it from all the elements of that row.

Step :2 Choose the least element in each column and subtract it from all the elements of that column. Step 2 has to be performed from the table obtained in step 1.

Step:3 Check whether there is atleast one zero in each row and each column and make an assignment as follows.

Step :4 If each row and each column contains exactly one assignment, then the solution is optimal.

Example 10.7

Solve the following assignment problem. Cell values represent cost of assigning job A, B, C and D to the machines I, II, III and IV.

Here the number of rows and columns are equal.

∴ The given assignment problem is balanced. Now let us find the solution.

Step 1: Select a smallest element in each row and subtract this from all the elements in its row.

Look for atleast one zero in each row and each column.Otherwise go to step 2.

Step 2: Select the smallest element in each column and subtract this from all the elements in its column.

Since each row and column contains atleast one zero, assignments can be made.

Step 3 (Assignment):

Thus all the four assignments have been made. The optimal assignment schedule and total cost is

The optimal assignment (minimum) cost

Example 10.8

Consider the problem of assigning five jobs to five persons. The assignment costs are given as follows. Determine the optimum assignment schedule.

∴ The given assignment problem is balanced.

Now let us find the solution.

The cost matrix of the given assignment problem is

Column 3 contains no zero. Go to Step 2.

Thus all the five assignments have been made. The Optimal assignment schedule and total cost is

The optimal assignment (minimum) cost = ` 9

Example 10.9

Solve the following assignment problem.

Since the number of columns is less than the number of rows, given assignment problem is unbalanced one. To balance it , introduce a dummy column with all the entries zero. The revised assignment problem is

Here only 3 tasks can be assigned to 3 men.

Step 1: is not necessary, since each row contains zero entry. Go to Step 2.

Step 3 (Assignment) :

Since each row and each columncontains exactly one assignment,all the three men have been assigned a task. But task S is not assigned to any Man. The optimal assignment schedule and total cost is

The optimal assignment (minimum) cost = ₹ 35

Principedia

Successful Strategies for Solving Problems on Assignments

Solving complex problems is a challenging task and warrants ongoing effort throughout your career. A number of approaches that expert problem-solvers find useful are summarized below, and you may find these strategies helpful in your own work. Any quantitative problem, whether in economics, science, or engineering, requires a two-step approach: analyze, then compute. Jumping directly to “number-crunching” without thinking through the logic of the problem is counter-productive. Conversely, analyzing a problem and then computing carelessly  will not result in the right answer either. So, think first, calculate, and always check your results. And remember, attitude matters. Approach solving a problem as something that you know you can do, rather than something you think that you can’t do. Very few of us can see the answer to a problem without working through various approaches first.

Analysis Stage

Read the problem carefully at least twice, aloud if possible, then restate the problem in your own words.
Write down all the information that you know in the problem and separate, if necessary, the “givens” from the “constraints.”
Think about what can be done with the information that is given. What are some relationships within the information given? What does this particular problem have in common conceptually with course material or other questions that you have solved?
Draw pictures or graphs to help you sort through what’s really going on in the problem. These will help you recall related course material that will help you solve the problem. However, be sure to check that the assumptions underlying the picture or graph you have drawn are the same as the assumptions made in the problem. If they are not, you will need to take this into consideration when setting up your approach.

Computing Stage

If the actual numbers involved in the problem are too large, small, or abstract and seem to be getting in the way of your thinking, substitute simple numbers and plan your approach. Then, once you get an understanding of the concepts in the problem, you can go back to the numbers given.
Once you have a plan, do the necessary calculations. If you think of a simpler or more elegant approach, you can try it afterwards and use it as a check of your logic. Be careful about changing your approach in the middle of a problem. You can inadvertently include some incorrect or inapplicable assumptions from the prior plan.
Throughout the computing stage, pause periodically to be sure that you understand the intuition behind each concept in the problem. Doing this will not only strengthen your understanding of the material, but it will also help you in solving other problems that also focus on those concepts.
Resist the temptation to consult the answer key before you have finished the problem. Problems often look logical when someone else does them; that recognition does not require the same knowledge as solving the problem yourself. Likewise, when soliciting help from the AI or course head, ask for direction or a helpful tip only—avoid having them work the problem for you. This approach will help ensure that you really understand the problem—an essential prerequisite for successfully solving problems on exams and quizzes where no outside help is available.
Check your results. Does the answer make sense given the information you have and the concepts involved? Does the answer make sense in the real world? Are the units reasonable? Are the units the ones specified in the problem? If you substitute your answer for the unknown in the problem, does it fit the criteria given? Does your answer fit within the range of an estimate that you made prior to calculating the result? One especially effective way to check your results is to work with a study partner or group. Discussing various options for a problem can help you uncover both computational errors and errors in your thinking about the problem. Before doing this, of course, make sure that working with someone else is acceptable to your course instructor.
Ask yourself why this question is important. Lectures, precepts, problem sets, and exams are all intended to increase your knowledge of the subject. Thinking about the connection between a problem and the rest of the course material will strengthen your overall understanding.

If you get stuck, take a break. Research has shown that the brain works very productively on problems while we sleep—so plan your problem-solving sessions in such a way that you do a “first pass.” Then, get a night’s rest, return to the problem set the next day, and think about approaching the problem in an entirely different way.

References and Further Reading:

Adapted in part from Walter Pauk. How to Study in College , 7th edition, Houghton Mifflin Co., 2001

← Questions to Ask Yourself When Problem Solving
Breaking Down Large Projects Into Manageable Pieces →

Linear Programming using Pyomo
Networking and Professional Development for Machine Learning Careers in the USA
Predicting Employee Churn in Python
Airflow Operators
MLOps Tutorial

Solving Assignment Problem using Linear Programming in Python

Learn how to use Python PuLP to solve Assignment problems using Linear Programming.

In earlier articles, we have seen various applications of Linear programming such as transportation, transshipment problem, Cargo Loading problem, and shift-scheduling problem. Now In this tutorial, we will focus on another model that comes under the class of linear programming model known as the Assignment problem. Its objective function is similar to transportation problems. Here we minimize the objective function time or cost of manufacturing the products by allocating one job to one machine.

If we want to solve the maximization problem assignment problem then we subtract all the elements of the matrix from the highest element in the matrix or multiply the entire matrix by –1 and continue with the procedure. For solving the assignment problem, we use the Assignment technique or Hungarian method, or Flood’s technique.

The transportation problem is a special case of the linear programming model and the assignment problem is a special case of transportation problem, therefore it is also a special case of the linear programming problem.

In this tutorial, we are going to cover the following topics:

Assignment Problem

A problem that requires pairing two sets of items given a set of paired costs or profit in such a way that the total cost of the pairings is minimized or maximized. The assignment problem is a special case of linear programming.

For example, an operation manager needs to assign four jobs to four machines. The project manager needs to assign four projects to four staff members. Similarly, the marketing manager needs to assign the 4 salespersons to 4 territories. The manager’s goal is to minimize the total time or cost.

Problem Formulation

A manager has prepared a table that shows the cost of performing each of four jobs by each of four employees. The manager has stated his goal is to develop a set of job assignments that will minimize the total cost of getting all 4 jobs.

Initialize LP Model

In this step, we will import all the classes and functions of pulp module and create a Minimization LP problem using LpProblem class.

Define Decision Variable

In this step, we will define the decision variables. In our problem, we have two variable lists: workers and jobs. Let’s create them using LpVariable.dicts() class. LpVariable.dicts() used with Python’s list comprehension. LpVariable.dicts() will take the following four values:

First, prefix name of what this variable represents.
Second is the list of all the variables.
Third is the lower bound on this variable.
Fourth variable is the upper bound.
Fourth is essentially the type of data (discrete or continuous). The options for the fourth parameter are LpContinuous or LpInteger .

Let’s first create a list route for the route between warehouse and project site and create the decision variables using LpVariable.dicts() the method.

Define Objective Function

In this step, we will define the minimum objective function by adding it to the LpProblem object. lpSum(vector)is used here to define multiple linear expressions. It also used list comprehension to add multiple variables.

Define the Constraints

Here, we are adding two types of constraints: Each job can be assigned to only one employee constraint and Each employee can be assigned to only one job. We have added the 2 constraints defined in the problem by adding them to the LpProblem object.

Solve Model

In this step, we will solve the LP problem by calling solve() method. We can print the final value by using the following for loop.

From the above results, we can infer that Worker-1 will be assigned to Job-1, Worker-2 will be assigned to job-3, Worker-3 will be assigned to Job-2, and Worker-4 will assign with job-4.

In this article, we have learned about Assignment problems, Problem Formulation, and implementation using the python PuLp library. We have solved the Assignment problem using a Linear programming problem in Python. Of course, this is just a simple case study, we can add more constraints to it and make it more complicated. You can also run other case studies on Cargo Loading problems , Staff scheduling problems . In upcoming articles, we will write more on different optimization problems such as transshipment problem, balanced diet problem. You can revise the basics of mathematical concepts in this article and learn about Linear Programming in this article .

Solving Blending Problem in Python using Gurobi
Transshipment Problem in Python Using PuLP

Pandas DataFrame

Handling Missing Values in Pandas

Agglomerative Clustering

404 Not found

35 problem-solving techniques and methods for solving complex problems

Design your next session with SessionLab

Join the 150,000+ facilitators  using SessionLab.

How do you identify problems?

How do you identify the right solution.

Tips for more effective problem-solving

Complete problem-solving methods

Problem-solving techniques to identify and analyze problems
Problem-solving techniques for developing solutions

Problem-solving warm-up activities

Closing activities for a problem-solving process.

Before you can move towards finding the right solution for a given problem, you first need to identify and define the problem you wish to solve.

Here, you want to clearly articulate what the problem is and allow your group to do the same. Remember that everyone in a group is likely to have differing perspectives and alignment is necessary in order to help the group move forward.

Identifying a problem accurately also requires that all members of a group are able to contribute their views in an open and safe manner. It can be scary for people to stand up and contribute, especially if the problems or challenges are emotive or personal in nature. Be sure to try and create a psychologically safe space for these kinds of discussions.

Remember that problem analysis and further discussion are also important. Not taking the time to fully analyze and discuss a challenge can result in the development of solutions that are not fit for purpose or do not address the underlying issue.

Successfully identifying and then analyzing a problem means facilitating a group through activities designed to help them clearly and honestly articulate their thoughts and produce usable insight.

With this data, you might then produce a problem statement that clearly describes the problem you wish to be addressed and also state the goal of any process you undertake to tackle this issue.

Finding solutions is the end goal of any process. Complex organizational challenges can only be solved with an appropriate solution but discovering them requires using the right problem-solving tool.

After you’ve explored a problem and discussed ideas, you need to help a team discuss and choose the right solution. Consensus tools and methods such as those below help a group explore possible solutions before then voting for the best. They’re a great way to tap into the collective intelligence of the group for great results!

Remember that the process is often iterative. Great problem solvers often roadtest a viable solution in a measured way to see what works too. While you might not get the right solution on your first try, the methods below help teams land on the most likely to succeed solution while also holding space for improvement.

Every effective problem solving process begins with an agenda . A well-structured workshop is one of the best methods for successfully guiding a group from exploring a problem to implementing a solution.

In SessionLab, it’s easy to go from an idea to a complete agenda . Start by dragging and dropping your core problem solving activities into place . Add timings, breaks and necessary materials before sharing your agenda with your colleagues.

The resulting agenda will be your guide to an effective and productive problem solving session that will also help you stay organized on the day!

Tips for more effective problem solving

Problem-solving activities are only one part of the puzzle. While a great method can help unlock your team’s ability to solve problems, without a thoughtful approach and strong facilitation the solutions may not be fit for purpose.

Let’s take a look at some problem-solving tips you can apply to any process to help it be a success!

Clearly define the problem

Jumping straight to solutions can be tempting, though without first clearly articulating a problem, the solution might not be the right one. Many of the problem-solving activities below include sections where the problem is explored and clearly defined before moving on.

This is a vital part of the problem-solving process and taking the time to fully define an issue can save time and effort later. A clear definition helps identify irrelevant information and it also ensures that your team sets off on the right track.

Don’t jump to conclusions

It’s easy for groups to exhibit cognitive bias or have preconceived ideas about both problems and potential solutions. Be sure to back up any problem statements or potential solutions with facts, research, and adequate forethought.

The best techniques ask participants to be methodical and challenge preconceived notions. Make sure you give the group enough time and space to collect relevant information and consider the problem in a new way. By approaching the process with a clear, rational mindset, you’ll often find that better solutions are more forthcoming.

Try different approaches

Problems come in all shapes and sizes and so too should the methods you use to solve them. If you find that one approach isn’t yielding results and your team isn’t finding different solutions, try mixing it up. You’ll be surprised at how using a new creative activity can unblock your team and generate great solutions.

Don’t take it personally

Depending on the nature of your team or organizational problems, it’s easy for conversations to get heated. While it’s good for participants to be engaged in the discussions, ensure that emotions don’t run too high and that blame isn’t thrown around while finding solutions.

You’re all in it together, and even if your team or area is seeing problems, that isn’t necessarily a disparagement of you personally. Using facilitation skills to manage group dynamics is one effective method of helping conversations be more constructive.

Get the right people in the room

Your problem-solving method is often only as effective as the group using it. Getting the right people on the job and managing the number of people present is important too!

If the group is too small, you may not get enough different perspectives to effectively solve a problem. If the group is too large, you can go round and round during the ideation stages.

Creating the right group makeup is also important in ensuring you have the necessary expertise and skillset to both identify and follow up on potential solutions. Carefully consider who to include at each stage to help ensure your problem-solving method is followed and positioned for success.

Document everything

The best solutions can take refinement, iteration, and reflection to come out. Get into a habit of documenting your process in order to keep all the learnings from the session and to allow ideas to mature and develop. Many of the methods below involve the creation of documents or shared resources. Be sure to keep and share these so everyone can benefit from the work done!

Bring a facilitator

Facilitation is all about making group processes easier. With a subject as potentially emotive and important as problem-solving, having an impartial third party in the form of a facilitator can make all the difference in finding great solutions and keeping the process moving. Consider bringing a facilitator to your problem-solving session to get better results and generate meaningful solutions!

Develop your problem-solving skills

It takes time and practice to be an effective problem solver. While some roles or participants might more naturally gravitate towards problem-solving, it can take development and planning to help everyone create better solutions.

You might develop a training program, run a problem-solving workshop or simply ask your team to practice using the techniques below. Check out our post on problem-solving skills to see how you and your group can develop the right mental process and be more resilient to issues too!

Design a great agenda

Workshops are a great format for solving problems. With the right approach, you can focus a group and help them find the solutions to their own problems. But designing a process can be time-consuming and finding the right activities can be difficult.

Check out our workshop planning guide to level-up your agenda design and start running more effective workshops. Need inspiration? Check out templates designed by expert facilitators to help you kickstart your process!

In this section, we’ll look at in-depth problem-solving methods that provide a complete end-to-end process for developing effective solutions. These will help guide your team from the discovery and definition of a problem through to delivering the right solution.

If you’re looking for an all-encompassing method or problem-solving model, these processes are a great place to start. They’ll ask your team to challenge preconceived ideas and adopt a mindset for solving problems more effectively.

Six Thinking Hats
Lightning Decision Jam
Problem Definition Process
Discovery & Action Dialogue

Design Sprint 2.0

Open Space Technology

1. Six Thinking Hats

Individual approaches to solving a problem can be very different based on what team or role an individual holds. It can be easy for existing biases or perspectives to find their way into the mix, or for internal politics to direct a conversation.

Six Thinking Hats is a classic method for identifying the problems that need to be solved and enables your team to consider them from different angles, whether that is by focusing on facts and data, creative solutions, or by considering why a particular solution might not work.

Like all problem-solving frameworks, Six Thinking Hats is effective at helping teams remove roadblocks from a conversation or discussion and come to terms with all the aspects necessary to solve complex problems.

2. Lightning Decision Jam

Featured courtesy of Jonathan Courtney of AJ&Smart Berlin, Lightning Decision Jam is one of those strategies that should be in every facilitation toolbox. Exploring problems and finding solutions is often creative in nature, though as with any creative process, there is the potential to lose focus and get lost.

Unstructured discussions might get you there in the end, but it’s much more effective to use a method that creates a clear process and team focus.

In Lightning Decision Jam, participants are invited to begin by writing challenges, concerns, or mistakes on post-its without discussing them before then being invited by the moderator to present them to the group.

From there, the team vote on which problems to solve and are guided through steps that will allow them to reframe those problems, create solutions and then decide what to execute on.

By deciding the problems that need to be solved as a team before moving on, this group process is great for ensuring the whole team is aligned and can take ownership over the next stages.

Lightning Decision Jam (LDJ) #action #decision making #problem solving #issue analysis #innovation #design #remote-friendly The problem with anything that requires creative thinking is that it’s easy to get lost—lose focus and fall into the trap of having useless, open-ended, unstructured discussions. Here’s the most effective solution I’ve found: Replace all open, unstructured discussion with a clear process. What to use this exercise for: Anything which requires a group of people to make decisions, solve problems or discuss challenges. It’s always good to frame an LDJ session with a broad topic, here are some examples: The conversion flow of our checkout Our internal design process How we organise events Keeping up with our competition Improving sales flow

3. Problem Definition Process

While problems can be complex, the problem-solving methods you use to identify and solve those problems can often be simple in design.

By taking the time to truly identify and define a problem before asking the group to reframe the challenge as an opportunity, this method is a great way to enable change.

Begin by identifying a focus question and exploring the ways in which it manifests before splitting into five teams who will each consider the problem using a different method: escape, reversal, exaggeration, distortion or wishful. Teams develop a problem objective and create ideas in line with their method before then feeding them back to the group.

This method is great for enabling in-depth discussions while also creating space for finding creative solutions too!

Problem Definition #problem solving #idea generation #creativity #online #remote-friendly A problem solving technique to define a problem, challenge or opportunity and to generate ideas.

4. The 5 Whys

Sometimes, a group needs to go further with their strategies and analyze the root cause at the heart of organizational issues. An RCA or root cause analysis is the process of identifying what is at the heart of business problems or recurring challenges.

The 5 Whys is a simple and effective method of helping a group go find the root cause of any problem or challenge and conduct analysis that will deliver results.

By beginning with the creation of a problem statement and going through five stages to refine it, The 5 Whys provides everything you need to truly discover the cause of an issue.

The 5 Whys #hyperisland #innovation This simple and powerful method is useful for getting to the core of a problem or challenge. As the title suggests, the group defines a problems, then asks the question “why” five times, often using the resulting explanation as a starting point for creative problem solving.

5. World Cafe

World Cafe is a simple but powerful facilitation technique to help bigger groups to focus their energy and attention on solving complex problems.

World Cafe enables this approach by creating a relaxed atmosphere where participants are able to self-organize and explore topics relevant and important to them which are themed around a central problem-solving purpose. Create the right atmosphere by modeling your space after a cafe and after guiding the group through the method, let them take the lead!

Making problem-solving a part of your organization’s culture in the long term can be a difficult undertaking. More approachable formats like World Cafe can be especially effective in bringing people unfamiliar with workshops into the fold.

World Cafe #hyperisland #innovation #issue analysis World Café is a simple yet powerful method, originated by Juanita Brown, for enabling meaningful conversations driven completely by participants and the topics that are relevant and important to them. Facilitators create a cafe-style space and provide simple guidelines. Participants then self-organize and explore a set of relevant topics or questions for conversation.

6. Discovery & Action Dialogue (DAD)

One of the best approaches is to create a safe space for a group to share and discover practices and behaviors that can help them find their own solutions.

With DAD, you can help a group choose which problems they wish to solve and which approaches they will take to do so. It’s great at helping remove resistance to change and can help get buy-in at every level too!

This process of enabling frontline ownership is great in ensuring follow-through and is one of the methods you will want in your toolbox as a facilitator.

Discovery & Action Dialogue (DAD) #idea generation #liberating structures #action #issue analysis #remote-friendly DADs make it easy for a group or community to discover practices and behaviors that enable some individuals (without access to special resources and facing the same constraints) to find better solutions than their peers to common problems. These are called positive deviant (PD) behaviors and practices. DADs make it possible for people in the group, unit, or community to discover by themselves these PD practices. DADs also create favorable conditions for stimulating participants’ creativity in spaces where they can feel safe to invent new and more effective practices. Resistance to change evaporates as participants are unleashed to choose freely which practices they will adopt or try and which problems they will tackle. DADs make it possible to achieve frontline ownership of solutions.

7. Design Sprint 2.0

Want to see how a team can solve big problems and move forward with prototyping and testing solutions in a few days? The Design Sprint 2.0 template from Jake Knapp, author of Sprint, is a complete agenda for a with proven results.

Developing the right agenda can involve difficult but necessary planning. Ensuring all the correct steps are followed can also be stressful or time-consuming depending on your level of experience.

Use this complete 4-day workshop template if you are finding there is no obvious solution to your challenge and want to focus your team around a specific problem that might require a shortcut to launching a minimum viable product or waiting for the organization-wide implementation of a solution.

8. Open space technology

Open space technology- developed by Harrison Owen – creates a space where large groups are invited to take ownership of their problem solving and lead individual sessions. Open space technology is a great format when you have a great deal of expertise and insight in the room and want to allow for different takes and approaches on a particular theme or problem you need to be solved.

Start by bringing your participants together to align around a central theme and focus their efforts. Explain the ground rules to help guide the problem-solving process and then invite members to identify any issue connecting to the central theme that they are interested in and are prepared to take responsibility for.

Once participants have decided on their approach to the core theme, they write their issue on a piece of paper, announce it to the group, pick a session time and place, and post the paper on the wall. As the wall fills up with sessions, the group is then invited to join the sessions that interest them the most and which they can contribute to, then you’re ready to begin!

Everyone joins the problem-solving group they’ve signed up to, record the discussion and if appropriate, findings can then be shared with the rest of the group afterward.

Open Space Technology #action plan #idea generation #problem solving #issue analysis #large group #online #remote-friendly Open Space is a methodology for large groups to create their agenda discerning important topics for discussion, suitable for conferences, community gatherings and whole system facilitation

Techniques to identify and analyze problems

Using a problem-solving method to help a team identify and analyze a problem can be a quick and effective addition to any workshop or meeting.

While further actions are always necessary, you can generate momentum and alignment easily, and these activities are a great place to get started.

We’ve put together this list of techniques to help you and your team with problem identification, analysis, and discussion that sets the foundation for developing effective solutions.

Let’s take a look!

The Creativity Dice
Fishbone Analysis
Problem Tree
SWOT Analysis
Agreement-Certainty Matrix
The Journalistic Six
LEGO Challenge
What, So What, Now What?
Journalists

Individual and group perspectives are incredibly important, but what happens if people are set in their minds and need a change of perspective in order to approach a problem more effectively?

Flip It is a method we love because it is both simple to understand and run, and allows groups to understand how their perspectives and biases are formed.

Participants in Flip It are first invited to consider concerns, issues, or problems from a perspective of fear and write them on a flip chart. Then, the group is asked to consider those same issues from a perspective of hope and flip their understanding.

No problem and solution is free from existing bias and by changing perspectives with Flip It, you can then develop a problem solving model quickly and effectively.

Flip It! #gamestorming #problem solving #action Often, a change in a problem or situation comes simply from a change in our perspectives. Flip It! is a quick game designed to show players that perspectives are made, not born.

10. The Creativity Dice

One of the most useful problem solving skills you can teach your team is of approaching challenges with creativity, flexibility, and openness. Games like The Creativity Dice allow teams to overcome the potential hurdle of too much linear thinking and approach the process with a sense of fun and speed.

In The Creativity Dice, participants are organized around a topic and roll a dice to determine what they will work on for a period of 3 minutes at a time. They might roll a 3 and work on investigating factual information on the chosen topic. They might roll a 1 and work on identifying the specific goals, standards, or criteria for the session.

Encouraging rapid work and iteration while asking participants to be flexible are great skills to cultivate. Having a stage for idea incubation in this game is also important. Moments of pause can help ensure the ideas that are put forward are the most suitable.

The Creativity Dice #creativity #problem solving #thiagi #issue analysis Too much linear thinking is hazardous to creative problem solving. To be creative, you should approach the problem (or the opportunity) from different points of view. You should leave a thought hanging in mid-air and move to another. This skipping around prevents premature closure and lets your brain incubate one line of thought while you consciously pursue another.

11. Fishbone Analysis

Organizational or team challenges are rarely simple, and it’s important to remember that one problem can be an indication of something that goes deeper and may require further consideration to be solved.

Fishbone Analysis helps groups to dig deeper and understand the origins of a problem. It’s a great example of a root cause analysis method that is simple for everyone on a team to get their head around.

Participants in this activity are asked to annotate a diagram of a fish, first adding the problem or issue to be worked on at the head of a fish before then brainstorming the root causes of the problem and adding them as bones on the fish.

Using abstractions such as a diagram of a fish can really help a team break out of their regular thinking and develop a creative approach.

Fishbone Analysis #problem solving ##root cause analysis #decision making #online facilitation A process to help identify and understand the origins of problems, issues or observations.

12. Problem Tree

Encouraging visual thinking can be an essential part of many strategies. By simply reframing and clarifying problems, a group can move towards developing a problem solving model that works for them.

In Problem Tree, groups are asked to first brainstorm a list of problems – these can be design problems, team problems or larger business problems – and then organize them into a hierarchy. The hierarchy could be from most important to least important or abstract to practical, though the key thing with problem solving games that involve this aspect is that your group has some way of managing and sorting all the issues that are raised.

Once you have a list of problems that need to be solved and have organized them accordingly, you’re then well-positioned for the next problem solving steps.

Problem tree #define intentions #create #design #issue analysis A problem tree is a tool to clarify the hierarchy of problems addressed by the team within a design project; it represents high level problems or related sublevel problems.

13. SWOT Analysis

Chances are you’ve heard of the SWOT Analysis before. This problem-solving method focuses on identifying strengths, weaknesses, opportunities, and threats is a tried and tested method for both individuals and teams.

Start by creating a desired end state or outcome and bare this in mind – any process solving model is made more effective by knowing what you are moving towards. Create a quadrant made up of the four categories of a SWOT analysis and ask participants to generate ideas based on each of those quadrants.

Once you have those ideas assembled in their quadrants, cluster them together based on their affinity with other ideas. These clusters are then used to facilitate group conversations and move things forward.

SWOT analysis #gamestorming #problem solving #action #meeting facilitation The SWOT Analysis is a long-standing technique of looking at what we have, with respect to the desired end state, as well as what we could improve on. It gives us an opportunity to gauge approaching opportunities and dangers, and assess the seriousness of the conditions that affect our future. When we understand those conditions, we can influence what comes next.

14. Agreement-Certainty Matrix

Not every problem-solving approach is right for every challenge, and deciding on the right method for the challenge at hand is a key part of being an effective team.

The Agreement Certainty matrix helps teams align on the nature of the challenges facing them. By sorting problems from simple to chaotic, your team can understand what methods are suitable for each problem and what they can do to ensure effective results.

If you are already using Liberating Structures techniques as part of your problem-solving strategy, the Agreement-Certainty Matrix can be an invaluable addition to your process. We’ve found it particularly if you are having issues with recurring problems in your organization and want to go deeper in understanding the root cause.

Agreement-Certainty Matrix #issue analysis #liberating structures #problem solving You can help individuals or groups avoid the frequent mistake of trying to solve a problem with methods that are not adapted to the nature of their challenge. The combination of two questions makes it possible to easily sort challenges into four categories: simple, complicated, complex , and chaotic . A problem is simple when it can be solved reliably with practices that are easy to duplicate. It is complicated when experts are required to devise a sophisticated solution that will yield the desired results predictably. A problem is complex when there are several valid ways to proceed but outcomes are not predictable in detail. Chaotic is when the context is too turbulent to identify a path forward. A loose analogy may be used to describe these differences: simple is like following a recipe, complicated like sending a rocket to the moon, complex like raising a child, and chaotic is like the game “Pin the Tail on the Donkey.” The Liberating Structures Matching Matrix in Chapter 5 can be used as the first step to clarify the nature of a challenge and avoid the mismatches between problems and solutions that are frequently at the root of chronic, recurring problems.

Organizing and charting a team’s progress can be important in ensuring its success. SQUID (Sequential Question and Insight Diagram) is a great model that allows a team to effectively switch between giving questions and answers and develop the skills they need to stay on track throughout the process.

Begin with two different colored sticky notes – one for questions and one for answers – and with your central topic (the head of the squid) on the board. Ask the group to first come up with a series of questions connected to their best guess of how to approach the topic. Ask the group to come up with answers to those questions, fix them to the board and connect them with a line. After some discussion, go back to question mode by responding to the generated answers or other points on the board.

It’s rewarding to see a diagram grow throughout the exercise, and a completed SQUID can provide a visual resource for future effort and as an example for other teams.

SQUID #gamestorming #project planning #issue analysis #problem solving When exploring an information space, it’s important for a group to know where they are at any given time. By using SQUID, a group charts out the territory as they go and can navigate accordingly. SQUID stands for Sequential Question and Insight Diagram.

16. Speed Boat

To continue with our nautical theme, Speed Boat is a short and sweet activity that can help a team quickly identify what employees, clients or service users might have a problem with and analyze what might be standing in the way of achieving a solution.

Methods that allow for a group to make observations, have insights and obtain those eureka moments quickly are invaluable when trying to solve complex problems.

In Speed Boat, the approach is to first consider what anchors and challenges might be holding an organization (or boat) back. Bonus points if you are able to identify any sharks in the water and develop ideas that can also deal with competitors!

Speed Boat #gamestorming #problem solving #action Speedboat is a short and sweet way to identify what your employees or clients don’t like about your product/service or what’s standing in the way of a desired goal.

17. The Journalistic Six

Some of the most effective ways of solving problems is by encouraging teams to be more inclusive and diverse in their thinking.

Based on the six key questions journalism students are taught to answer in articles and news stories, The Journalistic Six helps create teams to see the whole picture. By using who, what, when, where, why, and how to facilitate the conversation and encourage creative thinking, your team can make sure that the problem identification and problem analysis stages of the are covered exhaustively and thoughtfully. Reporter’s notebook and dictaphone optional.

The Journalistic Six – Who What When Where Why How #idea generation #issue analysis #problem solving #online #creative thinking #remote-friendly A questioning method for generating, explaining, investigating ideas.

18. LEGO Challenge

Now for an activity that is a little out of the (toy) box. LEGO Serious Play is a facilitation methodology that can be used to improve creative thinking and problem-solving skills.

The LEGO Challenge includes giving each member of the team an assignment that is hidden from the rest of the group while they create a structure without speaking.

What the LEGO challenge brings to the table is a fun working example of working with stakeholders who might not be on the same page to solve problems. Also, it’s LEGO! Who doesn’t love LEGO!

LEGO Challenge #hyperisland #team A team-building activity in which groups must work together to build a structure out of LEGO, but each individual has a secret “assignment” which makes the collaborative process more challenging. It emphasizes group communication, leadership dynamics, conflict, cooperation, patience and problem solving strategy.

19. What, So What, Now What?

If not carefully managed, the problem identification and problem analysis stages of the problem-solving process can actually create more problems and misunderstandings.

The What, So What, Now What? problem-solving activity is designed to help collect insights and move forward while also eliminating the possibility of disagreement when it comes to identifying, clarifying, and analyzing organizational or work problems.

Facilitation is all about bringing groups together so that might work on a shared goal and the best problem-solving strategies ensure that teams are aligned in purpose, if not initially in opinion or insight.

Throughout the three steps of this game, you give everyone on a team to reflect on a problem by asking what happened, why it is important, and what actions should then be taken.

This can be a great activity for bringing our individual perceptions about a problem or challenge and contextualizing it in a larger group setting. This is one of the most important problem-solving skills you can bring to your organization.

W³ – What, So What, Now What? #issue analysis #innovation #liberating structures You can help groups reflect on a shared experience in a way that builds understanding and spurs coordinated action while avoiding unproductive conflict. It is possible for every voice to be heard while simultaneously sifting for insights and shaping new direction. Progressing in stages makes this practical—from collecting facts about What Happened to making sense of these facts with So What and finally to what actions logically follow with Now What . The shared progression eliminates most of the misunderstandings that otherwise fuel disagreements about what to do. Voila!

20. Journalists

Problem analysis can be one of the most important and decisive stages of all problem-solving tools. Sometimes, a team can become bogged down in the details and are unable to move forward.

Journalists is an activity that can avoid a group from getting stuck in the problem identification or problem analysis stages of the process.

In Journalists, the group is invited to draft the front page of a fictional newspaper and figure out what stories deserve to be on the cover and what headlines those stories will have. By reframing how your problems and challenges are approached, you can help a team move productively through the process and be better prepared for the steps to follow.

Journalists #vision #big picture #issue analysis #remote-friendly This is an exercise to use when the group gets stuck in details and struggles to see the big picture. Also good for defining a vision.

Problem-solving techniques for developing solutions

The success of any problem-solving process can be measured by the solutions it produces. After you’ve defined the issue, explored existing ideas, and ideated, it’s time to narrow down to the correct solution.

Use these problem-solving techniques when you want to help your team find consensus, compare possible solutions, and move towards taking action on a particular problem.

Improved Solutions
Four-Step Sketch
15% Solutions
How-Now-Wow matrix
Impact Effort Matrix

21. Mindspin

Brainstorming is part of the bread and butter of the problem-solving process and all problem-solving strategies benefit from getting ideas out and challenging a team to generate solutions quickly.

With Mindspin, participants are encouraged not only to generate ideas but to do so under time constraints and by slamming down cards and passing them on. By doing multiple rounds, your team can begin with a free generation of possible solutions before moving on to developing those solutions and encouraging further ideation.

This is one of our favorite problem-solving activities and can be great for keeping the energy up throughout the workshop. Remember the importance of helping people become engaged in the process – energizing problem-solving techniques like Mindspin can help ensure your team stays engaged and happy, even when the problems they’re coming together to solve are complex.

MindSpin #teampedia #idea generation #problem solving #action A fast and loud method to enhance brainstorming within a team. Since this activity has more than round ideas that are repetitive can be ruled out leaving more creative and innovative answers to the challenge.

22. Improved Solutions

After a team has successfully identified a problem and come up with a few solutions, it can be tempting to call the work of the problem-solving process complete. That said, the first solution is not necessarily the best, and by including a further review and reflection activity into your problem-solving model, you can ensure your group reaches the best possible result.

One of a number of problem-solving games from Thiagi Group, Improved Solutions helps you go the extra mile and develop suggested solutions with close consideration and peer review. By supporting the discussion of several problems at once and by shifting team roles throughout, this problem-solving technique is a dynamic way of finding the best solution.

Improved Solutions #creativity #thiagi #problem solving #action #team You can improve any solution by objectively reviewing its strengths and weaknesses and making suitable adjustments. In this creativity framegame, you improve the solutions to several problems. To maintain objective detachment, you deal with a different problem during each of six rounds and assume different roles (problem owner, consultant, basher, booster, enhancer, and evaluator) during each round. At the conclusion of the activity, each player ends up with two solutions to her problem.

23. Four Step Sketch

Creative thinking and visual ideation does not need to be confined to the opening stages of your problem-solving strategies. Exercises that include sketching and prototyping on paper can be effective at the solution finding and development stage of the process, and can be great for keeping a team engaged.

By going from simple notes to a crazy 8s round that involves rapidly sketching 8 variations on their ideas before then producing a final solution sketch, the group is able to iterate quickly and visually. Problem-solving techniques like Four-Step Sketch are great if you have a group of different thinkers and want to change things up from a more textual or discussion-based approach.

Four-Step Sketch #design sprint #innovation #idea generation #remote-friendly The four-step sketch is an exercise that helps people to create well-formed concepts through a structured process that includes: Review key information Start design work on paper, Consider multiple variations , Create a detailed solution . This exercise is preceded by a set of other activities allowing the group to clarify the challenge they want to solve. See how the Four Step Sketch exercise fits into a Design Sprint

24. 15% Solutions

Some problems are simpler than others and with the right problem-solving activities, you can empower people to take immediate actions that can help create organizational change.

Part of the liberating structures toolkit, 15% solutions is a problem-solving technique that focuses on finding and implementing solutions quickly. A process of iterating and making small changes quickly can help generate momentum and an appetite for solving complex problems.

Problem-solving strategies can live and die on whether people are onboard. Getting some quick wins is a great way of getting people behind the process.

It can be extremely empowering for a team to realize that problem-solving techniques can be deployed quickly and easily and delineate between things they can positively impact and those things they cannot change.

15% Solutions #action #liberating structures #remote-friendly You can reveal the actions, however small, that everyone can do immediately. At a minimum, these will create momentum, and that may make a BIG difference. 15% Solutions show that there is no reason to wait around, feel powerless, or fearful. They help people pick it up a level. They get individuals and the group to focus on what is within their discretion instead of what they cannot change. With a very simple question, you can flip the conversation to what can be done and find solutions to big problems that are often distributed widely in places not known in advance. Shifting a few grains of sand may trigger a landslide and change the whole landscape.

25. How-Now-Wow Matrix

The problem-solving process is often creative, as complex problems usually require a change of thinking and creative response in order to find the best solutions. While it’s common for the first stages to encourage creative thinking, groups can often gravitate to familiar solutions when it comes to the end of the process.

When selecting solutions, you don’t want to lose your creative energy! The How-Now-Wow Matrix from Gamestorming is a great problem-solving activity that enables a group to stay creative and think out of the box when it comes to selecting the right solution for a given problem.

Problem-solving techniques that encourage creative thinking and the ideation and selection of new solutions can be the most effective in organisational change. Give the How-Now-Wow Matrix a go, and not just for how pleasant it is to say out loud.

How-Now-Wow Matrix #gamestorming #idea generation #remote-friendly When people want to develop new ideas, they most often think out of the box in the brainstorming or divergent phase. However, when it comes to convergence, people often end up picking ideas that are most familiar to them. This is called a ‘creative paradox’ or a ‘creadox’. The How-Now-Wow matrix is an idea selection tool that breaks the creadox by forcing people to weigh each idea on 2 parameters.

26. Impact and Effort Matrix

All problem-solving techniques hope to not only find solutions to a given problem or challenge but to find the best solution. When it comes to finding a solution, groups are invited to put on their decision-making hats and really think about how a proposed idea would work in practice.

The Impact and Effort Matrix is one of the problem-solving techniques that fall into this camp, empowering participants to first generate ideas and then categorize them into a 2×2 matrix based on impact and effort.

Activities that invite critical thinking while remaining simple are invaluable. Use the Impact and Effort Matrix to move from ideation and towards evaluating potential solutions before then committing to them.

Impact and Effort Matrix #gamestorming #decision making #action #remote-friendly In this decision-making exercise, possible actions are mapped based on two factors: effort required to implement and potential impact. Categorizing ideas along these lines is a useful technique in decision making, as it obliges contributors to balance and evaluate suggested actions before committing to them.

27. Dotmocracy

If you’ve followed each of the problem-solving steps with your group successfully, you should move towards the end of your process with heaps of possible solutions developed with a specific problem in mind. But how do you help a group go from ideation to putting a solution into action?

Dotmocracy – or Dot Voting -is a tried and tested method of helping a team in the problem-solving process make decisions and put actions in place with a degree of oversight and consensus.

One of the problem-solving techniques that should be in every facilitator’s toolbox, Dot Voting is fast and effective and can help identify the most popular and best solutions and help bring a group to a decision effectively.

Dotmocracy #action #decision making #group prioritization #hyperisland #remote-friendly Dotmocracy is a simple method for group prioritization or decision-making. It is not an activity on its own, but a method to use in processes where prioritization or decision-making is the aim. The method supports a group to quickly see which options are most popular or relevant. The options or ideas are written on post-its and stuck up on a wall for the whole group to see. Each person votes for the options they think are the strongest, and that information is used to inform a decision.

All facilitators know that warm-ups and icebreakers are useful for any workshop or group process. Problem-solving workshops are no different.

Use these problem-solving techniques to warm up a group and prepare them for the rest of the process. Activating your group by tapping into some of the top problem-solving skills can be one of the best ways to see great outcomes from your session.

Check-in/Check-out
Doodling Together
Show and Tell
Constellations
Draw a Tree

28. Check-in / Check-out

Solid processes are planned from beginning to end, and the best facilitators know that setting the tone and establishing a safe, open environment can be integral to a successful problem-solving process.

Check-in / Check-out is a great way to begin and/or bookend a problem-solving workshop. Checking in to a session emphasizes that everyone will be seen, heard, and expected to contribute.

If you are running a series of meetings, setting a consistent pattern of checking in and checking out can really help your team get into a groove. We recommend this opening-closing activity for small to medium-sized groups though it can work with large groups if they’re disciplined!

Check-in / Check-out #team #opening #closing #hyperisland #remote-friendly Either checking-in or checking-out is a simple way for a team to open or close a process, symbolically and in a collaborative way. Checking-in/out invites each member in a group to be present, seen and heard, and to express a reflection or a feeling. Checking-in emphasizes presence, focus and group commitment; checking-out emphasizes reflection and symbolic closure.

29. Doodling Together

Thinking creatively and not being afraid to make suggestions are important problem-solving skills for any group or team, and warming up by encouraging these behaviors is a great way to start.

Doodling Together is one of our favorite creative ice breaker games – it’s quick, effective, and fun and can make all following problem-solving steps easier by encouraging a group to collaborate visually. By passing cards and adding additional items as they go, the workshop group gets into a groove of co-creation and idea development that is crucial to finding solutions to problems.

Doodling Together #collaboration #creativity #teamwork #fun #team #visual methods #energiser #icebreaker #remote-friendly Create wild, weird and often funny postcards together & establish a group’s creative confidence.

30. Show and Tell

You might remember some version of Show and Tell from being a kid in school and it’s a great problem-solving activity to kick off a session.

Asking participants to prepare a little something before a workshop by bringing an object for show and tell can help them warm up before the session has even begun! Games that include a physical object can also help encourage early engagement before moving onto more big-picture thinking.

By asking your participants to tell stories about why they chose to bring a particular item to the group, you can help teams see things from new perspectives and see both differences and similarities in the way they approach a topic. Great groundwork for approaching a problem-solving process as a team!

Show and Tell #gamestorming #action #opening #meeting facilitation Show and Tell taps into the power of metaphors to reveal players’ underlying assumptions and associations around a topic The aim of the game is to get a deeper understanding of stakeholders’ perspectives on anything—a new project, an organizational restructuring, a shift in the company’s vision or team dynamic.

31. Constellations

Who doesn’t love stars? Constellations is a great warm-up activity for any workshop as it gets people up off their feet, energized, and ready to engage in new ways with established topics. It’s also great for showing existing beliefs, biases, and patterns that can come into play as part of your session.

Using warm-up games that help build trust and connection while also allowing for non-verbal responses can be great for easing people into the problem-solving process and encouraging engagement from everyone in the group. Constellations is great in large spaces that allow for movement and is definitely a practical exercise to allow the group to see patterns that are otherwise invisible.

Constellations #trust #connection #opening #coaching #patterns #system Individuals express their response to a statement or idea by standing closer or further from a central object. Used with teams to reveal system, hidden patterns, perspectives.

32. Draw a Tree

Problem-solving games that help raise group awareness through a central, unifying metaphor can be effective ways to warm-up a group in any problem-solving model.

Draw a Tree is a simple warm-up activity you can use in any group and which can provide a quick jolt of energy. Start by asking your participants to draw a tree in just 45 seconds – they can choose whether it will be abstract or realistic.

Once the timer is up, ask the group how many people included the roots of the tree and use this as a means to discuss how we can ignore important parts of any system simply because they are not visible.

All problem-solving strategies are made more effective by thinking of problems critically and by exposing things that may not normally come to light. Warm-up games like Draw a Tree are great in that they quickly demonstrate some key problem-solving skills in an accessible and effective way.

Draw a Tree #thiagi #opening #perspectives #remote-friendly With this game you can raise awarness about being more mindful, and aware of the environment we live in.

Each step of the problem-solving workshop benefits from an intelligent deployment of activities, games, and techniques. Bringing your session to an effective close helps ensure that solutions are followed through on and that you also celebrate what has been achieved.

Here are some problem-solving activities you can use to effectively close a workshop or meeting and ensure the great work you’ve done can continue afterward.

One Breath Feedback
Who What When Matrix
Response Cards

How do I conclude a problem-solving process?

All good things must come to an end. With the bulk of the work done, it can be tempting to conclude your workshop swiftly and without a moment to debrief and align. This can be problematic in that it doesn’t allow your team to fully process the results or reflect on the process.

At the end of an effective session, your team will have gone through a process that, while productive, can be exhausting. It’s important to give your group a moment to take a breath, ensure that they are clear on future actions, and provide short feedback before leaving the space.

The primary purpose of any problem-solving method is to generate solutions and then implement them. Be sure to take the opportunity to ensure everyone is aligned and ready to effectively implement the solutions you produced in the workshop.

Remember that every process can be improved and by giving a short moment to collect feedback in the session, you can further refine your problem-solving methods and see further success in the future too.

33. One Breath Feedback

Maintaining attention and focus during the closing stages of a problem-solving workshop can be tricky and so being concise when giving feedback can be important. It’s easy to incur “death by feedback” should some team members go on for too long sharing their perspectives in a quick feedback round.

One Breath Feedback is a great closing activity for workshops. You give everyone an opportunity to provide feedback on what they’ve done but only in the space of a single breath. This keeps feedback short and to the point and means that everyone is encouraged to provide the most important piece of feedback to them.

One breath feedback #closing #feedback #action This is a feedback round in just one breath that excels in maintaining attention: each participants is able to speak during just one breath … for most people that’s around 20 to 25 seconds … unless of course you’ve been a deep sea diver in which case you’ll be able to do it for longer.

34. Who What When Matrix

Matrices feature as part of many effective problem-solving strategies and with good reason. They are easily recognizable, simple to use, and generate results.

The Who What When Matrix is a great tool to use when closing your problem-solving session by attributing a who, what and when to the actions and solutions you have decided upon. The resulting matrix is a simple, easy-to-follow way of ensuring your team can move forward.

Great solutions can’t be enacted without action and ownership. Your problem-solving process should include a stage for allocating tasks to individuals or teams and creating a realistic timeframe for those solutions to be implemented or checked out. Use this method to keep the solution implementation process clear and simple for all involved.

Who/What/When Matrix #gamestorming #action #project planning With Who/What/When matrix, you can connect people with clear actions they have defined and have committed to.

35. Response cards

Group discussion can comprise the bulk of most problem-solving activities and by the end of the process, you might find that your team is talked out!

Providing a means for your team to give feedback with short written notes can ensure everyone is head and can contribute without the need to stand up and talk. Depending on the needs of the group, giving an alternative can help ensure everyone can contribute to your problem-solving model in the way that makes the most sense for them.

Response Cards is a great way to close a workshop if you are looking for a gentle warm-down and want to get some swift discussion around some of the feedback that is raised.

Response Cards #debriefing #closing #structured sharing #questions and answers #thiagi #action It can be hard to involve everyone during a closing of a session. Some might stay in the background or get unheard because of louder participants. However, with the use of Response Cards, everyone will be involved in providing feedback or clarify questions at the end of a session.

Save time and effort discovering the right solutions

A structured problem solving process is a surefire way of solving tough problems, discovering creative solutions and driving organizational change. But how can you design for successful outcomes?

With SessionLab, it’s easy to design engaging workshops that deliver results. Drag, drop and reorder blocks to build your agenda. When you make changes or update your agenda, your session timing adjusts automatically , saving you time on manual adjustments.

Collaborating with stakeholders or clients? Share your agenda with a single click and collaborate in real-time. No more sending documents back and forth over email.

Explore how to use SessionLab to design effective problem solving workshops or watch this five minute video to see the planner in action!

Over to you

The problem-solving process can often be as complicated and multifaceted as the problems they are set-up to solve. With the right problem-solving techniques and a mix of creative exercises designed to guide discussion and generate purposeful ideas, we hope we’ve given you the tools to find the best solutions as simply and easily as possible.

Is there a problem-solving technique that you are missing here? Do you have a favorite activity or method you use when facilitating? Let us know in the comments below, we’d love to hear from you!

thank you very much for these excellent techniques

Certainly wonderful article, very detailed. Shared!

Design your next workshop with SessionLab

Join the 150,000 facilitators using SessionLab

Our Mission

3 Simple Strategies to Improve Students’ Problem-Solving Skills

These strategies are designed to make sure students have a good understanding of problems before attempting to solve them.

Research provides a striking revelation about problem solvers. The best problem solvers approach problems much differently than novices. For instance, one meta-study showed that when experts evaluate graphs , they tend to spend less time on tasks and answer choices and more time on evaluating the axes’ labels and the relationships of variables within the graphs. In other words, they spend more time up front making sense of the data before moving to addressing the task.

While slower in solving problems, experts use this additional up-front time to more efficiently and effectively solve the problem. In one study, researchers found that experts were much better at “information extraction” or pulling the information they needed to solve the problem later in the problem than novices. This was due to the fact that they started a problem-solving process by evaluating specific assumptions within problems, asking predictive questions, and then comparing and contrasting their predictions with results. For example, expert problem solvers look at the problem context and ask a number of questions:

What do we know about the context of the problem?
What assumptions are underlying the problem? What’s the story here?
What qualitative and quantitative information is pertinent?
What might the problem context be telling us? What questions arise from the information we are reading or reviewing?
What are important trends and patterns?

As such, expert problem solvers don’t jump to the presented problem or rush to solutions. They invest the time necessary to make sense of the problem.

Now, think about your own students: Do they immediately jump to the question, or do they take time to understand the problem context? Do they identify the relevant variables, look for patterns, and then focus on the specific tasks?

If your students are struggling to develop the habit of sense-making in a problem- solving context, this is a perfect time to incorporate a few short and sharp strategies to support them.

3 Ways to Improve Student Problem-Solving

1. Slow reveal graphs: The brilliant strategy crafted by K–8 math specialist Jenna Laib and her colleagues provides teachers with an opportunity to gradually display complex graphical information and build students’ questioning, sense-making, and evaluating predictions.

For instance, in one third-grade class, students are given a bar graph without any labels or identifying information except for bars emerging from a horizontal line on the bottom of the slide. Over time, students learn about the categories on the x -axis (types of animals) and the quantities specified on the y -axis (number of baby teeth).

The graphs and the topics range in complexity from studying the standard deviation of temperatures in Antarctica to the use of scatterplots to compare working hours across OECD (Organization for Economic Cooperation and Development) countries. The website offers a number of graphs on Google Slides and suggests questions that teachers may ask students. Furthermore, this site allows teachers to search by type of graph (e.g., scatterplot) or topic (e.g., social justice).

2. Three reads: The three-reads strategy tasks students with evaluating a word problem in three different ways . First, students encounter a problem without having access to the question—for instance, “There are 20 kangaroos on the grassland. Three hop away.” Students are expected to discuss the context of the problem without emphasizing the quantities. For instance, a student may say, “We know that there are a total amount of kangaroos, and the total shrinks because some kangaroos hop away.”

Next, students discuss the important quantities and what questions may be generated. Finally, students receive and address the actual problem. Here they can both evaluate how close their predicted questions were from the actual questions and solve the actual problem.

To get started, consider using the numberless word problems on educator Brian Bushart’s site . For those teaching high school, consider using your own textbook word problems for this activity. Simply create three slides to present to students that include context (e.g., on the first slide state, “A salesman sold twice as much pears in the afternoon as in the morning”). The second slide would include quantities (e.g., “He sold 360 kilograms of pears”), and the third slide would include the actual question (e.g., “How many kilograms did he sell in the morning and how many in the afternoon?”). One additional suggestion for teams to consider is to have students solve the questions they generated before revealing the actual question.

3. Three-Act Tasks: Originally created by Dan Meyer, three-act tasks follow the three acts of a story . The first act is typically called the “setup,” followed by the “confrontation” and then the “resolution.”

This storyline process can be used in mathematics in which students encounter a contextual problem (e.g., a pool is being filled with soda). Here students work to identify the important aspects of the problem. During the second act, students build knowledge and skill to solve the problem (e.g., they learn how to calculate the volume of particular spaces). Finally, students solve the problem and evaluate their answers (e.g., how close were their calculations to the actual specifications of the pool and the amount of liquid that filled it).

Often, teachers add a fourth act (i.e., “the sequel”), in which students encounter a similar problem but in a different context (e.g., they have to estimate the volume of a lava lamp). There are also a number of elementary examples that have been developed by math teachers including GFletchy , which offers pre-kindergarten to middle school activities including counting squares , peas in a pod , and shark bait .

Students need to learn how to slow down and think through a problem context. The aforementioned strategies are quick ways teachers can begin to support students in developing the habits needed to effectively and efficiently tackle complex problem-solving.

A Study on the Weapon–Target Assignment Problem Considering Heading Error

Original Paper
Open access
Published: 27 March 2024

Cite this article

You have full access to this open access article

Ji-Eun Kim 1 ,
Chang-Hun Lee 2 &
Mun Yong Yi ORCID: orcid.org/0000-0003-1784-8983 1

66 Accesses

Explore all metrics

The focus of this study is to investigate the assignment of weapons to multiple targets in a scenario, specifically when an air defense system is confronted with numerous targets, such as low-altitude rockets or groups of drones. The accuracy of weapons in destroying these targets depends heavily on the correct alignment of the launchers with the targets, which can be affected by errors in launcher orientation. Therefore, in solving weapon–target assignment (WTA) problems, it is crucial to account for the heading errors caused by the launcher’s orientation angle. To address this issue, the use of a rotation strategy to align the orientation angle with the target’s approach direction can significantly improve the probability of kill (PK) against the target. However, its unitary implementation has limitations, which may result in missed engagements if there is insufficient time to rotate to the desired orientation angle. Thus, as a remedy, we propose a new WTA method that combines rotation and rotation fix strategy, improving the weakness of losing the opportunity of engagement due to rotation time and heading errors. The efficacy of this approach is evaluated through numerical simulations.

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

Bi-objective dynamic weapon-target assignment problem with stability measure

Ahmet Silav, Esra Karasakal & Orhan Karasakal

Weapon-Target Assignment and Firing Scheduling for Rapid Engagement with Heterogeneous Interceptors

Hyeon-Woo Park & Han-Lim Choi

Avoid common mistakes on your manuscript.

1 Introduction

Over the past few decades, weapon–target assignment (WTA) has been considered a crucial procedure for providing autonomous decision support in air defense systems [ 1 , 2 ]. The WTA involves determining which interceptors to use and when to launch them to counter identified threats. The WTA problem has been proven to be NP-complete, according to references [ 3 , 4 ]. Consequently, many previous research efforts have focused on tackling the computational complexity of the general WTA problem. Various search methods have been developed over the last few decades, including Lagrangian relaxation [ 5 ], exact and heuristic approaches [ 6 , 7 ], and meta-heuristic algorithms like ant colony optimization [ 8 ], particle swarm optimization [ 9 ], genetic algorithm [ 10 , 11 ], permutation and tabu search [ 12 , 13 ], variable neighborhood search [ 14 ], harmony search [ 15 ], hybrid discrete gray wolf optimization [ 16 ], and greedy maximization algorithm [ 17 , 18 , 19 , 20 ].

The primary objective of WTA, as highlighted in the references [ 21 , 22 , 23 ], is to minimize the potential damage to friendly assets and increase the survivability of identified threat targets. The optimization model for the WTA problem focuses on a single goal, which is to minimize the survival probability of the targets. Moreover, there are additional objectives that can be considered, including optimizing resource usage, minimizing target flight duration, and refining the fire doctrine in defense site zones [ 24 , 25 ]. To address the multi-objective WTA problem, various methods are employed, such as rule-based heuristics, goal programming, and evolutionary algorithms [ 24 , 26 , 27 , 28 ].

There are two main categories of the WTA problem: static WTA (SWTA) and dynamic WTA (DWTA) [ 29 ]. The former, SWTA, assumes that time is not a factor, and therefore subsequent engagements are not taken into consideration. Moreover, it is typically assumed that all weapons have an equal probability of success when targeting each type of enemy. The latter, DWTA, on the other hand, takes into account the available time windows during which targets can be engaged. This approach, proposed by Leboucher et al. [ 30 ], involves calculating the time to impact for each target and identifying the earliest moment at which each weapon can intercept the target. Xin et al. [ 31 ] have proposed a model that allows for variable probabilities of success for each weapon against each target and across different time periods. Khosla [ 32 ] has formulated a mixed integer program to address some of the key considerations in the WTA problem, including the inclusion of additional time constraints such as reload time.

Recent research has highlighted the need for more realistic WTA engagement scenarios [ 30 , 33 , 34 , 35 ], leading to the development of new models that reflect the characteristics of both the interceptors and targets in specific scenarios [ 36 , 37 , 38 , 39 , 40 ]. Cho and Choi [ 18 ] have proposed a time-based WTA problem that considers the interceptor’s firing time in relation to the target’s incoming direction and provides a time-dependent reward for determining the interceptor and its firing time. Leboucher and colleagues [ 30 ] have proposed a two-step approach for solving dynamic WTA problems, where the selection of weapon types and specific weapons occurs in the first step, followed by the determination of a sequence of firing times in the second step. Uhm and Lee [ 41 ] have also proposed a two-step algorithm that uses a time-based probability of success, which is a convex function of the firing time. Bogdanowicz and colleagues [ 37 , 38 ] have developed a novel method for the WTA problem based on the assumption of a fixed probability of success for a given time of engagement. Guo and colleagues [ 39 ] and Na and Lee [ 40 ] have considered factors that can affect the probability of success in a realistic engagement scenario, such as the time-to-go, line-of-sight, and miss distance between the target and interceptor. By incorporating these factors into the problem formulation, the engagement performance of the WTA problem can be improved in a real environment.

In recent years, area targets, such as drone swarms and low-altitude rockets, have emerged as significant threats, leading to an increased demand for air defense systems to counter them [ 42 , 43 , 44 , 45 , 46 ]. Such air defense systems require a large number of interceptors during the engagement, each of which is typically developed using low-cost and small-sized components. Thus, these interceptors have lower maneuverability than other types of interceptors, which can lead to the varying probability of kill (PK) depending on the relative engagement geometry between the target and launcher (i.e., the heading errors between the launcher’s orientation angle and the interceptor’s flight direction). Additionally, Guo et al. [ 39 ] have pointed out that initial heading errors can negatively affect the entire course of action. To overcome this limitation of interceptor countering area targets, WTA methods should consider the degradation of PK due to heading errors. Kim and colleagues [ 46 ] have addressed the aforementioned concerns by developing a model that considers the variation in PK as a function of changes in heading errors. They compared the performance of two strategies: the rotation-fixed (RF) strategy and the rotation (R) strategy, which differ in how they manage the launcher’s orientation angle relative to the target’s approach angle. The RF strategy fixes the orientation angle at a specific value for all engagements, while the R strategy rotates the launcher’s orientation angle to align with the target’s approach angle. The authors analyzed the trade-off between reaction time and PK degradation for each strategy. To achieve a more effective balance between PK degradation and reaction time, they extended the strategies to the clustering-based WTA (CWTA) method, where targets are clustered using a representative point that can potentially be intercepted for each target. The initial orientation angle of each launcher is then determined based on the centroid of each cluster relative to each launcher.

However, the previous study was limited because it used a single strategy, either R or RF, for all engagements without the flexibility to adjust to different engagement situations. More specifically, when the two strategies are properly mixed and used, more optimal results can be obtained by the trade-off between reaction time and PK degradation, depending on engagement situations. Based on this rationale, this study aims to propose a mixed version of R and RF strategies that allows for the selection of either R or RF strategies for each engagement based on the launcher’s orientation angle. This mixed strategy approach provides greater flexibility, allowing for the decision to maintain the current orientation angle or rotate it to some extent when using the R strategy for a particular engagement. Unlike the previous study, where the optimal orientation angle for each engagement was predetermined under the R strategy, the proposed method permits variations in the orientation angle for each engagement. Additionally, the clustering approach from the previous study can still be applied in the mixed version to further reduce the rotation angle. In this study, numerical simulations are performed to investigate the performance of the proposed method. The results will show that the proposed method (i.e., the mixed version of R and RF) is superior to using only R or RF strategies. The main contribution of this study is to establish a new WTA method for the rotation-mixed (M) strategy, which considers the launcher’s orientation angle as a decision variable for each engagement, unlike the prior R and RF strategies. The key feature of the proposed method lies in its simplicity and superiority, suitable for the interception of area targets.

The structure of the paper is as follows: In Sect. 2 , the formulation of the WTA problems is presented, taking into account the mixed version of R and RF strategies. Section 3 describes the proposed WTA algorithm. The effectiveness of the proposed method is demonstrated through numerical simulations in Sect. 4 . Finally, Sect. 6 summarizes the findings and draws conclusions.

2 PK Modeling

The main goal of WTA problems is to achieve the highest possible expected PK for all targets that have been identified. Therefore, when defining the objective function for WTA problems, the focus should be on maximizing the overall PK against targets that pose a threat and are being countered by interceptors. In this study, a three-dimensional (3D) engagement scenario is considered. However, the PK value is determined based on the $X_I-Y_I$ planar engagement geometry between the launcher and the target, as illustrated in Fig. 1 . This rationale stems from the similarity in the impact of PK value fluctuations resulting from vertical engagement geometry on both R strategy and RF strategy. In contrast, the variations in PK attributed to horizontal engagement geometry significantly influence both R strategy and RF strategy.

Planar engagement geometry

The PK value is calculated using the three geometric parameters. The first parameter, denoted as $a^{\textrm{HE}}_{t,w,s}$ , refers to the heading errors between the predicted intercept point (PIP) $X^{\textrm{pip}}_{t,w,s}$ of the target t at a specific time slot s and the launcher w located at $X_{w}$ . The second parameter, denoted as $a^{M}_{t,w,s}$ , represents the predicted intercept angle between the moving direction $M_{t,w,s}$ of the target at the time of interception and the approaching direction $H_{t,w,s}$ of the interceptor. Finally, the third parameter is the relative distance $r_{t,w,s}$ calculated based on the positions of the target and launcher.

More specifically, the heading error is defined as the angle between $O_{w}$ , which denotes the orientation angle of the launcher w , and $H_{t,w,s}$ , which indicates the heading angle toward the PIP of the target t , given by:

The PK variation according to a relative distance and heading error, b expected target’s leading angle and heading error

In this context, the PIP refers to the expected location of the interception between the target t and the interceptor launched from the launcher w at a specific time s . In order to compute the PIP, it is essential to ensure that the flight time for the target to reach the PIP is equal to the flight time of the assigned interceptor to reach the PIP, starting from the moment of firing. The predicted intercept angle $a^{M}_{t,w,s}$ can be determined by calculating the angle between the approaching angle of the target $M_{t,w,s}$ and the opposite angle of the interceptor’s flight direction $-H_{t,w,s}$ as follows:

The Euclidean distance between a launcher position $X_{w}$ and a particular PIP $X^{\textrm{pip}}_{t,w,s}$ is established as the relative distance between the two points. This relative distance is calculated as follows:

The computation of the expected PK $P_{t,w,s}$ involves the multiplication of three separate Gaussian functions, denoted as G , which depend on the geometric parameters $a^{\textrm{HE}}_{t,w,s}$ , $a^{M}_{t,w,s}$ , and $r_{t,w,s}$ as follows:

The Gaussian function used in this study is given by

The first term on the right-hand side of Eq. ( 4 ) describes how the PK varies as a result of changes in heading errors. This variation is modeled using a Gaussian function, where $\mu ^{a_{\textrm{HE}}}$ represents the mean and $\sigma ^{a_{\textrm{HE}}}$ represents the standard deviation. An increase in heading errors can cause a degradation in the PK, as it requires more maneuverability to intercept the target. The second term in Eq. ( 4 ) represents the PK variation as a function of the expected angle difference between the approach direction of the interceptor and the velocity direction of the target. The mean is represented by $\mu ^{a_{M}}$ , while the standard deviation is denoted by $\sigma ^{a_{M}}$ . In Eq. ( 4 ), the third term expresses the PK variation due to changes in relative distance, where $\mu ^{r}$ represents the mean and $\sigma ^{r}$ represents the standard deviation. The Gaussian functions for each term have a value ranging from 0 to 1. Accordingly, the overall PK $P_{t,w,s}$ also has a value ranging from 0 to 1.

Figure 2 illustrates the PK model used in the study, where the design parameters for heading errors, relative distance, and the expected target’s leading angle are specified. The values chosen for the parameters are $\mu ^{a^{\textrm{HE}}}=0\;\deg $ , $\sigma ^{a^{\textrm{HE}}}=20\;\deg $ , $\mu ^{r}=20\;\textrm{km}$ , $\sigma ^{r}=10\;\textrm{km}$ , $r^{\max }=35\;\textrm{km}$ , $r^{\min }=5\;\textrm{km}$ , $\mu ^{a^{M}}=0\;\deg $ , and $\sigma ^{a^{M}}=20\;\deg $ , respectively. The PK variation patterns shown in Fig. 2 are adjusted by manipulating a two-factor pair: the expected target’s leading angle versus heading error and relative distance versus heading error. This study presents two figures to illustrate this manipulation. In Fig. 2 a, the PK variation is based on changes in relative distance and heading error, while the PK induced by only an expected target’s leading angle is kept constant at 1. The engagement region is limited to $r_{t,w,s} > r^{\min }$ and $r_{t,w,s} < r^{\max }$ in Fig. 2 (a). The PK reaches its maximum at $r_{t,w,s}=\mu ^{r}$ and $a^{\textrm{HE}}_{t,w,s}=\mu ^{a^{\textrm{HE}}}$ , and decreases as the relative distance deviates from $\mu ^{r}$ and heading error deviates from $\mu ^{a^{\textrm{HE}}}$ . In Fig. 2 b, the PK induced by only a relative distance is fixed at 1, while the PK variation based on changes in the expected target’s leading angle and heading error is shown. The parameter $\sigma $ (i.e., $\sigma ^{r}$ , $\sigma ^{a^{\textrm{HE}}}$ , and $\sigma ^{a^{M}}$ ) governs the rate at which the PK decreases. As the value of $\sigma ^{a^{\textrm{HE}}}$ increases, the decreasing rate of the PK due to heading error decreases. When $\sigma ^{a^{\textrm{HE}}}\rightarrow \infty $ , the effect of PK variation due to heading errors is diminished in the model. The parameter $\sigma $ is highly related to the interceptor’s maneuverability, and it is meaningful to examine how the PK variation changes with alterations to $\sigma ^{a^{\textrm{HE}}}$ .

In the comprehensive design of a fire control system, the development of a weapon–target assignment algorithm operates under the premise that a PK model is available. This PK model can either stem from a distinct computation process or be a streamlined version that captures the core attributes of the complete PK model [ 18 , 47 ]. Subsequently, the accurate PK model is determined and integrated with the weapon–target assignment algorithm. In general, the discrepancy in the PK modeling would lead to a decline in the performance of the weapon–target assignment algorithm. Therefore, an exhaustive and quantitative analysis, including sensitivity assessments, becomes imperative. However, this study focuses on the development of the weapon–target assignment algorithm itself. Thus, it is assumed that the consideration of a streamlined PK model that encapsulates the fundamental features of the accurate PK model is sufficient for achieving this purpose in practice, as in the previous studies [ 18 , 47 ].

As shown in Eqs. ( 4 ) and ( 5 ), we employ scaled Gaussian functions with uniform weighting factors to establish the PK model. This choice stems from the fact that constant scale factors within the PK model have no impact on the optimization outcomes when the objective function aims to maximize the aggregate PK value.

3 Problem Formulation

This section describes the formulations of the WTA problem for three strategies: RF, R, and M strategies, using the mixed-integer linear programming (MILP) framework. The formulation proposed by Kim and colleagues focuses on RF strategy and R strategy separately (i.e., unitary strategy), and it cannot be applied by combining RF and R [ 46 ]. A new formulation for the mixed version of the R and RF strategy is proposed in this chapter. It is worth noting that the main difference between the M strategy and the unitary strategies (R and RF) is whether the decision of a launcher’s orientation angle for each engagement is considered as a decision variable.

3.1 Formulation of Unitary Strategy

The WTA problems can be expressed by defining decision variables and constraints, as well as an objective function that takes into account the degradation of PK resulting from changes in heading errors. The constraints in this problem involve the rotation of the orientation angle of a launcher, and the choice between using the R strategy or the RF strategy depends on whether these constraints are taken into account. Under the RF strategy, the orientation angle of each launcher is fixed during engagement to reduce the delay in firing an interceptor against a target. On the other hand, the R strategy involves aligning the orientation angle of each launcher with the heading angle towards the PIP of a target in order to eliminate the heading errors. Thus, the RF strategy has a short reaction time, so it can engage a large number of targets in a given time, but the PK for each engagement is reduced. The R strategy has a relatively large reaction time, so the number of targets that can be engaged in a given time is reduced, but the PK for each engagement is high.

3.1.1 Decision Variable

The primary determinant in the WTA problem is whether a particular launcher w ’s firing time slot s is designated for a specific target t , which serves as the key variable to be decided. This research defines a decision variable, denoted as $\ominus _{t,w,s}$ , for unitary strategies. The variable $\ominus _{t,w,s}$ represents the assignment of a launcher w against a target t at firing time slot s . The variable $\ominus _{t,w,s}$ is 1 if the launcher w is assigned to the target t at time slot s , otherwise 0.

3.1.2 Objective Function

In this context, the objective function is chosen to reflect the PK function that takes into account the factors of heading errors, relative distance, and the expected target’s leading angle, as previously mentioned. The ultimate goal of the WTA problem considered in this study is to maximize the total PK value of all identified targets as follows:

where the function $p\left( r_{t,w,s}, a^{\textrm{HE}}_{t,w,s}, a^{M}_{t,w,s}\right) $ indicates the probability of successful destruction of target t by the interceptor launched from launcher w .

3.1.3 Practical Constraints for General WTA Problems

Due to the limited availability of interceptors and a limited time window of opportunity to use them against targets, there are restrictions on assigning launchers to targets. In addition, the system has inherent limitations, including the time required for the launcher to prepare for firing an interceptor and the need to stabilize vibrations resulting from the launch. These conditions and limitations are considered as constraints. One of the primary constraints is that each launcher can only fire one interceptor at a time, which means that each designated time slot for a launcher should be assigned to a specific target. This limitation can be expressed as follows:

In this study, it is assumed that the number of interceptors assigned to each launcher is predetermined without considering the reloading process. Furthermore, as the firing process continues, the number of interceptors available for each launcher decreases, which means that the constraint related to the number of available interceptors should be considered in the WTA problem formulation. Accordingly, the limitation pertaining to the overall number of interceptors available for each launcher can be expressed as follows:

where the variable $n^{st}_{w}$ represents the highest possible quantity of usable interceptors for a launcher denoted by w . “st” of $n^{st}_{w}$ is an abbreviation for “stock”. Additionally, it is necessary to set a limit on the number of interceptors that can be assigned to a single target. This restriction is in place to avoid wastage of interceptors due to redundant allocations to a single target. This limitation on the total number of interceptors that can be assigned to a target is expressed as follows:

where the variable $n^{\textrm{as}}_{t}$ represents the upper limit on the number of interceptors assigned to the target t . “as” of $n^{\textrm{as}}_{t}$ is an abbreviation for “assign”.

In addition to these constraints, real-world engagement systems have additional practical constraints that should be considered. For example, there is a delay between receiving a firing command and the actual firing of the interceptor. A certain amount of time is also required for the launcher to stabilize after each firing. As a result, the constraints related to the time required for the firing process and the delay between subsequent firings can be formulated as follows:

where the parameter $\tau ^{d}$ stands for the time required between successive firing processes of a launcher. If a weapon w is assigned to target $t_{1}$ at time slot $s_{1}$ , then the value of $\ominus _{t_{1},w,s_{1}}$ is set to 1; otherwise, it is set to 0. Similarly, if a weapon w is assigned to target $t_{2}$ at time slot $s_{2}$ , then the value of $\ominus _{t_{2},w,s_{2}}$ is set to 1; otherwise, it is set to 0. This constraint ensures that $\ominus _{t_{1},w,s_{1}}$ and $\ominus _{t_{2},w,s_{2}}$ cannot both be 1 at the same time, preventing any additional assignment from being made within the time required for the launch procedure.

Moreover, the available firing time slot for a launcher-target pair is determined by the flight time required to reach the PIP, which should be within the interceptor’s maneuverability range. Thus, the feasible firing time slot is defined as the time slot corresponding to the PIP within the engagement region, as given by the following constraint.

where the parameter $L_{t,w}$ represents the collection of launch time slots associated with the region within which an interceptor fired from the launcher w can reach and intercept the target t . Therefore, any time slots of the launcher w , not included in $L_{t,w}$ , are unavailable for deployment against the target t .

3.1.4 Additional Constraints for Rotation Strategy

If a WTA problem for the R strategy is considered, it is essential to also take into account time limitations. These include the time needed to rotate an orientation angle of a launcher and the time required to align the launcher and interceptors after the rotation. To calculate the time needed to rotate the launcher’s orientation angle, the required rotation angle and the launcher’s rotational velocity should be considered. The necessary rotation angle for the launcher between two consecutive engagements can be determined using the following equation:

where the variable $H_{t_{1},w,s_{1}}$ refers to the orientation angle that the launcher w needs to be directed towards the PIP of a specific target $t_{1}$ at a particular time slot $s_{1}$ . Similarly, the variable $H_{t_{2},w,s_{2}}$ represents the orientation angle required for the same launcher w to point towards the PIP of another target $t_{2}$ at a different time slot $s_{2}$ . By assuming that the launcher’s rotation speed is constant, we can determine the time required to adjust the orientation angle of the launcher as follows:

where the parameter $v^{\textrm{rot}}$ represents the angular velocity required to rotate the orientation angle of a launcher, and the variable $a^{\textrm{rot}}_{w,t{1},s_{1},t_{2},s_{2}}$ represents the extent of the angle that needs to be rotated by the launcher. Additionally, after rotating the orientation angle of a launcher, time to realign internal devices of a launcher is required for the stable fire of the next interceptor. Based on this parameter, the constraint for the required time to rotate the launcher’s orientation angle and stabilize the launcher after rotating can be written as:

where the variable $\tau ^{\textrm{rot}}_{w,t_{1},s_{1},t_{2},s_{2}}$ denotes the time that the launcher takes to rotate its orientation from the angle $s_1$ at time $t_1$ to the angle $s_2$ at time $t_2$ . The parameter $\tau ^{\textrm{align}}$ is a fixed time period required for the launcher to stabilize its orientation following a rotation. In addition, there is a requirement to restrict the range of rotation. To enforce this limitation, the condition that the launcher’s rotation should not exceed the designated angle of rotation can be expressed as follows:

where the variable $a^{\textrm{ini}}_{w}$ represents the initial orientation angle of launcher w , and the parameter $a^{\max }$ denotes the maximum allowable range of rotation for the launcher relative to its initial orientation angle.

3.2 Formulation of Mixed Strategy

If a single strategy of either R strategy or RF strategy is applied consistently throughout all engagements, it can impose limitations on its effectiveness. The R strategy aims to eliminate heading errors but incurs a time penalty due to rotation. This approach can yield the maximum predicted PK for each engagement, but it also poses a risk of missing engagement opportunities due to the time lost during rotation. On the other hand, the RF strategy eliminates time loss caused by rotation, but it may result in lower PK due to heading errors. Although this approach may not achieve the maximum predicted PK for all engagements, it eliminates the risk of missed opportunities due to time loss. Moreover, using a single strategy does not resolve the two essential limitations present in both R and RF strategies: the inability to identify the appropriate strategy and select the orientation angle against a target for each engagement.

Consequently, this research paper investigates a new WTA strategy by combining R and RF strategies with orientation angle determination for each engagement. The R strategy determines a rotation angle that aligns with the PIP and only attempts engagement if there is enough time to rotate to the objective angle. However, if there is not enough time, the system may not attempt engagement. To address missed opportunities, incorporating flexibility into the system to engage while maintaining the current angle or rotating within a limited angle range, given the time constraints, could be beneficial. Conversely, the RF strategy maintains a constant orientation angle for all engagements. This implies that even if there is enough time to rotate, the system is unable to choose an alternative to rotate the angle to reduce potential PK loss. In such situations, having flexibility in the system to decide on rotating the angle within specified time constraints could potentially prevent PK loss in some engagements.

To decide whether and how much to rotate the launcher’s orientation angle for each engagement, the decision variable should be changed from $\ominus _{t,w,s}$ to $\ominus _{t,w,s,o}$ . However, this modification increases the search space from three to four dimensions, adding the orientation angle as a new variable alongside target, weapon, and time slots. This expansion in search space may result in longer search times and larger input data sizes, making it impractical for real-world air defense systems. To address this issue, we propose a two-level hierarchical formulation of the WTA problem that restricts the increase in search space for a decision variable. Previous studies, including those by Leboucher and colleagues [ 30 ] and Uhm and Lee [ 41 ], have also used a two-level hierarchical structure to solve the WTA problem, particularly when considering PKs that change over time. During the first level of the WTA model, pairs of targets and launchers are chosen while considering time constraints such as firing time windows. The reason why time constraints should be considered in the first level is to prevent the possibility of not being able to engage at the second level due to time constraints such as firing time window and successive launching delay. To account for these constraints, the decision variable $\ominus _{t,w,s}$ is used. During the second level process, the firing time slot and orientation angle are established for the targets assigned to each launcher. A new decision variable, $\zeta _{t,s,o}$ , is introduced in the second level to facilitate this process. The decision variable $\zeta _{t,s,o}$ represents the assignment of time slot s of a certain launcher against a target t at an orientation angle o , and $\zeta _{t,s,o}$ is 1 if time slot s of a certain launcher against a target t at an orientation angle o ; otherwise 0. The determination of firing time and orientation angle for targets is carried out on a per-launcher basis, meaning that it is performed independently for each launcher. The following formulation is established to address the problem of determining the appropriate firing time and orientation angle for targets assigned to a specific launcher.

The objective function in this context is to obtain the maximum overall PK against assigned targets, similar to that of the first level.

where the variable $a^{\textrm{HE}}_{t,s,o}$ represents the difference between the orientation angle o of a launcher during the firing time slot s and the approach angle of target t . The variable $a^{M}_{t,s,o}$ denotes the leading angle of the target. The function $p\left( r_{t,s,o}, a^{\textrm{HE}}_{t,s,o}, a^{M}_{t,s,o}\right) $ denotes the expected probability of effectively destroying the target t by the interceptor launched during the time slot s with the orientation angle o . It is important to define and take into account limitations related to time, such as the time period for firing and the need to adjust the orientation angle of a launcher. These restrictions should be incorporated into the decision variable $\zeta _{t,s,o}$ . The constraint specifying that each designated time slot of a launcher can only be assigned to a single target is written as:

where the notation $\ominus _{t,s,o}$ indicates whether a particular time slot s and orientation angle o have been assigned to a target t . The feasible firing time window for each target is determined as the time slot that corresponds to the PIP within the engagement region, as specified by:

where the parameter $L_{t}$ represents the set of firing time slots associated with the region in which an interceptor can reach and intercept target t . Thus, any time slots that are not included in $L_{t}$ are not applicable for deploying against target t . The constraint for successive launches should consider the time required for firing, the time needed to rotate the orientation angle of a launcher, and the assignment of the launcher and interceptors. It can be expressed as:

where the set T represents the assigned targets for a launcher. If the orientation angles $o_{1}$ and $o_{2}$ are identical, the RF strategy is chosen. Conversely, if the orientation angles $o_{1}$ and $o_{2}$ are different, the R strategy is chosen. The limitation of the range of rotation can be expressed as follows:

Here, the variable $a^{\textrm{ini}}$ represents the initial orientation angle of a launcher, and the parameter $a^{\max }$ represents the maximum allowable range of rotation for the launcher relative to its initial orientation angle as described before.

The flow of WTA under unitary strategies

This section delves into two WTA methods: the first one is the unitary strategies developed by Kim et al. (referred to as [ 46 ]), while the second one is a WTA method that combines the R and RF strategies proposed in this study.

The WTA under RF strategy a first engagement, b second engagement, c third engagement

The WTA under R strategy a first engagement, b second engagement, c third engagement

4.1 WTA Under Unitary Strategy

Kim et al. (referenced as [ 46 ]) introduced the RF strategy and R strategy for WTA methods, which utilize the Greedy Maximization (GM) algorithm for efficiency in terms of computation time and performance [ 48 , 49 ]. In the case of WTAs utilizing unitary strategies, a selection and exclusion loop framework is employed, as illustrated in Fig. 3 . The set of candidates ( V ) comprises all possible combinations of targets, weapons, and time slots. During the selection process, a candidate ( $\ominus ^{*}$ ) is chosen from the candidate set, which maximizes the gain in the candidate set excluding the selection set ( P ) and the exclusion set ( Q ). Once selected, this candidate is added to the selection set. Any candidate that violates constraints due to the inclusion of the new candidate is placed into the exclusion set. This process of selecting and excluding candidates continues until the candidate set (excluding the selection set and the exclusion set) is empty or no further gain can be achieved. In the exclusion phase, the constraints for the stock of selected launchers and the maximum number of interceptors ( $n_{t}^{\textrm{as}}$ ) for a target within a specific time interval for successive launches are taken into account. Additionally, for the R strategy, the time interval between successive launches includes the time ( $\tau ^{\textrm{rot}} + \tau ^{\textrm{align}}$ ) required for rotating the orientation angle of a launcher along with the time interval ( $\tau ^{d}$ ).

Figures 4 and 5 depict sequential engagement strategies used by WTA. Figure 4 employs the RF strategy, which maintains the launcher’s orientation angle at an initial angle of $a_{\textrm{ini}}$ . To achieve the desired probability of interception and avoid degradation of the PK caused by heading errors, the guided interceptor should have sufficient maneuverability to approach the PIP. The engagement region depicted in Fig. 4 represents the area where the probability of interception satisfies or exceeds a reference value, and the firing window is a constraint that ensures interception occurs within this region. In the case of the RF strategy, where the initial orientation angle is maintained, a significant loss of PK can occur when targets approach from a completely different orientation compared to the initial angle. To mitigate this PK loss, Kim et al. [ 46 ] adjust the initial orientation angle to align with the direction of the target. This adjustment aims to reduce the PK loss, but not necessarily eliminate it entirely.

4.2 WTA Under Mixed Strategy

The flow of CWTA under M strategy

The WTA under the combination of R and RF strategy a first engagement, b second engagement, and c third engagement

The proposed WTA method has been extended to a mixed strategy of RF and R in order to improve upon the unitary strategies of the previous WTA methods. Figure 6 provides an illustration of the process flow for the WTA method under the mixed strategy. This method utilizes the target–launcher assignment results obtained from the WTA method under RF strategy while also implementing an additional procedure in step 1 to determine the initial orientation angle of the launcher based on the target distribution. This step helps to reduce the difference between the launcher’s orientation angle and the target’s approaching angle. In step 2, targets are assigned to each launcher, taking into account time constraints such as the restricted firing time window and delay for successive launches. In step 3, the time slot and orientation angle are determined for each assigned target on an individual launcher basis using the newly proposed Algorithm 1, which builds on the problem formulation presented in Sect. 3 . The constraints relating to the firing window and the time required to rotate the launcher’s orientation angle are inspected to select a feasible solution that satisfies the time limitation. The process of examining these constraints is described in Algorithm 2 in detail.

Sequential engagements from the WTA method under the mixed strategy are illustrated in Fig. 7 . The first engagement is carried out using the RF strategy, which maintains the launcher’s initial orientation angle (i.e., $a^{\textrm{ini}}$ ). The second engagement is also accomplished using the RF strategy, but a slight loss in PK occurs due to heading errors. The proposed WTA method is capable of selecting R and RF strategies for each engagement. If the R strategy is selected, the extent of rotation is determined to align completely with the PIP or a certain proper angle. The third engagement is computed using the R strategy, but the orientation angle of the launcher rotates close to the completely aligned angle with the PIP. As a result, there is also a slight loss in PK, but the amount of PK loss is less than that of maintaining the initial orientation angle.

The trajectory demonstration of a scenario 1, b scenario 2

Algorithm 1 outlines the process of determining the appropriate pairs of target, orientation angle, and firing time slot using the greedy maximization assignment algorithm. The algorithm follows a selection and exclusion framework and selects a new solution candidate that achieves the maximum marginal gain $\bigtriangleup f\left( \ominus | P_{w} \right) $ as shown in (lines 14–18). Feasible pairs within the time slot and target set are considered as long as they are not apart from the limit angle of $a^{\max }$ (lines 2–13). The algorithm also takes into account constraints for the firing time window and rotation angle limit. The exclusion process described in Algorithm 2 ensures that there is no duplicated assignment of each time slot (lines 20–26) and considers the time delay $\tau ^{d}$ of successive launch, based on the determined strategy of R and RF (lines 2–19). In the RF strategy, only the delay time for the firing process and stabilization of vibration after launch are considered (lines 7–9), while in the R strategy, the time delay for rotating the orientation angle $\tau ^{\textrm{rot}}_{o,o^{*}}$ and time for alignment $\tau ^{\textrm{align}}$ after rotation are also considered along with the delay time for firing (lines 11–13).

5 Simulations

This section examines the simulation results of some scenarios using four different methods, and their performance is evaluated based on the indicators recommended by Kim et al. [ 46 ]. These indicators include overall PK ( $PK^{overall}$ ), PK loss ( $PK^{loss}$ ), time loss due to rotation, and missed opportunities for engagement ( $E^{loss}$ ). Table 1 presents a summary of the four distinct methods: WTA-RF, WTA-R, CWTA-RF, and the proposed CWTA-M. The WTA-RF is a conventional method that does not take heading error into account. The WTA-R method applies the R strategy to nullify heading error. The CWTA-RF method follows the RF strategy but initializes the orientation angle based on the target population. Lastly, the CWTA-M proposed in this paper applies both R and RF strategies depending on the situation.

During the simulation, we investigated defense scenarios against a considerable number of targets concentrated in a confined area, specifically low-altitude rocket threats in 3D space. These multiple targets, representing low-altitude rocket threats, were assumed to follow a ballistic trajectory with speeds ranging from 400 to 500 m/s during their descent phase. Additionally, we considered a situation where there are six enemy launchers, and each launcher sequentially fired 18–45 rocket threats. The minimum firing interval in this simulation was set to 0.5 s. To determine the ground target points for the low-altitude rocket threats, we employed Monte Carlo simulations to randomly select locations within a small region of approximately 9 to 12 km $^2$ . The trajectories of the enemies are illustrated in Fig. 8 a, b. In Fig. 8 a, the enemy launchers are evenly distributed at regular intervals. In contrast, the scenario depicted in Fig. 8 b involves enemy launchers divided into two groups, attacking a specific region within the defense area. The experiment used parameters that reflect realistic weapon systems, with a defense system’s engagement region limited between $4\;\textrm{km}$ and $12\;\textrm{km}$ . The experiment assumed two scenarios, each with 6 launchers and up to 270 targets. The time delay between the launching of each interceptor was set to 0.5 seconds, with an average speed of $400\;\mathrm{m/s}$ assumed for the interceptor. The launcher’s alignment time after launch, rotational speed, and maximum rotation limit were set to $\tau ^{\textrm{align}} = 1.5$ seconds, $v^{\textrm{rot}} = 15$ degrees per second, and $a^{\max } = 60$ degree, respectively. The experiment evaluated the effectiveness of the engagement using a randomly selected chance factor from the PK model. It is presumed that the defensive system’s area of operation for which an interceptor can intercept a target is limited by a maximum radius of $12\;\textrm{km}$ and a minimum radius of $4\;\textrm{km}$ . The mean and standard deviation of the engagement range were set to $\mu ^{r}=\left( r^{\max }+r^{\min }\right) /2$ and $\sigma ^{r} = 4\;\textrm{km}$ , respectively.

The result of simulation for scenario 1 according to the number of target increase a the overall PK, b the loss of PK, c the loss of time for rotation, and d the loss of engagement opportunity

The result of simulation for scenario 1 according to the standard deviation $\sigma ^{a_{\textrm{HE}}}$ of heading error increase a the overall PK, b the loss of PK, c the loss of time for rotation, and d the loss of engagement opportunity

The result of simulation for scenario 2 according to the number of target increase, a the overall PK, b the loss of PK, c the loss of time for rotation, and d the loss of engagement opportunity

The result of simulation for scenario 2 according to the standard deviation $\sigma ^{a_{\textrm{HE}}}$ of heading error increase a the overall PK, b the loss of PK, c the loss of time for rotation, and d the loss of engagement opportunity

The results of the simulation in Fig. 9 exhibit an increase in the number of targets in scenario 1. It is evident that WTA-R is inferior to WTA-RF since the latter nullifies the heading error by rotating the orientation angle of a launcher to the PIP direction. Additionally, CWTA-RF surpasses WTA-RF by reducing the heading error by adjusting the initial orientation angle to the region where PIP is formed. However, there are limitations to both WTA-R and CWTA-RF. While WTA-R improves the vulnerability of WTA-RF, it cannot engage certain targets due to the time required for rotating the orientation angles of launchers. Similarly, CWTA-RF cannot use the rotation strategy, even if there is time to apply it for some targets. To address these limitations, CWTA-M combines both R and RF strategies, resulting in the reduction of missed targets compared to WTA-R, as shown in Fig. 9 d. Additionally, CWTA-M further alleviates PK gradation by heading errors compared to CWTA-RF by applying the R strategy for some engagements, as shown in Fig. 9 b. Figure 9 c demonstrates that CWTA-M reduces the rotation time of launchers compared to WTA-R by applying the RF strategy together with the R strategy. Overall, the simulation results reveal that CWTA-M shows the most dominant performance by overcoming the limitations of both WTA-R and CWTA-RF. In Fig. 10 , the simulation results for scenario 1 display a comparison of the performance of the four methods according to the variable $\sigma ^{{a_{\textrm{HE}}}}$ , which determines the ratio of PK degradation by heading errors in relation to the interceptor’s characteristics.

As shown in Fig. 11 a, CWTA-M outperforms WTA-R and CWTA-RF in scenario 2 simulations. Figure 11 b indicates that CWTA-M mitigates PK degradation due to heading errors compared to CWTA-RF. Additionally, Fig. 11 d shows that CWTA-M has fewer missed targets than CWTA-R. In Fig. 11 c, there is no significant difference in the time required for rotation. However, the results presented in Fig. 11 b, d suggest that the total amount of rotation is not a crucial factor. Instead, the reduction of missed targets and PK degradation due to heading errors can be achieved by selecting an appropriate rotation strategy for each target, determining when and at what angle to rotate. Figure 12 depicts the simulation results for the increasing values of $\sigma ^{{a_{\textrm{HE}}}}$ in scenario 2. The trend of the results is similar to that observed in scenario 1. With an increase in $\sigma ^{{a_{\textrm{HE}}}}$ , the PK degradation ratio decreases due to heading errors. Therefore, if $\sigma ^{{a_{\textrm{HE}}}}$ increases, the results of the four methods become similar. In this study, our focus is on cases where the impact of heading error on PK degradation is significant. Accordingly, the performance of CWTA-M dominates in situations where $\sigma ^{{a_{\textrm{HE}}}}$ is less than 10. Similarly, as illustrated in Fig. 12 b, d, it is evident that CWTA-M is superior in terms of the number of targets engaged in PK loss caused by heading errors.

To summarize, the R strategy is effective in mitigating PK loss caused by heading errors and improving engagement success rates. However, its unitary implementation has limitations, as it only determines the rotation angle towards the PIP direction, which may result in missed engagements if there is insufficient time to rotate to the objective orientation angle. In such cases, alternative strategies like the RF strategy or determining a rotation angle within the available time constraints could increase engagement success rates. By allowing for the selection of R and RF strategies and determining the rotation angle for each engagement, the limitation of the unitary R strategy was overcome, and the CWTA-M outperformed WTA under the unitary strategy, as demonstrated in the simulation results.

6 Conclusions

The proposed WTA algorithms aim to improve the defense against multiple targets in narrow areas, which is a challenging task due to the limited maneuverability of interceptors. The use of a rotation strategy to align the orientation angle with the target’s approach direction can significantly improve the PK against the target. However, the unitary implementation of the WTA algorithm with a rotation strategy only aligns the orientation angle toward the PIP direction, which may result in missed engagements if there is insufficient time to rotate to the objective orientation angle. To overcome this limitation, the study proposes a mixed version of the strategy that allows for the selection of R and RF strategies and the determination of the rotation angle for each engagement. This approach can reduce PK degradation and reaction time, leading to better performance against multiple targets. The proposed approach involves the inclusion of a step to determine the rotation angle to determine the R and RF strategy, alongside making modifications to the WTA formulation. Numerical simulations were then conducted to evaluate the effectiveness of these methods. Results from the simulations indicate that the proposed methods outperformed the unitary strategy when faced with multiple targets. One of the main advantages of the proposed algorithms is their ability to overcome PK degradation caused by heading errors while also achieving high performance and efficient use of resources through the flexible application of the R and RF strategy to manage the trade-off between PK degradation and reaction time.

In future research, it would be beneficial to identify additional factors and challenges that could be taken into account during a WTA process to aid decision-making for defending against area targets. Such considerations may include avoiding interference between interceptors, accounting for misidentification between debris and actual targets due to collisions, and expanding sensor–weapon–target assignment problems for cooperative engagements. Additionally, WTA simulations should be conducted using various types of area targets and interceptors, along with more realistic and diverse scenarios that incorporate target attack patterns.

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

Article MathSciNet Google Scholar

Roux JN, Van Vuuren JH (2007) Threat evaluation and weapon assignment decision support: a review of the state of the art. ORiON 23(2):151–187

Article Google Scholar

Day RH (1966) Allocating weapons to target complexes by means of nonlinear programming. Oper Res 14(6):992–1013

Lloyd SP, Witsenhausen HS (1986) Weapon allocation is NP complete. In: Proc. IEEE Summer Comput. Simul. Conf., Reno, pp 1054–1058

Ni M, Yu Z, Ma F, Wu X (2011) A lagrange relaxation method for solving weapon-target assignment problem. Math Probl Eng 2011:873292. https://doi.org/10.1155/2011/873292

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

Ahuja RK, Kumar A, Jha KC, Orlin JB (2007) Exact and heuristic algorithms for the weapon-target assignment problem. Oper Res 55(6):1136–1146

Lee ZJ, Lee CY, Su SF (2002) An immunity-based ant colony optimization algorithm for solving weapon-target assignment problem. Appl Soft Comput 2(1):39–47

Zhou Y, Li X, Wang W (2016) A discrete particle swarm optimization algorithm applied in constrained static weapon-target assignment problem. In: Proc. IEEE 12th World Congr. Intell. Control Automat. (WCICA), pp 3118–3123

Li P, Wu L, Lu F (2009) A mutation-based GA for weapon-target allocation problem subject to spatial constraints. In: International workshop on intelligent systems and applications. IEEE, pp 1–4. https://doi.org/10.1109/IWISA.2009.5072642

Bisht S (2004) Hybrid genetic-simulated annealing algorithm for optimal weapon allocation in multilayer defence scenario. Defence Sci J 54(3):395–405

Blodgett DE, Gendreau M, Guertin F, Potvin J-Y, Seguin R (2003) A tabu search heuristic for resource management in naval warfare. J Heurist 9(2):145–169

Xin B, Chen J, Zhang J, Dou LH, Peng ZH (2010) Efficient decision makings for dynamic weapon-target assignment by virtual permutation and tabu search heuristics. IEEE Trans Syst Man Cybern C 40(6):649–662

Lee MZ (2010) Constrained weapon-target assignment: enhanced very large scale neighborhood search algorithm. IEEE Trans Syst Man Cybern A Syst Hum 40(1):198–204

Chang Y-Z, Li Z-W, Kou Y-X, Sun Q-P, Yang H-Y, Zhao Z-Y et al (2017) A new approach to weapon-target assignment in cooperative air combat. Math Probl Eng 2017

Wang J, Luo P, Hu X, Zhang X (2018) A hybrid discrete grey wolf optimizer to solve weapon target assignment problems. Discrete Dyn Nat Soc 2018:1–17

MathSciNet Google Scholar

Wang Z, Wang X, Liang Y, Pan Q (2013) Weapon target assignment leveraging strong submodularity. In: Proc. IEEE Int. Conf. Inf. Autom., Yinchuan, pp 74–79

Cho DH, Choi HL (2017) Greedy maximization for asset-based weapon-target assignment with time-dependent rewards. In: Wang Y (ed) Cooperative control of multi-agent systems: theory and applications. Wiley, New York, pp 115–139

Chapter Google Scholar

Jeong H (2020) Hierarchical lazy greedy algorithm for weapon target assignment. J KIMS Technol 23(4):381–388

Xin B, Wang Y, Chen J (2019) An efficient marginal-return-based constructive heuristic to solve the sensor-weapon-target assignment problem. IEEE Trans Syst Man Cybern Syst 49(2):2536–2547

Karasakal O (2008) Air defense missile-target allocation models for a naval task group. Comput Oper Res 35(2):1759–1770

Bogdanowicz ZR (2009) A new efficient algorithm for optimal assignment of smart weapons to targets. Comput Math Appl 58(4):1759–1770

Google Scholar

Huaiping C, Jingxu L, Yingwu C, Hao W (2006) Survey of the research on dynamic weapon-target assignment problem. J Syst Eng Electron 17(3):559–565

Hocaoglu MF (2019) Weapon target assignment optimization for land based multi-air defense systems: a goal programming approach. Comput Ind Eng 128:681–689

Mekawey HI, El-Wahab MSA, Hashem M (2009) Novel goal-based weapon target assignment doctrine. J Aerosp Comput Inf Comput 6:2–29

Xin B, Chen J, Peng Z, Dou L, Zhang J (2011) An efficient rule-based constructive heuristic to solve dynamic weapon-target assignment problem. IEEE Trans Syst Man Cybern Syst 41:598–606

Zhang K, Zhou D, Yang Z, Pan Q, Kong W (2019) Constrained multi-objective weapon target assignment for area targets by efficient evolutionary algorithm. IEEE Access 7:176339–176360

Gao C, Kou Y, Li Y, Li Z, Xu A (2011) Multi-objective weapon target assignment based on D-NSGA-III-A. IEEE Trans Syst Man Cybern Syst 7:50240–50254

Kline A, Ahner D, Hill R (2019) The weapon-target assignment problem. Comput Oper Res 105:226–236

Leboucher C, Shin H-S, Siarry P, Chelouah R, Le Ménec S, Tsourdos A (2013) A two-step optimisation method for dynamic weapon target assignment problem. In: Recent advances on meta-heuristics and their application to real scenarios, pp 109–129

Xin B, Chen J, Peng ZH, Dou LH, Zhang J (2011) An efficient rule-based constructive heuristic to solve dynamic weapon-target assignment problem. IEEE Trans Syst Man Cybern A Syst Hum 41:598–606

Khosla D (2001) Hybrid genetic approach for the dynamic weapon-target allocation problem. In: Battlespace digitization and network-centric warfare, vol 4396. International Society for Optics and Photonics, pp 244–260 . https://doi.org/10.1117/12.438322

Xin B, Chen J (2012) An estimation of distribution algorithm with efficient constructive repair/improvement operator for the dynamic weapon-target assignment. In: Proc. 31st Chin. Control Conf., Hefei

Park HW, Choi HL (2011) Weapon-target assignment and firing scheduling for rapid engagement with heterogeneous interceptors. ScienceDirect

Bogdanowicz ZR (2012) Advanced input generating algorithm for effect-based weapon-target pairing optimization. IEEE Trans Syst Man Cybern A Syst Hum 42:276–280

Ash M (1959) Letter to the editor-flood’s assignment model for small kill levels. Oper Res 7:258–260

Bogdanowicz ZR, Patel K (2015) Quick collateral damage estimation based on weapons assigned to targets. IEEE Trans Syst Man Cybern Syst 45:762–769

Bogdanowicz ZR, Tolano A, Patel K, Coleman NP (2013) Optimization of weapon-target pairings based on kill probabilities. IEEE Trans Cybern 43:1835–1844

Guo D, Liang Z, Jiang P, Dong X, Li Q, Ren Z (2019) Weapon-target assignment for multi-to-multi interception with grouping constraint. IEEE Access 7:34838–34849

Na H, Lee J (2020) Optimal arrangement of missile defense systems considering kill probability. IEEE Trans Aerosp Electron Syst 56:972–983

Uhm HS, Lee YH (2019) A heuristic algorithm for weapon target assignment and scheduling. Mil Oper Res 24:53–62

Evans RC (2011) National air defense: Challenges, solution profiles, and technology needs. The MITRE Corporation [Online]. http://ww.mitre.org/work/tech-papers/tech-papers-04/04-1108/04-1108.pdf

Missile defense review (2019). Office of the Secretary of Defense, 2019. [Online]. https://www.defense.gov/Portals/1/Interactive/2018/11-2019-Missile-Defense-Review/The

Andrew MAJ, Sanders W, US Army: Drone Swarms (2017) School of Advanced Military Studies. United States Army Command and General Staff College, Fort Leavenworth

Zhang K, Zhou D, Yang Z, Pan Q, Kong W (2017) Constrained multi-objective weapon target assignment for area targets by efficient evolutionary algorithm. IEEE Access 7:173669–176360

Kim JE, Lee CH, Yi MY (2022) New weapon target assignment algorithms for multiple targets using a rotational strategy and clustering approach. IEEE Access 10:43738–43750

Jang J, Yoon HG, Kim JC, Kim CO (2019) Adaptive weapon-to-target assignment model based on the real-time prediction of hit probability. IEEE Access 7:72210–72220

Krause A, Golovin D (2014) Submodular function maximization. In: Bordeaux L (ed) Tractability practical approaches to hard problems. Cambridge University Press, Cambridge, pp 71–104

Feldman M, Harshaw C, Karbasi A (2017) Greed is good: near-optimal submodular maximization via greedy optimization . arXiv preprint arXiv:1704.01652

Download references

Open Access funding enabled and organized by KAIST.

Author information

Authors and affiliations.

Industrial and Systems Engineering, KAIST, Daejeon, 34141, Republic of Korea

Ji-Eun Kim & Mun Yong Yi

Aerospace Engineering, KAIST, Daejeon, 34141, Republic of Korea

Chang-Hun Lee

You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mun Yong Yi .

Ethics declarations

Conflict of interest.

The authors clarify that there is no competing financial or non-financial interests that could have appeared to influence the work reported in this paper.

Additional information

Publisher's note.

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

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ .

Reprints and permissions

About this article

Kim, JE., Lee, CH. & Yi, M.Y. A Study on the Weapon–Target Assignment Problem Considering Heading Error. Int. J. Aeronaut. Space Sci. (2024). https://doi.org/10.1007/s42405-024-00717-5

Download citation

Received : 29 March 2023

Revised : 22 August 2023

Accepted : 05 February 2024

Published : 27 March 2024

DOI : https://doi.org/10.1007/s42405-024-00717-5

Share this article

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

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

Provided by the Springer Nature SharedIt content-sharing initiative

Weapon–target assignment
Heading error
Air defense system
Probability of kill
Find a journal
Publish with us
Track your research

ORIGINAL RESEARCH article

Partitioning qubo with two-way one-hot conditions on traveling salesman problems for city distributions with multiple clusters provisionally accepted.

1 NEC Corporation (Japan), Japan

The final, formatted version of the article will be published soon.

We introduce a method for solving a quadratic unconstrained binary optimization (QUBO) with the two-way one-hot constraints by dividing the QUBO into parts and solving it with an Ising machine. The one-hot constraint is a constraint condition in that only one binary variable takes the value one for a set of multiple binary variables. The two-way one-hot constraint imposes one-hot constraint conditions on every row and every column of a two-dimensional array of binary variables with equal numbers of rows and columns. For example, traveling salesman problems (TSPs) have two-way one-hot constraints. We propose two methods to solve a TSP by dividing the cities into clusters based on information in the QUBO matrix. The proposed methods decompose cities into clusters and solves TSPs for each cluster. We solve TSPs such that the cities are distributed in clusters and compare the results of the two proposed methods with the results of solving the problem without partitioning. The results show that the proposed methods are robust to the coefficient parameters in the Hamiltonian of QUBO and can obtain a solution closer to the optimal solution when solving the problem without partitioning is hard. We also discuss the application of the methods proposed in the TSPs to the quadratic assignment problems and to the problems of ordering things.

Keywords: Ising machines, combinatorial optimization problems, two-way one-hot constraints, Traveling salesman problems, Problem partitioning

Received: 29 Aug 2023; Accepted: 02 Apr 2024.

Copyright: © 2024 Yatabe. This is an open-access article distributed under the terms of the Creative Commons Attribution License (CC BY) . The use, distribution or reproduction in other forums is permitted, provided the original author(s) or licensor are credited and that the original publication in this journal is cited, in accordance with accepted academic practice. No use, distribution or reproduction is permitted which does not comply with these terms.

* Correspondence: Dr. Akihiro Yatabe, NEC Corporation (Japan), Tokyo, Japan

People also looked at

COMMENTS

Assignment Problem: Meaning, Methods and Variations
The flow chart of steps in the Hungarian method for solving an assignment problem is shown in following figures: Example: 1. In a computer centre after studying carefully the three expert programmes, the head of computer centre, estimates the computer time in minutes required by the experts for the application programmes as follows: ...
Assignment problem
Worked example of assigning tasks to an unequal number of workers using the Hungarian method. The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows: The problem instance has a number of agents and a number of tasks.Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent ...
Hungarian Algorithm for Assignment Problem
Time complexity : O(n^3), where n is the number of workers and jobs. This is because the algorithm implements the Hungarian algorithm, which is known to have a time complexity of O(n^3). Space complexity : O(n^2), where n is the number of workers and jobs.This is because the algorithm uses a 2D cost matrix of size n x n to store the costs of assigning each worker to a job, and additional ...
Hungarian Method
The Hungarian method is a computational optimization technique that addresses the assignment problem in polynomial time and foreshadows following primal-dual alternatives. In 1955, Harold Kuhn used the term "Hungarian method" to honour two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry. Let's go through the steps of the Hungarian method with the help of a solved example.
PDF Chapter8 ASSIGNMENT PROBLEM
Connection Between Transportation and Assignment Problem An assignment problem is a special case of transportation problem in which m = n, all a i and b j are unity and each is limited to either 0 or 1. Hungarian Method for Solving an Assignment Problem 1. Prepare a square n n matrix. If not, make it square by adding suitable number of dummy ...
The Assignment Problem
The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. In an ... The Hungarian is a (primal-dual) Simplex Method adapted to solve the assignment problem in bi-partite graphs
Assignment problem
The assignment problem arises when $ m = n $ and all $ a _ {i} $ and $ b _ {j} $ are $ 1 $. If all $ a _ {i} $ and $ b _ {j} $ in the transposed problem are integers, then there is an optimal solution for which all $ x _ {ij } $ are integers (Dantzig's theorem on integral solutions of the transport problem).
Assignment Problem and Hungarian Algorithm
This problem is known as the assignment problem. The assignment problem is a special case of the transportation problem, which in turn is a special case of the min-cost flow problem, so it can be solved using algorithms that solve the more general cases. Also, our problem is a special case of binary integer linear programming problem (which is ...
Solving an Assignment Problem
Solving an Assignment Problem Stay organized with collections Save and categorize content based on your preferences. This section presents an example that shows how to solve an assignment problem using both the MIP solver and the CP-SAT solver. Example. In the example there are five workers (numbered 0-4) and four tasks (numbered 0-3). ...
Journal of Physics: Conference Series
solution methods and differences for the classic assignment problem. Assignment problems are concerned with finding a one-to-one distribution to achieve maximum profits and revenues or to reduce the cost or time to complete tasks, where the problem of assignment can be a problem of maximization or a problem of minimization [7, 8].
How to Solve the Assignment Problem: A Complete Guide
Here, we will focus on the steps involved in solving the assignment problem using the Hungarian method, which is the most commonly used and efficient method. Step 1: Set up the cost matrix. The first step in solving the assignment problem is to set up the cost matrix, which represents the cost of assigning a task to an agent.
ES-3: Lesson 9. SOLUTION OF ASSIGNMENT PROBLEM
For an assignment problem of order n x n there would be only n basic variables in the solution because here n assignments are required to be made. This degeneracy problem of solution makes the transportation method computationally inefficient for solving the assignment problem. 9.2.4 Hungarian assignment method
Solution of assignment problems (Hungarian Method)
Step :4 If each row and each column contains exactly one assignment, then the solution is optimal. Example 10.7. Solve the following assignment problem. Cell values represent cost of assigning job A, B, C and D to the machines I, II, III and IV. Solution: Here the number of rows and columns are equal. ∴ The given assignment problem is ...
Successful Strategies for Solving Problems on Assignments
Analysis Stage. Read the problem carefully at least twice, aloud if possible, then restate the problem in your own words. Write down all the information that you know in the problem and separate, if necessary, the "givens" from the "constraints.". Think about what can be done with the information that is given.
Solving Assignment Problem using Linear Programming in Python
In this step, we will solve the LP problem by calling solve () method. We can print the final value by using the following for loop. From the above results, we can infer that Worker-1 will be assigned to Job-1, Worker-2 will be assigned to job-3, Worker-3 will be assigned to Job-2, and Worker-4 will assign with job-4.
An optimal new method to solve the Assignment problem
This and other algorithms like Simplex method, Enumeration method and Transportation method for solving the Assignment Problem assures the prior existence of a matrix of edge weights or costs and ...
PDF UNIT 5 ASSIGNMENT PROBLEMS
Assignment Problems 7 Hungarian Method of Solving an Assignment Problem The steps for obtaining an optimal solution of an assignment problem are as follows: 1. Check whether the given matrix is square. If not, make it square by adding a suitable number of dummy rows (or columns) with 0 cost/time elements. 2.
(PDF) Ones assignment method for solving assignment problems
Assignment problem is an important subject discussed in real physical world. We endeavor in this paper to introduce a new approach to assignment problem namely, ones assignment method, for solving ...
PDF A study on solving Assignment Problem Prof. Ramashankar Prajapati, Dr
The topic of assignment is a critical problem in mathematics and is further explored in the real physical world. We try to implement a replacement method during this paper to solve assignment problems with algorithm and solution steps. By using new method and computing by existing two methods, we analyse a
Assignment Problem: Meaning, Methods and Variations
After reading this article you will learn about:- 1. Means of Association Problem 2. Definition of Assignment Problem 3. Mathematical Formulation 4. Hungarian Method 5. Variations. Meaning of Assignment Problem: An assignment problem is an particular case of transportation problem where the objective is to assign a number of funds to an equal number of active so because at minimise full cost ...
Assignment Method
The method is, however, computationally inefficient for solving the assignment problem due to the solution's degeneracy problem. The Hungarian assignment method problem, developed by mathematician D. Konig, is a faster and more efficient approach to solving assignment problems. It involves determining the cost of making all possible ...
An Alternative Approach for Solving Unbalanced Assignment Problems
modified to solve the assignment problem [3],[4],[5]. Also the signature method for the assignment problem was presented by Balinski [6]. Kore [7] proposed a new approach to solve an unbalanced assignment problem without balancing it. Basirzadeh [8] developed a Hungarian-like method,
35 problem-solving techniques and methods for solving complex problems
Problem-solving methods are primarily designed to help a group or team through a process of first identifying problems and challenges, ... but each individual has a secret "assignment" which makes the collaborative process more challenging. It emphasizes group communication, leadership dynamics, conflict, cooperation, patience and problem ...
3 Ways to Improve Student Problem-Solving
3. Three-Act Tasks: Originally created by Dan Meyer, three-act tasks follow the three acts of a story. The first act is typically called the "setup," followed by the "confrontation" and then the "resolution.". This storyline process can be used in mathematics in which students encounter a contextual problem (e.g., a pool is being ...
A Study on the Weapon-Target Assignment Problem ...
Therefore, in solving weapon-target assignment (WTA) problems, it is crucial to account for the heading errors caused by the launcher's orientation angle. To address this issue, the use of a rotation strategy to align the orientation angle with the target's approach direction can significantly improve the probability of kill (PK) against ...
Frontiers
We also discuss the application of the methods proposed in the TSPs to the quadratic assignment problems and to the problems of ordering things. We introduce a method for solving a quadratic unconstrained binary optimization (QUBO) with the two-way one-hot constraints by dividing the QUBO into parts and solving it with an Ising machine.