Assignment Optimization Task

Context:
- Input: ...; cost matrix; ...
- It can be solved by an Assignment Optimization Machine that implements an Assignment Optimization Algorithm (such as a Hungarian algorithm).
- It can range from being a Linear Assignment Task to being a Non-Linear Assignment Task.
- …
Example(s):
- Given three workers and three jobs what is the minimum-cost way to assign the jobs? First we need a cost matrix of the costs of the workers doing the jobs...
- a Maximum Weight Bipartite Graph Matching Task.
See: Combinatorial Optimization, Matching (Graph Theory), Minimum Cost Flow Problem, Linear Program, Simplex Algorithm, Quadratic Assignment Problem.

References

(Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/Assignment_problem Retrieved:2014-8-22.
- The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. It consists of finding a maximum weight matching in a weighted bipartite graph.
  In its most general form, the problem is as follows:
  :There are 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-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.
  If the numbers of agents and tasks are equal and the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called the linear assignment problem. Commonly, when speaking of the assignment problem without any additional qualification, then the linear assignment problem is meant.

(Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/Hungarian_algorithm#Layman.E2.80.99s_Explanation_of_the_Assignment_Problem Retrieved:2014-8-22.
- Say you have three workers: Jim, Steve, and Alan. You need to have one of them clean the bathroom, another sweep the floors, and the third wash the windows. What’s the best (minimum-cost) way to assign the jobs? First we need a matrix of the costs of the workers doing the jobs.

- Then the Hungarian method, when applied to the above table would give us the minimum cost it can be done with: Jim cleans the bathroom, Steve sweeps the floors, and Alan washes the windows.

(Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/Assignment_problem#Algorithms_and_generalizations Retrieved:2014-8-22.
- The Hungarian algorithm is one of many algorithms that have been devised that solve the linear assignment problem within time bounded by a polynomial expression of the number of agents.
  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. While it is possible to solve any of these problems using the simplex algorithm, each specialization has more efficient algorithms designed to take advantage of its special structure. If the cost function involves quadratic inequalities it is called the quadratic assignment problem.