Assignment task

The assignment problem is one of the fundamental problems of combinatorial optimization in the field of mathematical optimization or the study of operations . The task is to find the minimum sum of arcs in a weighted bipartite graph .

In the most general form, the task is formulated as follows:

There is a certain number of works and a certain number of performers . Any contractor can be appointed to perform any (but only one) work, but with unequal costs. It is necessary to distribute the work in such a way as to perform work with minimal cost.

If the number of jobs and performers is the same, then the task is called a linear assignment problem . Usually, when one speaks of the assignment problem without additional conditions, they mean the linear assignment problem .

Content

1 Algorithms and generalizations
2 Example
3 Formal mathematical definition
4 See also
5 Literature

Algorithms and generalizations

The Hungarian algorithm is one of many algorithms designed to solve the linear assignment problem in polynomial time from the number of jobs.

The assignment problem is a special case of the transport problem , which is a special case of the problem of finding the minimum cost stream , and it, in turn, is a special case of the linear programming problem. Any of these problems can be solved by the simplex method , but each specialization has its own more efficient algorithm, based on the structural features of the problem.

If the objective function is expressed in terms of squares, they speak of a quadratic assignment problem .

Example

Suppose a taxi company has three free cars (performers), and three customers (jobs) who want to get a taxi as quickly as possible. The company takes care of the time of taxi delivery to the customer, so for each car the cost is determined by the time from which the car gets to the place of waiting determined by the customer. The solution to the assignment problem is to distribute the machines to customers such that the total cost (total waiting time) is minimal.

The assignment problem can be made more flexible. In the above example, there may be not three, but four free taxis, but the customer is still three. You can assign a fourth fictitious customer with zero cost, but distributing the machine to a fictitious customer means "do nothing."

A similar technique can be used when the number of orders can exceed the number of available cars, and the car can be assigned to perform several works, and also when the work can be assigned to several contractors (for example, if the customer is a group that does not fit in one taxi). You can also set the goal of increasing income, rather than minimizing the price.

Formal Mathematical Definition

Formal statement of the assignment problem :

Two sets A and T of the same size are given and a cost function C is given : A × T → R.

It is necessary to find a bijection f : A → T such that the objective function :

\sum _{a\in A}C(a,f(a))

{\ displaystyle \ sum _ {a \ in A} C (a, f (a))}

is minimal.

Usually, the cost function is defined as a square matrix C consisting of real numbers so that the objective function can be written as:

\sum _{a\in A}C_{a,f(a)}

{\ displaystyle \ sum _ {a \ in A} C_ {a, f (a)}}

The task is called “linear” because both the objective function and the constraints contain only linear expressions.

The task can be represented as a linear programming task with a target function

\sum _{i\in A}\sum _{j\in T}C(i,j)x_{ij}

{\ displaystyle \ sum _ {i \ in A} \ sum _ {j \ in T} C (i, j) x_ {ij}}

and limitations

\sum _{j\in T}x_{ij}=1

{\ displaystyle \ sum _ {j \ in T} x_ {ij} = 1}

for

i\in A

{\ displaystyle i \ in A}

,

\sum _{i\in A}x_{ij}=1

{\ displaystyle \ sum _ {i \ in A} x_ {ij} = 1}

for

j\in T

{\ displaystyle j \ in T}

,

x_{ij}\geq 0

{\ displaystyle x_ {ij} \ geq 0}

for

i,j\in A,T

{\ displaystyle i, j \ in A, T}

.

Variable $x_{ij}$ ${\ displaystyle x_ {ij}}$ represents the appointment of an artist $i$ ${\ displaystyle i}$ to work $j$ ${\ displaystyle j}$ , taking the value 1 if the contractor is assigned to this job and 0 otherwise. In this formulation, the solution may not be integer, but there is always an optimal solution with integer values. This fact follows from the absolute unimodularity of the matrix . The first restriction requires that exactly one task be assigned to each executor, the second requires that one executor be assigned to each task.

Literature

Hemdy A. Taha. Ch. 5.4 The assignment problem. // Introduction to operations research. 7th edition. Per. from English - M .: Williams Publishing House, 2005.
Wagner G. Appendix 1.2 Solution of the assignment problem // Fundamentals of operations research. Per. from English - M .: Publishing house "Mir", 1972 .. - T. 1.
Akof R., Sasieni M.,. Chapter 5 Distribution tasks: assignment and allocation of resources // Fundamentals of Operations Research. - M .: Publishing house "Mir", 1971.
Richard A. Brualdi. Combinatorial matrix classes. - Cambridge: Cambridge University Press , 2006. - (Encyclopedia of Mathematics and Its Applications). - ISBN 0-521-86565-4 .
Rainer Burkard, M. Dell'Amico, S. Martello. Assignment Problems (Revised reprint). - SIAM, 2012 .-- ISBN 978-1-61197-222-1 .