the assignment problem is solved by dash

Linear assignment with non-perfect matching

Dec 8, 2020

The linear assignment problem (or simply assignment problem) is the problem of finding a matching between two sets that minimizes the sum of pair-wise assignment costs. This can be expressed as finding a matching (or independent edge set) in a bipartite graph \(G = (U, V, E)\) that minimizes the sum of edge weights. The edge weights may be positive or negative and the bipartite graph does not need to be complete : if there is no edge between two vertices then they cannot be associated. Note that a maximum-weight assignment can be obtained by negating the weights and finding a minimum-weight assignment.

The simplest form of the assignment problem assumes that the bipartite graph is balanced (the two sets of vertices are the same size) and that there exists a perfect matching (in which every vertex has a match). Let \(n\) be the number of elements in each set and let \(C\) be a square matrix of size \(n \times n\) that contains the edge weights. Missing edges are represented by \(\infty\), such that \(C_{i j} < \infty \Leftrightarrow (i, j) \in E\). The assignment problem can then be clearly expressed as an integer linear program : (note that the problem is not actually solved using a general-purpose ILP solver, it is just a convenient framework in which to express the problem)

The constraint that the sum of each row and column is equal to one ensures that each element has exactly one match. However, what happens when the graph is not balanced or does not contain a perfect matching? We cannot enforce the sums to be equal to one. Which problem should be solved?

I recommend reading the tech report “On Minimum-Cost Assignments in Unbalanced Bipartite Graphs” by Lyle Ramshaw and Robert E. Tarjan. I will summarize some of the main points here.

Let us consider a more general, rectangular problem of size \(r \times n\) and assume (without loss of generality) that \(r \le n\). If \(r = n\) then the problem is balanced, if \(r < n\) it is unbalanced.

Clearly an unbalanced probem cannot have a perfect matching, since there will be at least \(n - r\) unmatched elements in the larger set. However, it may be possible to find a matching in which every vertex in the smaller set has a match. This is referred to as a one-sided perfect matching and the optimization problem can be expressed:

The inequality constraints enforce that each element in the smaller set has exactly one match while each element in the larger set has at most one match. Ramshaw and Tarjan outline a method to reduce from an unbalanced problem to a balanced problem while preserving sparsity. A simple alternative is to add \(n - r\) rows of zeros and then exclude these edges from the eventual solution. Most libraries for the assignment problem solve either the balanced or unbalanced version of this problem (see the later section).

However, whether balanced or unbalanced, it may still occur that the constraint set is infeasible, meaning that there does not exist a (one-sided) perfect matching. Let \(\nu(W) \le r\) denote the size of the largest matching in the graph. If \(\nu(W) < r\), then there does not exist a one-sided perfect matching and all possible matchings are imperfect.

Ramshaw and Tarjan actually outline three different versions of the assignment problem:

• perfect matching
• imperfect matching
• minimum-weight matching

The imperfect matching problem is to find the matching of size \(\nu(G)\) with the minimum cost. The minimum-weight matching problem is to find the matching of any size with the minimum cost. If \(\nu(G) = r = n\), then perfect and imperfect matching coincide. Otherwise, when \(\nu(G) < n\), there does not exist a perfect matching.

The imperfect matching problem can be expressed

and the minimum-weight matching problem can be expressed

Ramshaw and Tarjan show that both of these problems can be reduced to finding a perfect matching in a balanced graph. When using linear assignment, we should carefully consider which of the three problems we actually want to solve.

In support of minimum-weight matching

The minimum-weight matching problem is often the most natural choice, since it puts no constraint on the size of the matching. To illustrate the difference between this and the other problems, consider the following balanced problem:

The solution to perfect (or imperfect) matching is to choose -1 and -2 for a total score of -3 and a cardinality of 2. The solution to minimum-weight matching is to choose -4 with a cardinality of 1.

Minimum-weight matching will never select an edge with positive cost: it is better to simply leave it unselected. Edges with zero cost have no impact.

It may be more natural to consider the maximization of positive weights than the minimization of negative costs.

Min-cost imperfect matching with positive weights

Be careful when solving imperfect matching problems with positive edge weights! I would avoid this situation altogether due to the tension that exists between maximizing the number of matches and minimizing the sum of (positive) costs. This may result in the unexpected behaviour that adding an edge to the graph increases the minimum cost. For example, compare the following two problems:

Quick and dirty transformations

Ramshaw and Tarjan above describes some clever techniques to transform imperfect and minimum-weight matching problems into perfect matching problems while preserving sparsity. Here we describe some quick and dirty alternatives.

We can always transform an unbalanced (and therefore imperfect) problem into a balanced problem by adding \(n - r\) rows of zeros. The resulting balanced graph has a perfect matching if and only if the original unbalanced graph had a matching of size \(r\) (in which every vertex in the smaller set is matched).

If we need to solve imperfect matching but we only have a solver for perfect matching, it suffices to replace the infinite edge weights with a large, finite cost (e.g. larger than the total absolute value of all weights). The resulting graph must contain a perfect matching since it is a complete bipartite graph, and each high-cost edge is worth more than all original edges combined. The high-cost edges can be excluded at the end.

Most existing packages either solve perfect, one-sided perfect or imperfect matching. To use one of these solvers for the minimum-weight matching problem, it suffices to replace all positive edges (including infinite edges) with zero. If using a solver that leverages sparsity, it is better to use the technique described by Ramshaw and Tarjan.

Python packages

The table below outlines the different behaviour of several popular packages. The code that was used to determine the behaviour is available as a Jupyter notebook .

Algorithms: The Assignment Problem

One of the interesting things about studying optimization is that the techniques show up in a lot of different areas. The “assignment problem” is one that can be solved using simple techniques, at least for small problem sizes, and is easy to see how it could be applied to the real world.

Assignment Problem

Pretend for a moment that you are writing software for a famous ride sharing application. In a crowded environment, you might have multiple prospective customers that are requesting service at the same time, and nearby you have multiple drivers that can take them where they need to go. You want to assign the drivers to the customers in a way that minimizes customer wait time (so you keep the customers happy) and driver empty time (so you keep the drivers happy).

The assignment problem is designed for exactly this purpose. We start with m agents and n tasks. We make the rule that every agent has to be assigned to a task. For each agent-task pair, we figure out a cost associated to have that agent perform that task. We then figure out which assignment of agents to tasks minimizes the total cost.

Of course, it may be true that m != n , but that’s OK. If there are too many tasks, we can make up a “dummy” agent that is more expensive than any of the others. This will ensure that the least desirable task will be left to the dummy agent, and we can remove that from the solution. Or, if there are too many agents, we can make up a “dummy” task that is free for any agent. This will ensure that the agent with the highest true cost will get the dummy task, and will be idle.

If that last paragraph was a little dense, don’t worry; there’s an example coming that will help show how it works.

There are special algorithms for solving assignment problems, but one thing that’s nice about them is that a general-purpose solver can handle them too. Below is an example, but first it will help to cover a few concepts that we’ll be using.

Optimization Problems

Up above, we talked about making “rules” and minimizing costs. The usual name for this is optimization. An optimization problem is one where we have an “objective function” (which tells us what our goals are) and one or more “constraint functions” (which tell us what the rules are). The classic example is a factory that can make both “widgets” and “gadgets”. Each “widget” and “gadget” earns a certain amount of profit, but it also uses up raw material and time on the factory’s machines. The optimization problem is to determine exactly how many “widgets” and how many “gadgets” to make to maximize profit (the objective) while fitting within the material and time available (the constraints).

If we were to write this simple optimization problem out, it might look like this:

In this case, we have two variables: g for the number of gadgets we make and w for the number of widgets we make. We also have three constraints that we have to meet. Note that they are inequalities; we might not use all the available material or time in our optimal solution.

Just to unpack this a little: in English, the above is saying that we make 45 dollars / euros / quatloos per gadget we make. However, to make a gadget needs 120 lbs of raw material 1, 80 lbs of raw material 2, and 3.8 hours of machine time. So there is a limit on how many gadgets we can make, and it might be a better use of resources to balance gadgets with widgets.

Of course, real optimization problems have many more than two variables and many constraint functions, making them much harder to solve. The easiest kind of optimization problem to solve is linear, and fortunately, the assignment problem is linear.

Linear Programming

A linear program is a kind of optimization problem where both the objective function and the constraint functions are linear. (OK, that definition was a little self-referential.) We can have as many variables as we want, and as many constraint functions as we want, but none of the variables can have exponents in any of the functions. This limitation allows us to apply very efficient mathematical approaches to solve the problem, even for very large problems.

We can state the assignment problem as a linear programming problem. First, we choose to make “i” represent each of our agents (drivers) and “j” to represent each of our tasks (customers). Now, to write a problem like this, we need variables. The best approach is to use “indicator” variables, where xij = 1 means “driver i picks up customer j” and xij = 0 means “driver i does not pick up customer j”.

We wind up with:

This is a compact mathematical way to describe the problem, so again let me put it in English.

First, we need to figure out the cost of having each driver pick up each customer. Then, we can calculate the total cost for any scenario by just adding up the costs for the assignments we pick. For any assignment we don’t pick, xij will equal zero, so that term will just drop out of the sum.

Of course, the way we set up the objective function, the cheapest solution is for no drivers to pick up any customers. That’s not a very good business model. So we need a constraint to show that we want to have a driver assigned to every customer. At the same time, we can’t have a driver assigned to mutiple customers. So we need a constraint for that too. That leads us to the two constraints in the problem. The first just says, if you add up all the assignments for a given driver, you want the total number of assignments for that driver to be exactly one. The second constraint says, if you add up all the assignments to a given customer, you want the total number of drivers assigned to the customer to be one. If you have both of these, then each driver is assigned to exactly one customer, and the customers and drivers are happy. If you do it in a way that minimizes costs, then the business is happy too.

Solving with Octave and GLPK

The GNU Linear Programming Kit is a library that solves exactly these kinds of problems. It’s easy to set up the objective and constraints using GNU Octave and pass these over to GLPK for a solution.

Given some made-up sample data, the program looks like this:

Start with the definition of “c”, the cost information. For this example, I chose to have four drivers and three customers. There are sixteen numbers there; the first four are the cost of each driver to get the first customer, the next four are for the second customer, and the next four are for the third customer. Because we have an extra driver, we add a “dummy” customer at the end that is zero cost. This represents one of the drivers being idle.

The next definition is “b”, the right-hand side of our constraints. There are eight constraints, one for each of the drivers, and one for each of the customers (including the dummy). For each constraint, the right-hand side is 1.

The big block in the middle defines our constraint matrix “a”. This is the most challenging part of taking the mathematical definition and putting it into a form that is usable by GLPK; we have to expand out each constraint. Fortunately, in these kinds of cases, we tend to get pretty patterns that help us know we’re on the right track.

The first line in “a” says that the first customer needs a driver. To see why, remember that in our cost information, the first four numbers are the cost for each driver to get the first customer. With this constraint, we are requiring that one of those four costs be included and therefore that a driver is “selected” for the first customer. The other lines in “a” work similarly; the last four ensure that each driver has an assignment.

Note that the number of rows in “a” matches the number of items in “b”, and the number of columns in “a” matches the number of items in “c”. This is important; GLPK won’t run if this is not true (and our problem isn’t stated right in any case).

Compared to the above, the last few lines are easy.

• “lb” gives the lower bound for each variable.
• “ub” gives the upper bound.
• “ctype” tells GLPK that each constraint is an equality (“strict” as opposed to providing a lower or upper bound).
• “vartype” tells GLPK that these variables are all integers (can’t have half a driver showing up).
• “s” tells GLPK that we want to minimize our costs, not maximize them.

We push all that through a function call to GLPK, and what comes back are two values (along with some other stuff I’ll exclude for clarity):

The first item tells us that our best solution takes 27 minutes, or dollars, or whatever unit we used for cost. The second item tells us the assignments we got. (Note for pedants: I transposed this output to save space.)

This output tells us that customer 1 gets driver 2, customer 2 gets driver 3, customer 3 gets driver 4, and driver 1 is idle. If you look back at the cost data, you can see this makes sense, because driver 1 had some of the most expensive times to the three customers. You can also see that it managed to pick the least expensive pairing for each customer. (Of course, if I had done a better job making up cost data, it might not have picked the least expensive pairing in all cases, because a suboptimal individual pairing might still lead to an overall optimal solution. But this is a toy example.)

Of course, for a real application, we would have to take into consideration many other factors, such as the passage of time. Rather than knowing all of our customers and drivers up front, we would have customers and drivers continually showing up and being assigned. But I hope this simple example has revealed some of the concepts behind optimization and linear programming and the kinds of real-world problems that can be solved.

Assignment Problem: Maximization

There are problems where certain facilities have to be assigned to a number of jobs, so as to maximize the overall performance of the assignment.

The Hungarian Method can also solve such assignment problems , as it is easy to obtain an equivalent minimization problem by converting every number in the matrix to an opportunity loss.

The conversion is accomplished by subtracting all the elements of the given matrix from the highest element. It turns out that minimizing opportunity loss produces the same assignment solution as the original maximization problem.

• Unbalanced Assignment Problem
• Multiple Optimal Solutions

Example: Maximization In An Assignment Problem

At the head office of www.universalteacherpublications.com there are five registration counters. Five persons are available for service.

How should the counters be assigned to persons so as to maximize the profit ?

Here, the highest value is 62. So we subtract each value from 62. The conversion is shown in the following table.

On small screens, scroll horizontally to view full calculation

Now the above problem can be easily solved by Hungarian method . After applying steps 1 to 3 of the Hungarian method, we get the following matrix.

Draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix.

Select the smallest element from all the uncovered elements, i.e., 4. Subtract this element from all the uncovered elements and add it to the elements, which lie at the intersection of two lines. Thus, we obtain another reduced matrix for fresh assignment. Repeating step 3, we obtain a solution which is shown in the following table.

Final Table: Maximization Problem

Use Horizontal Scrollbar to View Full Table Calculation

The total cost of assignment = 1C + 2E + 3A + 4D + 5B

Substituting values from original table: 40 + 36 + 40 + 36 + 62 = 214.

Share This Article

Operations Research Simplified Back Next

Goal programming Linear programming Simplex Method Transportation Problem

• MapReduce Algorithm

Linear Programming using Pyomo

• Networking and Professional Development for Machine Learning Careers in the USA
• Predicting Employee Churn in Python
• Airflow Operators

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

You May Also Like

Solving Linear Programming using Python PuLP

Let’s Start with Pandas Library: Introduction and Installation

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

Related Topics

Privacy Policy , Terms and Conditions , DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.

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:

Q2 . Write a program the converts the input Celsius degree into its equivalent Fahrenheit degree. Use the formula: F = (9/5) *C+32.

Q3 . Write a program that converts the input dollar to its peso exchange rate equivalent.  Assume that the present exchange rate is 51.50 pesos against the dollar. Then display the peso equivalent exchange rate.

Q4 . Write a program that converts an input inch(es) into its equivalent centimeters. Take note that one inch is equivalent to 2.54cms.

Q5 . Write a program that exchanges the value of two variables: x and y.  The output must be: the value of variable y will become the value of variable x, and vice versa.

Q6 . Design a program to find the circumference of a circle. Use the formula: C=2πr, where π is approximately equivalent 3.1416.

Q7 . Write a program that takes as input the purchase price of an item (P), its expected number of years of service (Y) and its expected salvage value (S). Then outputs the yearly depreciation for the item (D). Use the formula: D = (P – S) Y.

Q8 . Swapping of 2 variables without using temporary (or 3 rd variable).

Q9 . Determine the most economical quantity to be stocked for each product that a manufacturing company has in its inventory: This quantity, called economic order quantity (EOQ) is calculated as follows: EOQ=2rs/1 where: R= total yearly production requirement S=set up cost per order I=inventory carrying cost per unit.

Q10 . Write a program to compute the radius of a circle. Derive your formula from the given equation: A=πr², then display the output.

• ← Solved Assignment Problems in Java (with Algorithm and Flowchart)
• Simple if statement in C →

Gopal Krishna

Hey Engineers, welcome to the award-winning blog,Engineers Tutor. I'm Gopal Krishna. a professional engineer & blogger from Andhra Pradesh, India. Notes and Video Materials for Engineering in Electronics, Communications and Computer Science subjects are added. "A blog to support Electronics, Electrical communication and computer students".

You May Also Like

Selection sort algorithm, problem solving and algorithms, flowchart and algorithm, leave a reply cancel reply.

Your email address will not be published. Required fields are marked *

The assignment problem revisited

• Original Paper
• Published: 16 August 2021
• Volume 16 , pages 1531–1548, ( 2022 )

Cite this article

• Carlos A. Alfaro   ORCID: orcid.org/0000-0001-9783-8587 1 ,
• Sergio L. Perez 2 ,
• Carlos E. Valencia 3 &
• Marcos C. Vargas 1  

1040 Accesses

4 Citations

4 Altmetric

Explore all metrics

First, we give a detailed review of two algorithms that solve the minimization case of the assignment problem, the Bertsekas auction algorithm and the Goldberg & Kennedy algorithm. It was previously alluded that both algorithms are equivalent. We give a detailed proof that these algorithms are equivalent. Also, we perform experimental results comparing the performance of three algorithms for the assignment problem: the \(\epsilon \) - scaling auction algorithm , the Hungarian algorithm and the FlowAssign algorithm . The experiment shows that the auction algorithm still performs and scales better in practice than the other algorithms which are harder to implement and have better theoretical time complexity.

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

Access this article

Subscribe and save.

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

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

Some results on an assignment problem variant

Integer Programming

A Full Description of Polytopes Related to the Index of the Lowest Nonzero Row of an Assignment Matrix

Bertsekas, D.P.: The auction algorithm: a distributed relaxation method for the assignment problem. Annal Op. Res. 14 , 105–123 (1988)

Article   MathSciNet   Google Scholar  

Bertsekas, D.P., Castañon, D.A.: Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Comput. 17 , 707–732 (1991)

Article   Google Scholar  

Bertsekas, D.P.: Linear network optimization: algorithms and codes. MIT Press, Cambridge, MA (1991)

MATH   Google Scholar  

Bertsekas, D.P.: The auction algorithm for shortest paths. SIAM J. Optim. 1 , 425–477 (1991)

Bertsekas, D.P.: Auction algorithms for network flow problems: a tutorial introduction. Comput. Optim. Appl. 1 , 7–66 (1992)

Bertsekas, D.P., Castañon, D.A., Tsaknakis, H.: Reverse auction and the solution of inequality constrained assignment problems. SIAM J. Optim. 3 , 268–299 (1993)

Bertsekas, D.P., Eckstein, J.: Dual coordinate step methods for linear network flow problems. Math. Progr., Ser. B 42 , 203–243 (1988)

Bertsimas, D., Tsitsiklis, J.N.: Introduction to linear optimization. Athena Scientific, Belmont, MA (1997)

Google Scholar  

Burkard, R., Dell’Amico, M., Martello, S.: Assignment Problems. Revised reprint. SIAM, Philadelphia, PA (2011)

Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for network problems. SIAM J. Comput. 18 (5), 1013–1036 (1989)

Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum flow problem. J. Assoc. Comput. Mach. 35 , 921–940 (1988)

Goldberg, A.V., Tarjan, R.E.: Finding minimum-cost circulations by successive approximation. Math. Op. Res. 15 , 430–466 (1990)

Goldberg, A.V., Kennedy, R.: An efficient cost scaling algorithm for the assignment problem. Math. Programm. 71 , 153–177 (1995)

MathSciNet   MATH   Google Scholar  

Goldberg, A.V., Kennedy, R.: Global price updates help. SIAM J. Discr. Math. 10 (4), 551–572 (1997)

Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2 , 83–97 (1955)

Kuhn, H.W.: Variants of the Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2 , 253–258 (1956)

Lawler, E.L.: Combinatorial optimization: networks and matroids, Holt. Rinehart & Winston, New York (1976)

Orlin, J.B., Ahuja, R.K.: New scaling algorithms for the assignment ad minimum mean cycle problems. Math. Programm. 54 , 41–56 (1992)

Ramshaw, L., Tarjan, R.E., Weight-Scaling Algorithm, A., for Min-Cost Imperfect Matchings in Bipartite Graphs, : IEEE 53rd Annual Symposium on Foundations of Computer Science. New Brunswick, NJ 2012 , 581–590 (2012)

Zaki, H.: A comparison of two algorithms for the assignment problem. Comput. Optim. Appl. 4 , 23–45 (1995)

Download references

Acknowledgements

This research was partially supported by SNI and CONACyT.

Author information

Authors and affiliations.

Banco de México, Mexico City, Mexico

Carlos A. Alfaro & Marcos C. Vargas

Mountain View, CA, 94043, USA

Sergio L. Perez

Departamento de Matemáticas, CINVESTAV del IPN, Apartado postal 14-740, 07000, Mexico City, Mexico

Carlos E. Valencia

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Carlos A. Alfaro .

Ethics declarations

Conflict of interest.

There is no conflict of interest.

Additional information

Publisher's note.

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

The authors were partially supported by SNI and CONACyT.

Rights and permissions

Reprints and permissions

About this article

Alfaro, C.A., Perez, S.L., Valencia, C.E. et al. The assignment problem revisited. Optim Lett 16 , 1531–1548 (2022). https://doi.org/10.1007/s11590-021-01791-4

Download citation

Received : 26 March 2020

Accepted : 03 August 2021

Published : 16 August 2021

Issue Date : June 2022

DOI : https://doi.org/10.1007/s11590-021-01791-4

Share this article

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

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

Provided by the Springer Nature SharedIt content-sharing initiative

• Assignment problem
• Bertsekas auction algorithm
• Combinatorial optimization and matching
• Find a journal
• Publish with us
• Track your research

Unbalanced Assignment Problem: Definition, Formulation, and Solution Methods

Table of Contents

Are you familiar with the assignment problem in Operations Research (OR)? This problem deals with assigning tasks to workers in a way that minimizes the total cost or time needed to complete the tasks. But what if the number of tasks and workers is not equal? In this case, we face the Unbalanced Assignment Problem (UAP). This blog will help you understand what the UAP is, how to formulate it, and how to solve it.

What is the Unbalanced Assignment Problem?

The Unbalanced Assignment Problem is an extension of the Assignment Problem in OR, where the number of tasks and workers is not equal. In the UAP, some tasks may remain unassigned, while some workers may not be assigned any task. The objective is still to minimize the total cost or time required to complete the assigned tasks, but the UAP has additional constraints that make it more complex than the traditional assignment problem.

Formulation of the Unbalanced Assignment Problem

To formulate the UAP, we start with a matrix that represents the cost or time required to assign each task to each worker. If the matrix is square, we can use the Hungarian algorithm to solve the problem. But when the matrix is not square, we need to add dummy tasks or workers to balance the matrix. These dummy tasks or workers have zero costs and are used to make the matrix square.

Once we have a square matrix, we can apply the Hungarian algorithm to find the optimal assignment. However, we need to be careful in interpreting the results, as the assignment may include dummy tasks or workers that are not actually assigned to anything.

Solutions for the Unbalanced Assignment Problem

Besides the Hungarian algorithm, there are other methods to solve the UAP, such as the transportation algorithm and the auction algorithm. The transportation algorithm is based on transforming the UAP into a transportation problem, which can be solved with the transportation simplex method. The auction algorithm is an iterative method that simulates a bidding process between the tasks and workers to find the optimal assignment.

In summary, the Unbalanced Assignment Problem is a variant of the traditional Assignment Problem in OR that deals with assigning tasks to workers when the number of tasks and workers is not equal. To solve the UAP, we need to balance the matrix by adding dummy tasks or workers and then apply algorithms such as the Hungarian algorithm, the transportation algorithm, or the auction algorithm. Understanding the UAP can help businesses and organizations optimize their resource allocation and improve their operational efficiency.

How useful was this post?

Click on a star to rate it!

Average rating 1.5 / 5. Vote count: 2

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

• Branch and Bound Tutorial
• Backtracking Vs Branch-N-Bound
• 0/1 Knapsack
• 8 Puzzle Problem
• Job Assignment Problem
• N-Queen Problem
• Travelling Salesman Problem
• Branch and Bound Algorithm
• Introduction to Branch and Bound - Data Structures and Algorithms Tutorial
• 0/1 Knapsack using Branch and Bound
• Implementation of 0/1 Knapsack using Branch and Bound
• 8 puzzle Problem using Branch And Bound

Job Assignment Problem using Branch And Bound

• N Queen Problem using Branch And Bound
• Traveling Salesman Problem using Branch And Bound

Let there be N workers and N jobs. Any worker can be assigned to perform any job, incurring some cost that may vary depending on the work-job assignment. It is required to perform all jobs by assigning exactly one worker to each job and exactly one job to each agent in such a way that the total cost of the assignment is minimized.

Let us explore all approaches for this problem.

Solution 1: Brute Force  

We generate n! possible job assignments and for each such assignment, we compute its total cost and return the less expensive assignment. Since the solution is a permutation of the n jobs, its complexity is O(n!).

Solution 2: Hungarian Algorithm  

The optimal assignment can be found using the Hungarian algorithm. The Hungarian algorithm has worst case run-time complexity of O(n^3).

Solution 3: DFS/BFS on state space tree  

A state space tree is a N-ary tree with property that any path from root to leaf node holds one of many solutions to given problem. We can perform depth-first search on state space tree and but successive moves can take us away from the goal rather than bringing closer. The search of state space tree follows leftmost path from the root regardless of initial state. An answer node may never be found in this approach. We can also perform a Breadth-first search on state space tree. But no matter what the initial state is, the algorithm attempts the same sequence of moves like DFS.

Solution 4: Finding Optimal Solution using Branch and Bound  

The selection rule for the next node in BFS and DFS is “blind”. i.e. the selection rule does not give any preference to a node that has a very good chance of getting the search to an answer node quickly. The search for an optimal solution can often be speeded by using an “intelligent” ranking function, also called an approximate cost function to avoid searching in sub-trees that do not contain an optimal solution. It is similar to BFS-like search but with one major optimization. Instead of following FIFO order, we choose a live node with least cost. We may not get optimal solution by following node with least promising cost, but it will provide very good chance of getting the search to an answer node quickly.

There are two approaches to calculate the cost function:  

• For each worker, we choose job with minimum cost from list of unassigned jobs (take minimum entry from each row).
• For each job, we choose a worker with lowest cost for that job from list of unassigned workers (take minimum entry from each column).

In this article, the first approach is followed.

Let’s take below example and try to calculate promising cost when Job 2 is assigned to worker A. 

Since Job 2 is assigned to worker A (marked in green), cost becomes 2 and Job 2 and worker A becomes unavailable (marked in red). 

Now we assign job 3 to worker B as it has minimum cost from list of unassigned jobs. Cost becomes 2 + 3 = 5 and Job 3 and worker B also becomes unavailable. 

Finally, job 1 gets assigned to worker C as it has minimum cost among unassigned jobs and job 4 gets assigned to worker D as it is only Job left. Total cost becomes 2 + 3 + 5 + 4 = 14. 

Below diagram shows complete search space diagram showing optimal solution path in green. 

Complete Algorithm:  

Below is the implementation of the above approach:

Time Complexity: O(M*N). This is because the algorithm uses a double for loop to iterate through the M x N matrix.  Auxiliary Space: O(M+N). This is because it uses two arrays of size M and N to track the applicants and jobs.

Please Login to comment...

Similar reads.

• Branch and Bound

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

• New Hampshire
• North Carolina
• Pennsylvania
• West Virginia
• Online hoaxes
• Coronavirus
• Health Care
• Immigration
• Environment
• Foreign Policy
• Kamala Harris
• Donald Trump
• Mitch McConnell
• Hakeem Jeffries
• Ron DeSantis
• Tucker Carlson
• Sean Hannity
• Rachel Maddow
• PolitiFact Videos
• 2024 Elections
• Mostly True
• Mostly False
• Pants on Fire
• Biden Promise Tracker
• Trump-O-Meter
• Latest Promises
• Our Process
• Who pays for PolitiFact?
• Advertise with Us
• Suggest a Fact-check
• Corrections and Updates
• Newsletters

Stand up for the facts!

Our only agenda is to publish the truth so you can be an informed participant in democracy. We need your help.

I would like to contribute

• Border Security
• Republican National Committee

Vice President Kamala Harris waves as she boards Air Force Two after a campaign event July 23, 2024, in Milwaukee. (AP)

'Border czar'? Kamala Harris assigned to tackle immigration's causes, not border security

If your time is short.

In March 2021, President Joe Biden tasked Vice President Kamala Harris with working alongside officials in Guatemala, El Salvador and Honduras to address the issues driving people to leave those countries and come to the United States.

The Biden-Harris administration said it would focus on five key issues: economic insecurity, corruption, human rights, criminal gang violence and gender-based violence.

Border security and management is the Homeland Security secretary’s responsibility.

Vice President Kamala Harris might soon get a new official title: 2024 Democratic presidential nominee. In the meantime, Republicans have revived a title they gave her in 2021: "border czar." 

Claims that President Joe Biden named Harris the "border czar" and that she is responsible for overseeing U.S. border enforcement gained prominence at the Republican National Convention as the party sought to link her to his immigration policy. 

The refrain intensified once Biden dropped out of the race and endorsed Harris. It was echoed in ads and by Trump campaign surrogates, including Ohio Sen. J.D. Vance , the Republican vice presidential nominee.

"Here’s Biden appointing Kamala Harris to be his border czar to deal with illegal immigration," a narrator says in a video the Republican National Committee posted on its X account, @GOP. "And here are a record number of illegal immigrants — 10 million and counting — flooding over the border after Harris was put in charge of stopping illegal immigration."

We’ve repeatedly fact-checked claims about the number of people entering the U.S. illegally under Biden. The federal data tracks how many times officials encountered a person trying to cross the southern border, but it doesn’t reflect the number of people let in. And if one person tries to cross the border multiple times, that counts as multiple encounters, even if it’s the same person. 

For this fact-check, we’re focused on the scope of Harris’ border responsibilities. 

"Border Czar Kamala Harris' reversal of President Trump's immigration policies has created an unprecedented and illegal immigration, humanitarian and national security crisis on our southern border," Trump campaign National Press Secretary Karoline Leavitt told PolitiFact in a statement. 

But Biden didn’t put Harris in charge of overseeing border security.

In a meeting with Harris in March 2021 , Biden said Harris would lead U.S. diplomatic efforts and work with officials in Mexico, Guatemala, El Salvador and Honduras to stem migration to the U.S. Biden said that when he was vice president, he "got a similar assignment" and that the Obama administration secured $700 million to help countries in Central America.

"One of the ways we learned is that if you deal with the problems in country, it benefits everyone. It benefits us, it benefits the people, and it grows the economies there," Biden said then.

Biden asked Harris "to be the chief diplomatic officer with Central American countries" and address the root causes that make people leave their home countries, said Michelle Mittelstadt, communications director for the Migration Policy Institute, a nonpartisan think tank. 

Managing the border "has always been" the Homeland Security secretary’s role, Mittelstadt said.

Biden tasked Harris with addressing the root causes influencing people’s decisions to migrate to the United States.

"I’ve asked her … to lead our efforts with Mexico and the Northern Triangle and the countries that help — are going to need help in stemming the movement of so many folks, stemming the migration to our southern border," Biden said in March 2021.

Biden held a similar role as vice president to former President Barack Obama. In a 2015 New York Times opinion piece, Biden said he would work with the Northern Triangle’s leaders on security, anti-corruption and investment efforts in the region.

"Donald Trump’s administration didn’t really sustain this strategy, but what Harris sought to revive in 2021 ran along the same lines," said Adam Isacson, defense oversight director at Washington Office on Latin America, a group advocating for human rights in the Americas. 

Within weeks of Biden’s remarks about Harris’ role, Republicans including Texas Gov. Greg Abbott and Rep. Steve Scalise, R-La., began calling Harris the " border czar " often in tandem with pointing out she had not yet been to the border.

In April 2021, when a reporter asked Harris whether she would visit the border, she said that her role is addressing the factors that make people leave their home countries, not managing the border.

Featured Fact-check

"The president has asked (Homeland Security) Secretary (Alejandro) Mayorkas to address what is going on at the border. And he has been working very hard at that, and it’s showing some progress because of his hard work," Harris said at an event . "I have been asked to lead the issue of dealing with root causes in the Northern Triangle, similar to what the then-vice president did many years ago."

Harris said she’d focus on economic struggles, violence, corruption and food insecurity in the countries. 

In June 2021, Harris visited El Paso, Texas, with Mayorkas. They outlined their responsibilities to reporters. Harris said she was addressing "the root causes of migration, predominantly out of Central America," and Mayorkas said, "It is my responsibility as the Secretary of Homeland Security to address the security and management of our border."

But this distinction didn’t stop critics from linking Harris with U.S.-Mexico border security. 

"The administration’s messaging on this in mid-2021 was not as clear as it should have been," Isacson said. "But at no time did Harris or the White House state that her duties included the U.S.-Mexico border, or border security."

Immigration experts said it’s hard to measure Harris’ success in her role, and that a "root causes" approach implies that the results will be seen long term, not immediately.

In July 2021, the administration published a strategy , with Harris writing the lead message, for confronting the factors that drive migration in Central America. The plan focused on economic insecurity, corruption, human rights, criminal gang violence and gender-based violence.

In March 2024, the administration said it secured more than $5.2 billion in private sector investments to the region. However, only about $1 billion has been distributed, the Partnership for Central America, a group working with the administration, reported .

The White House said the investments have generated more than 70,000 new jobs in Guatemala, Honduras and El Salvador, provided job training to 1 million people and expanded digital access to 4.5 million people. 

"Still, her engagement on this issue has been sporadic," Isacson said. "She has not traveled very often to the region or otherwise sought to make ‘root causes in Central America’ a central theme of her vice presidency."

Illegal immigration at the U.S. southern border from Guatemala, Honduras and El Salvador has dropped since 2021. Encounters with people from other countries, Venezuela, have risen . 

"But it’s hard to prove that U.S. assistance is a central reason" for the Northern Triangle countries’ decline, Isacson said.

The issues pushing people to leave Central American countries "are extremely complex and require deep restructuring of so much in those societies," said Cecilia Menjivar, a sociology professor at the University of California, Los Angeles who specializes on immigration. "So it’s very difficult for one person to change all that, even if it is a powerful person."

Immigration patterns at the U.S.-Mexico border have more to do with conditions in Latin American countries than "any U.S. policy," Mittelstadt said. 

For example, a humanitarian crisis in Venezuela has displaced nearly 8 million people since 2014, according to the United Nations. Political, economic and security crises in Cuba, Nicaragua, Haiti and Ecuador have also led to more migration from these countries, Mittelstadt said. 

In contrast, immigration encounters with people from El Salvador have dropped in past years, partly because of the country’s crime crackdown .

The Republican National Committee said Biden appointed Harris "to be his border czar to deal with illegal immigration...Harris was put in charge of stopping illegal immigration."

Biden tasked Harris with addressing the root causes that drive migration to the United States. He did not task her with controlling who and how many people enter the southern U.S. border. That's the Homeland Security secretary’s responsibility.

Experts say that seeing the results of addressing root causes driving people out of Guatemala, El Salvador and Honduras  — violence, economic insecurity and corruption — takes time.

The statement contains an element of truth, but it ignores critical facts that would give a different impression. We rate it Mostly False.

Read About Our Process

The Principles of the Truth-O-Meter

Our Sources

Truth Social, post , July 22, 2024

The Hill, House Republicans tee up vote condemning Harris as ‘border czar’ , July 23, 2024

C-SPAN, Sen. J.D. Vance campaign rally in Radford, Virginia , July 22, 2024

GOP, post on X , July 21, 2024

PolitiFact, Francis Suarez’s misleading claim about millions of migrants getting free cellphones, plane tickets , July 28, 2024

PolitiFact, There aren’t 20 million to 30 million immigrants in the U.S. illegally, as Sen. Marco Rubio claimed , June 11, 2024

The White House, Remarks by President Biden and Vice President Harris in a meeting on immigration , March 24, 2021

PolitiFact, Central America and the root causes of migration to the US , June 7, 2021

The New York Times, Joe Biden: A Plan for Central America , Jan. 29, 2015

The White House, Remarks by Vice President Harris at virtual roundtable of experts on the Northern Triangle , April 14, 2021

The White House, Remarks by Vice President Harris, Secretary of Homeland Security Mayorkas, Chairman Durbin, and Representative Escobar in press gaggle , June 25, 2021

Fox News, Obama-era DHS secretary: 'There's a real problem' when you have 'bipartisan outrage' , July 23, 2024

The White House, FACT SHEET: Strategy to address the root causes of migration in Central America , July 29, 2021

The White House, FACT SHEET: Vice President Harris announces public-private partnership has generated more than $5.2 billion in private sector commitments for Northern Central America , March 25, 2024

Migration Policy Institute, Shifting patterns and policies reshape migration to U.S.-Mexico border in major ways in 2023 , October 2023

United Nations High Commissioner for Refugees, Venezuela crisis explained , April 17, 2024

PolitiFact, Donald Trump fact-check: 2024 RNC speech in Milwaukee full of falsehoods about immigrants, economy , July 19, 2024

CBS News, The facts about Kamala Harris' role on immigration in the Biden administration , July 23, 2024

Email interview, Michelle Mittelstadt, communications director for the Migration Policy Institute, July 22, 2024

Email interview, Adam Isacson, defense oversight director at Washington Office on Latin America, July 22, 2024

Email interview, Henry Ziemer, research associate for the Center for Strategic and International Studies, July 22, 2024

Email interview, Cecilia Menjivar, sociology professor at the University of California, Los Angeles, July 22, 2024

Statement, Karoline Leavitt,  Trump campaign national press secretary, July 23, 2024

Browse the Truth-O-Meter

More by maria ramirez uribe.

'Border czar'? Kamala Harris assigned to tackle immigration's causes, not border security

Support independent fact-checking. Become a member!

'Border czar' or not, Kamala Harris ran from her job to get the border under control

Democrats say kamala harris was merely assigned to address immigration’s 'root causes.' that's not what the record shows..

It’s not easy to discern what Kamala Harris accomplished in her tenure as vice president.

The Onion once described this conundrum with the headline, “White House urges Kamala Harris to sit at computer all day in case emails come through.”

Even Harris’s own people complained to CNN in 2021 that the West Wing — Joe Biden and staff — had turned her into a potted palm .

Now that Harris has risen to the top of the Democrats’ presidential ticket, her defenders in the party and back-fillers in the media have undertaken a less complicated task.

They’re telling us what Harris didn’t do.

She didn’t oversee the border. 

Harris was never the 'border czar,' media claims

To put it more bluntly, they claim that she didn’t oversee the disaster that is the Biden-Harris border policy. She was never the “border czar.” 

Sure. Whatever you say. 

In his day, Arizona Sen. John McCain used to say the Democrats “ have more czars than the Romanovs .”

Democratic lawmakers are striding to the podium to hammer back any notion that Harris was ever the “border czar.” Republicans concocted the whole thing, they fume.

National media joined that chorus with their obedient little fact checks, until their knickers got caught in the ring washer. 

Axios, for instance, promoted its own piece this way: “The Trump campaign and Republicans have tagged Harris repeatedly with the ‘border czar’ title — which she never actually had.”

Then readers pointed out that Axios, itself, had called Harris the “border czar” and also ran a headline in 2021 that read, “ Biden puts Harris in charge of border crisis .”

News sites often make excuses for Kamala Harris

This caused all sorts of scrambling at Axios on Wednesday as it updated one story to say it had “incorrectly” called Harris the border czar, Fox News reported.

Soon after, one astute web commentator exclaimed, “Holy s---! Axios is literally throwing itself under the bus to rewrite history for Kamala.”

But Axios wasn’t alone. 

Stories at The New York Times, USA Today, Newsweek and others said Harris was focused on the root causes of illegal immigration in the so-called Northern Triangle — the countries of El Salvador, Guatemala and Honduras where multitudes of people are fleeing violence and poverty for the United States.

Harris doesn't the scare the GOP: But Mark Kelly should

Hers was a diplomatic mission in central America, not a focus on the U.S.-Mexico border.

The unspoken subtext here is that Harris cannot be held responsible for the record-high illegal immigration that happened under the Biden White House. 

To visualize the border crisis that Biden & Co. created, you can go to the pages of The New York Times to see bar graphs that rise like skyscrapers after the Trump administration, depicting record border apprehensions in the Biden years of 2022 and 2023.

Check the record: This clearly was the VP's job

Understandably, that is now a key line of attack for Republicans. 

So, what do Democrats do?

They deny Harris is culpable. They deny she was the “border czar.”

The problem is that one of their own, former Vice President Al Gore, invented this thing called the internet (so I’m told), that has dutifully kept a record of what actually went down in 2021 when Joe Biden handed the border portfolio to Kamala Harris.

Here’s how NBC News reported that moment on March 24, 2021:

“ Biden tasks Harris with 'stemming the migration' on southern border : The vice president is expected to focus on both curbing the current flow of migrants and coordinating with countries in the region to address the root causes of migration.”

NBC ran that headline because a “senior administration official” told them, “Harris’ role would focus on ‘two tracks’: both curbing the current flow of migrants and implementing a long-term strategy that addresses the root causes of migration.” 

This presents yet another problem for today’s Democrats and the Harris campaign.

Harris didn't want the assignment and quit

If they keep going down this trail of “Kamala Harris was never the border czar,” they’re not going to like where it ends. 

Pretty soon Republicans will direct voters back to CNN’s potted palm story and to what Biden’s team actually thought of Harris. 

“Worn out by what they see as entrenched dysfunction and lack of focus, key West Wing aides have largely thrown up their hands at Vice President Kamala Harris and her staff — deciding there simply isn’t time to deal with them right now, especially at a moment when President Joe Biden faces quickly multiplying legislative and political concerns.”

One of those multiplying concerns was the southern border. And Biden needed help.

But as CNN reported, Harris fled the assignment. 

“Harris herself has said she didn’t want to be assigned to manage the border, aware that it was a no-win political situation that would only sandbag her in the future.”

Americans might read that and logically think, why would we expect a President Kamala Harris to solve a serious national problem at the border when it so obviously grips her with fear?

From there, this discussion leads to the disastrous Lester Holt interview , in which the NBC anchor pressed Harris on why, she herself, had never been to the border. 

Her answer?

“And I haven’t been to Europe.”

Expect Trump to put her words on repeat

You could hear jaws drop all across America. You could also hear them hit the table at the White House. As CNN recounted, the West Wing was “annoyed.” 

Which brings us back to today and the 2024 race for president.

It won’t be long now before the Trump rallies start putting the Lester Holt-Kamala Harris interview on a loop to the rhythms of Three Dog Night: 

“ Well, I never been to heaven

But I been to Oklahoma

Oh, they tell me I was born there

But I really don’t remember 

In Oklahoma, not Arizona

What does it matter?

What does it matter?” 

Phil Boas is an editorial columnist with The Arizona Republic. Email him at [email protected] .

LIVE: Paris gets the Olympics underway with a floating extravaganza on the Seine

Biden asked Harris to tackle the 'root causes' of migration. Here's what happened after that.

President Joe Biden tapped Kamala Harris to tackle the daunting issue of immigration in March 2021, but the vice president’s public-facing work on addressing the root causes of migration largely evaporated within months, according to an NBC News analysis of public documents, U.S. aid disbursements and Harris’ travel schedule.

Harris traveled to Mexico in June 2021 to sign an agreement that has led to a commitment of $4 billion in direct assistance and over $5.2 billion in private-public investment from the U.S. But she has not visited the southern border, or the countries to its south, since January 2022. And despite requests from Mexico for more investment, her “Root Causes Strategy” made no new financial commitments.

When Harris became Biden’s “ border czar ,” as critics called her, the administration was under pressure from both sides to address the rising number of migrants — particularly unaccompanied children — crossing the border and landing in poor conditions in U.S. custody. On March 24, 2021, Biden took the stage at the White House and seemed to hand the keys on the issue over to his vice president.

“The vice president has agreed — among the multiple other things that I have her leading, and I appreciate it — agreed to lead our diplomatic effort to work with those nations to accept returnees and enhance migration enforcement at their borders,” Biden said.

In accepting the task, Harris made her role more specific, describing largely diplomatic responsibilities. “I look forward to engaging in diplomacy with government, with the private sector, with civil society and the leaders of each in El Salvador, Guatemala and Honduras to strengthen democracy and the rule of law and ensure shared prosperity in the region. We will collaborate with Mexico and other countries throughout the Western Hemisphere.”

Biden administration officials have pointed to those remarks in rejecting criticism that Harris did not solve the crisis at the border, where there have been record crossings under Biden. They say her job was to focus on working with countries in the region to address root causes, and they reject the mocking title “border czar.” 

The Border Patrol union says Harris did not deliver on any of her immigration-related assignments. 

When Harris’ name is mentioned at the border, “it’s a lot of eye rolls,” said Jon Anfinsen, national executive vice president of the National Border Patrol Council, the Border Patrol union. 

“I would ask what has she done in terms of solving the root causes. This has been a goal of hers for this many years. What’s changed? I would argue it’s not improved; it has only gotten worse,” Anfinsen said. “Shortly around that period of time, it kind of just went away, and you didn’t hear it.”

But Daniel Suvor, who was chief of policy for Harris from 2014 to 2017 while she was California's attorney general, said he was unsurprised she was tapped to address root causes of migration in Central America.

“She’s been interested in Central America for some time, and she has built up a wide range of relationships down there,” Suvor said.

Suvor said Harris' connections in Latin America stemmed from her work as attorney general to combat drug trafficking by transnational criminal organizations and her trips to Mexico City to meet with foreign officials.

“She understood all the way back then that we needed to work with the Mexican government, El Salvador, Honduran, Guatemalan government, to take on the cartels.”

'Don't come'

An NBC News review found that her travel to address root issues in the region was largely limited to June 2021, with one trip to the border in El Paso, Texas, and another to Mexico and Guatemala. She made one additional trip to Honduras in January 2022. 

Her work in Guatemala may have been most memorable. It was where she faced criticism from immigration groups for telling migrants “don’t come” to the U.S. 

But her work in Mexico was arguably the most significant. It was there that Mexico and the U.S. signed a memorandum of understanding to “strengthen development cooperation in northern Central America ... to exchange knowledge, experiences, assets, and resources to address the root causes of irregular migration in northern Central America,” according to a description of the agreement by the State Department.

The agreement sent funds from the U.S. Agency for International Development, coupled with those from the Mexican Agency for International Development Cooperation, to help people in Central America. Since then, the U.S. has stayed on track to meet its commitment of $4 billion to address root causes, but Harris has also been able to solicit significant help from private companies, which have invested $5.2 billion in the region since 2021.

Those investments have funded entrepreneurs, ensured labor rights, strengthened food security and launched “19 projects in Guatemala, El Salvador, and Honduras across sectors, including financial inclusion, healthcare, climate finance, and affordable housing,” according to the White House.

Since 2021, however, the Root Causes Strategy has made no new commitments, despite Mexican pleas for more direct investment from the U.S., not just from U.S. companies.

Mexican President Andrés Manuel López Obrador said in May 2022 that the private investment strategy is too slow.

“ We are convincing the government of the United States to invest with readiness,” he said at a news conference. “They have a very special system — they think that it’s enough to promote private investments. That if plants, factories are installed in Central America, then employment will be generated. … That is good, but that takes time.”

Harris made one more trip to Central America after 2021, to attend the inauguration of Honduran President Xiomara Castro in January 2022. According to the White House, Harris talked to her about “combating corruption and gender-based violence as a way to address the root causes of migration.”

Since then, she has held two meetings in Washington, one with López Obrador in July 2022 and the other most recently with Guatemalan President Bernardo Arévalo in March.

A White House official defended Harris’ record and said her work is ongoing. “Vice President Harris continues to lead the effort to address the root causes of migration from Honduras, Guatemala, and El Salvador, including by generating more than $5.2 billion in investments into the region to give people economic opportunity at home. These investments are creating jobs and have connected more than 4.5 million people to the internet and brought more than 2.5 million people into the formal financial system.”

“Under the Vice President’s leadership, the Biden-Harris Administration continues to implement the Root Causes Strategy. As a part of this strategy, the Administration is on track to meet its commitment to provide $4 billion to the region over four years and continues to work to combat corruption, reduce violence, and empower women,” the White House official wrote.

Think tanks that study immigration and international non-governmental organizations have also questioned the impact of Harris’ work in addressing immigration.

“She had a very narrow mandate, which was to be the diplomatic representative in Central America at the time when most unauthorized immigration was coming from Central America,” said Andrew Selee, president of the Migration Policy Institute, a nonpartisan think tank based in Washington.

Since 2021, immigration from the Central American countries of Guatemala, El Salvador and Honduras, once the leaders in illegal immigration across the southwest border, has fallen from 86,089 in March 2021 to 25,015 in June 2024, according to Customs and Border Protection data. 

But immigration experts point out that the decline is most likely driven by other factors, including U.S. policies restricting asylum at the border and an increase in Mexican interdictions of U.S.-bound migrants. And during that time, migration from countries like Venezuela and China — where Harris has no involvement in immigration discussions — has mounted.

Selee said USAID took over the money the U.S. sent to Central America for development while Harris stayed focused on the private-sector investment.

“Vice President Harris was very involved diplomatically early on with Central American governments, clearing the way to get these two initiatives underway and talking about how to stem unauthorized migration,” Selee said. “But, as near as I can tell, she just hasn’t stayed as engaged diplomatically on this. And, you know, over time, the State Department and the National Security Council really took over the diplomatic side.”

Krish O’Mara Vignarajah, president and CEO of Global Refuge, noted Harris’ role launching an anti-corruption task force with the Justice Department focused on Northern Triangle countries.

“I do think she [Harris] has played a leadership role in addressing the root causes,” Vignarajah said.

“Do we believe this solves the problem? No. Of course not. And this is where Congress needs to be a real player,” she said.

Didi Martinez is an associate producer with the NBC News Investigative Unit. 

Julia Ainsley is the homeland security correspondent for NBC News and covers the Department of Homeland Security for the NBC News Investigative Unit.

Advertisement

Supported by

What We Know About the Global Microsoft Outage

Airlines to banks to retailers were affected in many countries. Businesses are struggling to recover.

• Share full article

By Eshe Nelson and Danielle Kaye

Eshe Nelson reported from London and Danielle Kaye from New York.

Across the world, critical businesses and services including airlines, hospitals, train networks and TV stations, were disrupted on Friday by a global tech outage affecting Microsoft users.

In many countries, flights were grounded, workers could not get access to their systems and, in some cases, customers could not make card payments in stores. While some of the problems were resolved within hours, many businesses, websites and airlines continued to struggle to recover.

What happened?

A series of outages rippled across the globe as information displays, login systems and broadcasting networks went dark.

The problem affecting the majority of services was caused by a flawed update by CrowdStrike , an American cybersecurity firm, whose systems are intended to protect users from hackers. Microsoft said on Friday that it was aware of an issue affecting machines running “CrowdStrike Falcon.”

But Microsoft had also said there was an earlier outage affecting U.S. users of Azure, its cloud service system. Some users may have been affected by both. Even as CrowdStrike sent out a fix, some systems were still affected by midday in the United States as businesses needed to make manual updates to their systems to resolve the issue.

George Kurtz, the president and chief executive of CrowdStrike, said on Friday morning that it could take some time for some systems to recover.

How a Software Update Crashed Computers Around the World

Here’s a visual explanation for how a faulty software update crippled machines.

How the airline cancellations rippled around the world (and across time zones)

Share of canceled flights at 25 airports on Friday

50% of flights

Ai r po r t

Bengalu r u K empeg o wda

Dhaka Shahjalal

Minneapolis-Saint P aul

Stuttga r t

Melbou r ne

Be r lin B r anden b urg

London City

Amsterdam Schiphol

Chicago O'Hare

Raleigh−Durham

B r adl e y

Cha r lotte

Reagan National

Philadelphia

1:20 a.m. ET

We are having trouble retrieving the article content.

Please enable JavaScript in your browser settings.

Thank you for your patience while we verify access. If you are in Reader mode please exit and  log into  your Times account, or  subscribe  for all of The Times.

Thank you for your patience while we verify access.

Already a subscriber?  Log in .

Want all of The Times?  Subscribe .