In this section, we compare the speed of the OR-Tools solvers for various types of assignment problems. As mentioned previously, for a simple assignment problem in which the only requirement is that each worker be assigned to a unique task, the specialized linear assignment solver is fastest.

For more general assignment problems, you have a choice between min cost flow, MIP, and CP. If the problem can be written as a flow problem, min cost flow is the fastest option. Otherwise, you must use MIP or CP. For some types of problems, MIP is faster, while for others, CP is faster. The following guidelines provide some criteria for making your choice.

### Guidelines for choosing between MIP and CP

- If all the constraints for the problem must hold for a solution to be feasible (constraints connected by "and" statements), then MIP is generally faster.
- If many of the constraints have the property that just one of them needs to hold for a solution to be feasible (constraints connected by "or" statements), then CP is generally faster.

## Assignment with task sizes

The first example is an assignment problem in which the tasks are assigned
*sizes*, which measure how much time or effort each task requires.
The new constraint is that the total size of the tasks
performed by each worker has a fixed bound. Since all of these constraints must hold for a
solution to be feasible, the problem meets the condition in
guideline 1 above.

### MIP solution

First, here's a Python program that solves the problem using the MIP solver.

#### Create the data

The following code creates the data for the program.

cost = [[90, 76, 75, 70, 50, 74, 12, 68], [35, 85, 55, 65, 48, 101, 70, 83], [125, 95, 90, 105, 59, 120, 36, 73], [45, 110, 95, 115, 104, 83, 37, 71], [60, 105, 80, 75, 59, 62, 93, 88], [45, 65, 110, 95, 47, 31, 81, 34], [38, 51, 107, 41, 69, 99, 115, 48], [47, 85, 57, 71, 92, 77, 109, 36], [39, 63, 97, 49, 118, 56, 92, 61], [47, 101, 71, 60, 88, 109, 52, 90]] task_sizes = [10, 7, 3, 12, 15, 4, 11, 5] # Maximum total of task sizes for any worker total_size_max = 15

#### Create the variables and constraints

The following code creates the variables and constraints for the program.

# Variables x = {} for i in range(num_workers): for j in range(num_tasks): x[i, j] = solver.IntVar(0, 1, 'x[%i,%i]' % (i, j)) # Constraints # The total size of the tasks each worker takes on is at most total_size_max. for i in range(num_workers): solver.Add(solver.Sum([task_sizes[j] * x[i, j] for j in range(num_tasks)]) <= total_size_max) # Each task is assigned to at least one worker. for j in range(num_tasks): solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) >= 1)

#### Create the objective

The following code creates the objective function.

solver.Minimize(solver.Sum([cost[i][j] * x[i,j] for i in range(num_workers) for j in range(num_tasks)]))

#### Invoke the solver and display the results

The following code invokes the solver and displays the results.

sol = solver.Solve() print('Total cost = ', solver.Objective().Value()) print() for i in range(num_workers): for j in range(num_tasks): if x[i, j].solution_value() > 0: print('Worker', i,' assigned to task', j, ' Cost = ', cost[i][j]) print() print("Time = ", solver.WallTime(), "milliseconds")

Here is the output of the program.

Total cost = 326.0 Worker 0 assigned to task 6 Cost = 12 Worker 1 assigned to task 0 Cost = 35 Worker 1 assigned to task 2 Cost = 55 Worker 4 assigned to task 4 Cost = 59 Worker 5 assigned to task 5 Cost = 31 Worker 5 assigned to task 7 Cost = 34 Worker 6 assigned to task 1 Cost = 51 Worker 8 assigned to task 3 Cost = 49 Time = 20 milliseconds

### CP solution

Next, let's take a look at the CP solution to the assignment problem with task sizes. The code that creates the data is omitted, since it is the same as for the MIP solution.

#### Create the variables and constraints

The following code creates the variables and constraints for the program.

# Variables total_cost = solver.IntVar(0, 1000, "total_cost") x = [] for i in range(num_workers): t = [] for j in range(num_tasks): t.append(solver.IntVar(0, 1, "x[%i,%i]" % (i, j))) x.append(t) x_array = [x[i][j] for i in range(num_workers) for j in range(num_tasks)] # Constraints # Each task is assigned to at least one worker. [solver.Add(solver.Sum(x[i][j] for i in range(num_workers)) >= 1) for j in range(num_tasks)] # Total task size for each worker is at most total_size_max [solver.Add(solver.Sum(sizes[j] * x[i][j] for j in range(num_tasks)) <= total_size_max) for i in range(num_workers)]

#### Create the objective

The following code creates the objective function.

# Total cost solver.Add( total_cost == solver.Sum( [solver.ScalProd(x_row, cost_row) for (x_row, cost_row) in zip(x, cost)])) objective = solver.Minimize(total_cost, 1)

#### Invoke the solver

The following code invokes the solver and displays the results.

solver.Solve(db, [objective, collector]) if collector.SolutionCount() > 0: best_solution = collector.SolutionCount() - 1 print("Total cost = ", collector.ObjectiveValue(best_solution)) print() for i in range(num_workers): for j in range(num_tasks): if collector.Value(best_solution, x[i][j]) == 1: print('Worker ', i, ' assigned to task ', j, ' Cost = ', cost[i][j]) print() print("Time = ", solver.WallTime(), "milliseconds")

Here's the output of the program.

Total cost = 326 Worker 0 assigned to task 6 Cost = 12 Worker 1 assigned to task 0 Cost = 35 Worker 1 assigned to task 2 Cost = 55 Worker 4 assigned to task 4 Cost = 59 Worker 5 assigned to task 5 Cost = 31 Worker 5 assigned to task 7 Cost = 34 Worker 6 assigned to task 1 Cost = 51 Worker 8 assigned to task 3 Cost = 49 Time = 4576 milliseconds

### Summary

MIP is much faster than CP for this problem. MIP takes only 20 milliseconds, versus 4576 milliseconds for the CP solver. Of course, this is small problem, for which the speed of the solver doesn't matter that much. But for large problems that meet the conditions of guideline 1, it is usually best to use the MIP solver.

#### The entire programs

Here are the entire programs for solving the assignment problem with task sizes using MIP and CP.

from __future__ import print_function from ortools.linear_solver import pywraplp def main(): # Instantiate a mixed-integer solver solver = pywraplp.Solver('SolveTransportationProblem', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING) cost = [[90, 76, 75, 70, 50, 74, 12, 68], [35, 85, 55, 65, 48, 101, 70, 83], [125, 95, 90, 105, 59, 120, 36, 73], [45, 110, 95, 115, 104, 83, 37, 71], [60, 105, 80, 75, 59, 62, 93, 88], [45, 65, 110, 95, 47, 31, 81, 34], [38, 51, 107, 41, 69, 99, 115, 48], [47, 85, 57, 71, 92, 77, 109, 36], [39, 63, 97, 49, 118, 56, 92, 61], [47, 101, 71, 60, 88, 109, 52, 90]] task_sizes = [10, 7, 3, 12, 15, 4, 11, 5] # Maximum total of task sizes for any worker total_size_max = 15 num_workers = len(cost) num_tasks = len(cost[1]) # Variables x = {} for i in range(num_workers): for j in range(num_tasks): x[i, j] = solver.IntVar(0, 1, 'x[%i,%i]' % (i, j)) # Constraints # The total size of the tasks each worker takes on is at most total_size_max. for i in range(num_workers): solver.Add(solver.Sum([task_sizes[j] * x[i, j] for j in range(num_tasks)]) <= total_size_max) # Each task is assigned to at least one worker. for j in range(num_tasks): solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) >= 1) solver.Minimize(solver.Sum([cost[i][j] * x[i,j] for i in range(num_workers) for j in range(num_tasks)])) sol = solver.Solve() print('Total cost = ', solver.Objective().Value()) print() for i in range(num_workers): for j in range(num_tasks): if x[i, j].solution_value() > 0: print('Worker', i,' assigned to task', j, ' Cost = ', cost[i][j]) print() print("Time = ", solver.WallTime(), "milliseconds") if __name__ == '__main__': main()

from __future__ import print_function from ortools.constraint_solver import pywrapcp def main(): # Instantiate a cp solver. solver = pywrapcp.Solver("transportation_with_sizes") cost = [[90, 76, 75, 70, 50, 74, 12, 68], [35, 85, 55, 65, 48, 101, 70, 83], [125, 95, 90, 105, 59, 120, 36, 73], [45, 110, 95, 115, 104, 83, 37, 71], [60, 105, 80, 75, 59, 62, 93, 88], [45, 65, 110, 95, 47, 31, 81, 34], [38, 51, 107, 41, 69, 99, 115, 48], [47, 85, 57, 71, 92, 77, 109, 36], [39, 63, 97, 49, 118, 56, 92, 61], [47, 101, 71, 60, 88, 109, 52, 90]] sizes = [10, 7, 3, 12, 15, 4, 11, 5] total_size_max = 15 num_workers = len(cost) num_tasks = len(cost[1]) # Variables total_cost = solver.IntVar(0, 1000, "total_cost") x = [] for i in range(num_workers): t = [] for j in range(num_tasks): t.append(solver.IntVar(0, 1, "x[%i,%i]" % (i, j))) x.append(t) x_array = [x[i][j] for i in range(num_workers) for j in range(num_tasks)] # Constraints # Each task is assigned to at least one worker. [solver.Add(solver.Sum(x[i][j] for i in range(num_workers)) >= 1) for j in range(num_tasks)] # Total task size for each worker is at most total_size_max [solver.Add(solver.Sum(sizes[j] * x[i][j] for j in range(num_tasks)) <= total_size_max) for i in range(num_workers)] # Total cost solver.Add( total_cost == solver.Sum( [solver.ScalProd(x_row, cost_row) for (x_row, cost_row) in zip(x, cost)])) objective = solver.Minimize(total_cost, 1) db = solver.Phase(x_array, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) # Create a solution collector. collector = solver.LastSolutionCollector() # Add decision variables #collector.Add(x_array) for i in range(num_workers): collector.Add(x[i]) # Add objective collector.AddObjective(total_cost) solver.Solve(db, [objective, collector]) if collector.SolutionCount() > 0: best_solution = collector.SolutionCount() - 1 print("Total cost = ", collector.ObjectiveValue(best_solution)) print() for i in range(num_workers): for j in range(num_tasks): if collector.Value(best_solution, x[i][j]) == 1: print('Worker ', i, ' assigned to task ', j, ' Cost = ', cost[i][j]) print() print("Time = ", solver.WallTime(), "milliseconds") if __name__ == '__main__': main()

## Assignment with allowed groups of workers

The next example is an assignment problem in which
only certain allowed groups of workers can be assigned to the tasks. In the example,
there are twelve workers, numbered 0 — 11. An *allowed group* of
workers is simply a subset of the workers that can be assigned to the tasks,
so that each worker in the group performs some task.

In this problem, the allowed groups of workers are defined by the following three sets:

group1 = [[2, 3], # Subgroups of workers 0 - 3 [1, 3], [1, 2], [0, 1], [0, 2]] group2 = [[6, 7], # Subgroups of workers 4 - 7 [5, 7], [5, 6], [4, 5], [4, 7]] group3 = [[10, 11], # Subgroups of workers 8 - 11 [9, 11], [9, 10], [8, 10], [8, 11]]

The allowed groups are any combination of three pairs of workers from the sets shown above: one pair from group1, a second pair from group2, and a third pair from group3. For example, combining [2, 3], [6, 7], and [10, 11] results in the allowed group [2, 3, 6, 7, 10, 11]. Since each of the three sets contains five elements, the total number of allowed groups is 5 * 5 * 5 = 125.

The problem meets the condition in guideline 2 because a group of workers can be assigned to the tasks if it matches any one of the allowed groups. To solve this problem, the MIP solver has to loop through all 125 allowed groups and find the optimal assignment for each group, and then choose the assignment with the smallest overall cost. As you will see, this turns out to be a relatively slow way to solve this problem, compared with the method used by the CP solver.

### MIP solution

The following sections present a Python program that solves the assignment problem with allowed groups of workers using the MIP solver.

#### Create the data

The following code creates the data for the program.

cost = [[90, 76, 75, 70, 50, 74], [35, 85, 55, 65, 48, 101], [125, 95, 90, 105, 59, 120], [45, 110, 95, 115, 104, 83], [60, 105, 80, 75, 59, 62], [45, 65, 110, 95, 47, 31], [38, 51, 107, 41, 69, 99], [47, 85, 57, 71, 92, 77], [39, 63, 97, 49, 118, 56], [47, 101, 71, 60, 88, 109], [17, 39, 103, 64, 61, 92], [101, 45, 83, 59, 92, 27]]

#### Create the allowed groups

The following code creates the allowed groups, by looping through the three sets of subgroups shown above.

allowed_groups = [] for i in range(len(group1)): for j in range(len(group2)): for k in range(len(group3)): allowed_groups.append(group1[i] + group2[j] + group3[k])

#### Create the variables and constraints

The following code creates the variables and constraints for the program.

x = {} for i in group: for j in range(num_tasks): x[i, j] = solver.IntVar(0, 1, 'x[%i,%i]' % (i, j)) # constraints # Each worker is assigned to exactly one task. for i in group: solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) <= 1) # Each task is assigned to at least one worker. for j in range(num_tasks): solver.Add(solver.Sum([x[i, j] for i in group]) >= 1)

#### Create the objective

The following code creates the objective function.

solver.Minimize(solver.Sum([cost[i][j] * x[i,j] for i in group for j in range(num_tasks)]))

#### Invoke the solver and display the results

The following code invokes the solver and displays the results.

solver.Solve() res = [solver, x] return res if __name__ == '__main__': main()Here's the output of the program:

Minimum cost = 239.0 Workers: [0, 1, 5, 6, 10, 11] Worker 0 assigned to task 4 Cost = 50 Worker 1 assigned to task 2 Cost = 55 Worker 5 assigned to task 5 Cost = 31 Worker 6 assigned to task 3 Cost = 41 Worker 10 assigned to task 0 Cost = 17 Worker 11 assigned to task 1 Cost = 45 Time = 396 milliseconds

### CP solution

Next, let's take a look at the CP solution to the assignment problem with allowed groups. Once again, the code that creates the data is omitted, since it is the same as for the MIP program.

#### Create the allowed groups

You define the allowed groups of workers slightly differently for the CP solver than for the MIP solver. Instead of specifying the workers in a group by their numbers (as for MIP), you create binary arrays that indicate which workers belong to a group. For example, for group1 (workers 0—3), the binary vector [0, 0, 1, 1] specifies the group containing workers 2 and 3.

The following arrays define the same allowed groups as the code for the MIP solver.

group1 = [[0, 0, 1, 1], # Workers 2, 3 [0, 1, 0, 1], # Workers 1, 3 [0, 1, 1, 0], # Workers 1, 2 [1, 1, 0, 0], # Workers 0, 1 [1, 0, 1, 0]] # Workers 0, 2 group2 = [[0, 0, 1, 1], # Workers 6, 7 [0, 1, 0, 1], # Workers 5, 7 [0, 1, 1, 0], # Workers 5, 6 [1, 1, 0, 0], # Workers 4, 5 [1, 0, 0, 1]] # Workers 4, 7 group3 = [[0, 0, 1, 1], # Workers 10, 11 [0, 1, 0, 1], # Workers 9, 11 [0, 1, 1, 0], # Workers 9, 10 [1, 0, 1, 0], # Workers 8, 10 [1, 0, 0, 1]] # Workers 8, 11For CP it is not necessary to create all 125 combinations of these vectors in a loop. The CP solver provides a method,

`AllowedAssignments`

, which enables you to specify
the constraints for the allowed groups separately for each of the three sets of workers
(0—3, 4—7, and 8—11). Here's how it works:
solver.Add(solver.AllowedAssignments([work[0], work[1], work[2], work[3]], group1)) solver.Add(solver.AllowedAssignments([work[4], work[5], work[6], work[7]], group2)) solver.Add(solver.AllowedAssignments([work[8], work[9], work[10], work[11]], group3))The variables

`work[i]`

are 0—1 variables that indicate the *work status*or each worker. That is,

`work[i]`

equals 0 if worker i is assigned to a task,
and 0 otherwise. The line
solver.Add(solver.AllowedAssignments([work[0], work[1], work[2], work[3]], group1))defines the constraint that the work status of workers 0—3 must match one of the patterns in group1. You can see the full details of the code in the next section.

#### Create the variables and constraints

The following code creates the variables and constraints for the program.

# Declare the variables. x = [] for i in range(num_workers): t = [] for j in range(num_tasks): t.append(solver.IntVar(0, 1, "x[%i,%i]" % (i, j))) x.append(t) x_array = [x[i][j] for i in range(num_workers) for j in range(num_tasks)]

#### Create the objective

The following code creates the objective function.

total_cost = solver.IntVar(0, 1000, "total_cost") # total_cost solver.Add( total_cost == solver.Sum( [solver.ScalProd(x_row, cost_row) for (x_row, cost_row) in zip(x, cost)])) objective = solver.Minimize(total_cost, 1)

#### Invoke the solver

The following code invokes the solver and displays the results.

solver.Solve(db, [objective, collector]) if collector.SolutionCount() > 0: best_solution = collector.SolutionCount() - 1 print("Total cost = ", collector.ObjectiveValue(best_solution)) for i in range(num_workers): for j in range(num_tasks): if collector.Value(best_solution, x[i][j]) == 1: print() print('Worker ', i, ' assigned to task ', j, ' Cost = ', cost[i][j]) print() print("Time = ", solver.WallTime(), "milliseconds")

#### Output of the program

Here's the output of the program.

Total cost = 239 Worker 0 assigned to task 4 Cost = 50 Worker 1 assigned to task 2 Cost = 55 Worker 5 assigned to task 5 Cost = 31 Worker 6 assigned to task 3 Cost = 41 Worker 10 assigned to task 0 Cost = 17 Worker 11 assigned to task 1 Cost = 45 Time = 9 milliseconds

### Summary

This time, CP is the clear winner: it solves the problem in 9 milliseconds, versus 396 milliseconds for the MIP solver. Again, for a small problem like this one, the time difference is not that important. But for large problems that meet the conditions of guideline 2, the CP solver is usually the best choice.

#### The entire programs

Here are the entire programs for solving the assignment problem with allowed patterns using MIP and CP.

from __future__ import print_function from ortools.linear_solver import pywraplp def main(): # Instantiate a mixed-integer solver solver = pywraplp.Solver('SolveTransportationProblem', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING) cost = [[90, 76, 75, 70, 50, 74, 12, 68], [35, 85, 55, 65, 48, 101, 70, 83], [125, 95, 90, 105, 59, 120, 36, 73], [45, 110, 95, 115, 104, 83, 37, 71], [60, 105, 80, 75, 59, 62, 93, 88], [45, 65, 110, 95, 47, 31, 81, 34], [38, 51, 107, 41, 69, 99, 115, 48], [47, 85, 57, 71, 92, 77, 109, 36], [39, 63, 97, 49, 118, 56, 92, 61], [47, 101, 71, 60, 88, 109, 52, 90]] task_sizes = [10, 7, 3, 12, 15, 4, 11, 5] # Maximum total of task sizes for any worker total_size_max = 15 num_workers = len(cost) num_tasks = len(cost[1]) # Variables x = {} for i in range(num_workers): for j in range(num_tasks): x[i, j] = solver.IntVar(0, 1, 'x[%i,%i]' % (i, j)) # Constraints # The total size of the tasks each worker takes on is at most total_size_max. for i in range(num_workers): solver.Add(solver.Sum([task_sizes[j] * x[i, j] for j in range(num_tasks)]) <= total_size_max) # Each task is assigned to at least one worker. for j in range(num_tasks): solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) >= 1) solver.Minimize(solver.Sum([cost[i][j] * x[i,j] for i in range(num_workers) for j in range(num_tasks)])) sol = solver.Solve() print('Total cost = ', solver.Objective().Value()) print() for i in range(num_workers): for j in range(num_tasks): if x[i, j].solution_value() > 0: print('Worker', i,' assigned to task', j, ' Cost = ', cost[i][j]) print() print("Time = ", solver.WallTime(), "milliseconds") if __name__ == '__main__': main()

from __future__ import print_function from ortools.constraint_solver import pywrapcp def main(): # Instantiate a cp solver. solver = pywrapcp.Solver("transportation_with_sizes") cost = [[90, 76, 75, 70, 50, 74, 12, 68], [35, 85, 55, 65, 48, 101, 70, 83], [125, 95, 90, 105, 59, 120, 36, 73], [45, 110, 95, 115, 104, 83, 37, 71], [60, 105, 80, 75, 59, 62, 93, 88], [45, 65, 110, 95, 47, 31, 81, 34], [38, 51, 107, 41, 69, 99, 115, 48], [47, 85, 57, 71, 92, 77, 109, 36], [39, 63, 97, 49, 118, 56, 92, 61], [47, 101, 71, 60, 88, 109, 52, 90]] sizes = [10, 7, 3, 12, 15, 4, 11, 5] total_size_max = 15 num_workers = len(cost) num_tasks = len(cost[1]) # Variables total_cost = solver.IntVar(0, 1000, "total_cost") x = [] for i in range(num_workers): t = [] for j in range(num_tasks): t.append(solver.IntVar(0, 1, "x[%i,%i]" % (i, j))) x.append(t) x_array = [x[i][j] for i in range(num_workers) for j in range(num_tasks)] # Constraints # Each task is assigned to at least one worker. [solver.Add(solver.Sum(x[i][j] for i in range(num_workers)) >= 1) for j in range(num_tasks)] # Total task size for each worker is at most total_size_max [solver.Add(solver.Sum(sizes[j] * x[i][j] for j in range(num_tasks)) <= total_size_max) for i in range(num_workers)] # Total cost solver.Add( total_cost == solver.Sum( [solver.ScalProd(x_row, cost_row) for (x_row, cost_row) in zip(x, cost)])) objective = solver.Minimize(total_cost, 1) db = solver.Phase(x_array, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) # Create a solution collector. collector = solver.LastSolutionCollector() # Add decision variables #collector.Add(x_array) for i in range(num_workers): collector.Add(x[i]) # Add objective collector.AddObjective(total_cost) solver.Solve(db, [objective, collector]) if collector.SolutionCount() > 0: best_solution = collector.SolutionCount() - 1 print("Total cost = ", collector.ObjectiveValue(best_solution)) print() for i in range(num_workers): for j in range(num_tasks): if collector.Value(best_solution, x[i][j]) == 1: print('Worker ', i, ' assigned to task ', j, ' Cost = ', cost[i][j]) print() print("Time = ", solver.WallTime(), "milliseconds") if __name__ == '__main__': main()