# Comparing MIP and CP

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

1. 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.
2. 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.
In the following sections, we present two problems to illustrate these guidelines. The first problem meets the condition in guideline 1, while the second meets the condition in guideline 2. We solve both problems, using both MIP and CP, and record the time it takes each solver to solve the problems. You can see the results at the end of each section.

## Assignment with task sizes

### 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 =  14 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 =  3900 milliseconds```

### Summary

MIP is much faster than CP for this problem. MIP takes only 14 milliseconds, versus 3900 milliseconds for the CP solver. (The is CPU time from the creation of the solver. Your results may be slightly different.) 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.

Full MIP program
```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()```
Full CP program
```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 =  251 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, 11```
For 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 251 milliseconds for the MIP solver. (The is CPU time from the creation of the solver. Your results may be slightly different.) 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.

Full MIP program
```from __future__ import print_function
from ortools.linear_solver import pywraplp
import math

def main():
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]]
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]]
num_tasks = len(cost[1])
# Allowed groups of workers:
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])
min_val = 1e6
total_time = 0

for i in range(len(allowed_groups)):
group = allowed_groups[i]
res = assignment(cost, group)
solver_tmp = res[0]
x_tmp = res[1]
total_time = total_time + solver_tmp.WallTime()

if solver_tmp.Objective().Value() < min_val:
min_val = solver_tmp.Objective().Value()
min_index = i
min_solver = solver_tmp
min_x = x_tmp
min_group = group

print('Minimum cost = ', min_val)
print('Workers: ', min_group)
print()
for i in min_group:
for j in range(num_tasks):
if min_x[i, j].solution_value() > 0:
print('Worker', i,' assigned to task', j, '  Cost = ', cost[i][j])
print()

print("Time = ", total_time, "milliseconds")

def assignment(cost, group):
# Solve assignment problem for given group of workers.
num_tasks = len(cost[1])
# Clear values in x
solver = None
# Instantiate a mixed-integer solver
solver = pywraplp.Solver('TransportationProblemGroups',
pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
x = None
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)
# Objective
solver.Minimize(solver.Sum([cost[i][j] * x[i,j] for i in group
for j in range(num_tasks)]))
solver.Solve()
res = [solver, x]
return res

if __name__ == '__main__':
main()```
Full CP program
```from __future__ import print_function
from ortools.constraint_solver import pywrapcp

def main():
# Instantiate a cp solver.
solver = pywrapcp.Solver("assignment_with_patterns")
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]]
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, 11
num_workers = len(cost)
num_tasks = len(cost[1])
# 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)]
# 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)]

# Each worker is assigned to at most one task.
[solver.Add(solver.Sum(x[i][j] for j in range(num_tasks)) <= 1)
for i in range(num_workers)]

# Create variables for each worker, indicating whether they work on some task.
work = []
for i in range(num_workers):
work.append(solver.IntVar(0, 1, "work[%i]" % i))

for i in range(num_workers):
for j in range(num_tasks):
solver.Add(work[i] == solver.Sum(x[i][j] for j in range(num_tasks)))

# Define the allowed groups of worders
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))
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)
db = solver.Phase(x_array,
solver.CHOOSE_FIRST_UNBOUND,
solver.ASSIGN_MIN_VALUE)

# Create a solution collector.
collector = solver.LastSolutionCollector()
# Add decision variables

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))

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")

if __name__ == '__main__':
main()```