Assignment problem

The (linear) assignment problem is a discrete optimization problem from graph theory. It is a special classical transportation problem and has applications in operations research.

It can be formulated verbally as follows:

A number (n ) workers should be assigned the same number of activities with known (execution ) costs, which differ in the execution costs of worker to worker and job to job.

• Each worker is assigned to exactly one activity and any activity performed by exactly one worker.
• Then the minimum-cost routing is chosen among all admissible plans.

With the variable

And the cost of execution gives rise to the following mathematical model:

Minimize

Subject to the constraints

This problem can be solved by the Hungarian method. Examples of the linear assignment problem is the assignment of students to schools, or the assignment of students to seminar courses. The quadratic assignment problem is with the linear problem identical constraints, however, the objective function is quadratic. It can for example be used in the workshop production to an assignment of machines on pitches, in which the sum of the products of transport volumes and distances is minimal. This problem class is NP - hard and therefore can not be solved with simple algorithms.