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 discrete assignment on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task and exactly one task to each agent in such a way that the total cost of the assignment is minimized.
A naive solution for the assignment problem is to check all the assignments and calculate the cost of each one. This may be very inefficient since, with n agents and n tasks, there are n! Many algorithms have been developed for solving the assignment problem in time bounded by a polynomial of n. One of the first such algorithms was the Hungarian algorithm, developed by Munkres. The assignment problem is a special case of the transportation problem, which is a special case of the minimum cost flow problem, which in turn is a special case of a linear program.
When a number of agents and tasks is very large, a parallel algorithm with randomization can be applied. The problem of finding minimum weight maximum matching can be converted to finding a minimum weight perfect matching. A bipartite graph can be extended to a complete bipartite graph by adding artificial edges with large weights. The firm prides itself on speedy pickups, so for each taxi the “cost” of picking up a particular customer will depend on the time taken for the taxi to reach the pickup point. The solution to the assignment problem will be whichever combination of taxis and customers results in the least total cost.
However, the assignment problem can be made rather more flexible than it first appears. In the above example, suppose that there are four taxis available, but still only three customers. Then a fourth dummy task can be invented, perhaps called “sitting still doing nothing”, with a cost of 0 for the taxi assigned to it. The assignment problem can then be solved in the usual way and still give the best solution to the problem. The problem is “linear” because the cost function to be optimized as well as all the constraints contain only linear terms. The assignment problem can be solved by presenting it as a linear program. For convenience we will present the maximization problem.
The goal is to find a maximum-weight perfect matching. To guarantee that the variables indeed represent a perfect matching, we add constraints saying that each vertex is adjacent to exactly one edge in the matching, i. This is an integer linear program. While this formulation allows also fractional variable values, in this special case, the LP always has an optimal solution where the variables take integer values. This can also be proved directly.
By similar considerations we move from one vertex to another, collecting edges with fractional values. Since the graph is finite, at some point we must have a cycle. So the number of edges in the cycle is 2m – it must be even since the graph is bipartite. Suppose we add a certain constant e to all even variables in the cycle, and remove the same constant e from all odd variables in the cycle. Moreover, if e is sufficiently small, all variables remain between 0 and 1, so the domain constraints are still satisfied too.
By repeating the cycle-removal process we arrive, after at most n steps, at a solution in which all variables are integral. Algorithms for the Assignment and Transportation Problems”. Journal of the Society for Industrial and Applied Mathematics. Matching is as easy as matrix inversion”. Encyclopedia of Mathematics and Its Applications. Network Optimization: Continuous and Discrete Models.