One of the most well-known combinatorial optimization problems is the 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.
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.
The total cost of the assignment is 70 + 55 + 95 + 45 = 265.
The next section 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:
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.