Stay organized with collections
Save and categorize content based on your preferences.
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.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-28 UTC."],[[["The assignment problem focuses on optimally assigning workers to tasks to minimize the total cost, where each worker is assigned at most one task and no task is assigned to multiple workers."],["This problem can be visualized using a graph where edges represent worker-task assignments and edge labels represent the cost of each assignment."],["OR-Tools offers various solvers like MIP, CP-SAT, Linear Sum Assignment, and Minimum Cost Flow, but MIP and CP-SAT are recommended for their versatility and efficiency in handling a broader range of assignment problems."]]],["The content describes the assignment problem, a combinatorial optimization challenge where workers are assigned to tasks to minimize total cost. Each worker is assigned to at most one task, and each task is done by at most one worker. The example shows how the problem can be represented graphically, with edges representing possible assignments and their costs. The total cost is calculated by adding up the costs of the assigned edges. OR-Tools offer multiple tools to solve such problems, among which the MIP and CP-SAT are the most general.\n"]]
