# Assignment

One of the most well-known combinatorial optimization problems is the
[*assignment problem*](https://en.wikipedia.org/wiki/Assignment_problem). Here's an example: suppose a group of workers needs to perform a set of tasks, and for
each worker and task, there is a cost for assigning the worker to the task.
The problem is to assign each worker to at most one task, with no two workers
performing the same task, while minimizing the total cost.

You can visualize this problem by the graph below, in which there are four
workers and four tasks. The edges represent all possible ways to assign workers
to tasks. The labels on the edges are the costs of assigning workers to tasks.

![assignment flow graph](https://developers.google.com/static/optimization/images/assignment/assignment.svg)

An assignment corresponds to a subset of the edges, in which each worker has at
most one edge leading out, and no two workers have edges leading to the same
task. One possible assignment is shown below.

![assignment solution flow graph](https://developers.google.com/static/optimization/images/assignment/assignment_solution.svg)

The total cost of the assignment is `70 + 55 + 95 + 45 = 265`.

The [next section](https://developers.google.com/optimization/assignment/assignment_example) shows how solve
an assignment problem, using both the MIP solver and the CP-SAT solver.

### Other tools for solving assignment problems

OR-Tools also provides a couple of other tools for solving assignment problems,
which can be faster than the MIP or CP solvers:

- [Linear sum assignment solver](https://developers.google.com/optimization/assignment/linear_assignment)
- [Minimum cost flow solver](https://developers.google.com/optimization/flow/assignment_min_cost_flow)

However, these tools can only solve simple types of assignment problems.
So for general solvers that can handle a wide variety of problems (and are fast
enough for most applications), we recommend the MIP and CP-SAT solvers.