This section describes 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. The allowed groups are combinations of the following pairs of workers.

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

An allowed group can be any combination of three pairs of workers, one pair from each of group1, group2, and 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.

Note that a group of workers can be a solution to the problem if it belongs to
any one of the allowed groups. In other words, the feasible set consists of points for which
any one of the
constraints is satisfied. This is an example of a *non-convex* problem.
By contrast, the MIP Example, described
previously, is a *convex* problem: for a point to be feasible, all constraints must be
satisfied.

For non-convex problems like this one, the CP-SAT solver is usually faster than a MIP solver. The following sections present solutions to the problem using the CP-SAT solver and the MIP solver, and compare the solution times for the two solvers.

## CP-SAT solution

First, we'll describe a solution to the problem using the CP-SAT solver.

### Create the data

The following code creates the data for the problem.

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]] num_workers = len(cost) num_tasks = len(cost[1])

### Create the allowed groups

To define the allowed groups of workers for the CP-SAT solver, 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.

**Note:** This way specifying the groups is slightly different
from how they are specified in the MIP solution, but it amounts to the same thing.

The following arrays define the allowed groups of workers.

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-SAT it is not necessary to create all 125 combinations of these vectors in a loop. The CP-SAT 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:
model.AddAllowedAssignments([work[0], work[1], work[2], work[3]], group1) model.AddAllowedAssignments([work[4], work[5], work[6], work[7]], group2) model.AddAllowedAssignments([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(model.NewIntVar(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.

model.Minimize(sum([np.dot(x_row, cost_row) for (x_row, cost_row) in zip(x, cost)]))

### Invoke the solver

The following code invokes the solver and displays the results.

solver = cp_model.CpSolver() status = solver.Solve(model) if status == cp_model.OPTIMAL: print('Minimum cost = %i' % solver.ObjectiveValue()) print() for i in range(num_workers): for j in range(num_tasks): if solver.Value(x[i][j]) == 1: print('Worker ', i, ' assigned to task ', j, ' Cost = ', cost[i][j]) print() end = time.time() print("Time = ", round(end - start, 4), "seconds")

### Output of the program

Here's the output of the program.

Minimum 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 = 0.0113 seconds

## MIP solution

Next, we describe a solution to the problem using the MIP solver. We omit the code that creates the data for the problem since it is the same as in the CP-SAT solution.

### Create the allowed groups

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

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]] 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)) # 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 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 = 0.3281 seconds

## Solutions times

The solution times for the two solvers are as follows:

- CP-SAT: 0.0113 seconds
- MIP: 0.3281 seconds

CP-SAT is significantly faster than MIP for this problem.

## Complete programs

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

from __future__ import print_function from ortools.linear_solver import pywraplp import time def main(): start = time.time() 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]] num_tasks = len(cost[1]) # Allowed groups of workers: 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]] 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() 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() end = time.time() print("Time = ", round(end - start, 4), "seconds") 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('AssignmentProblemGroups', 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)) # 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()

from __future__ import print_function from ortools.sat.python import cp_model import time import numpy as np def main(): model = cp_model.CpModel() start = time.time() 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]] num_workers = len(cost) num_tasks = len(cost[1]) 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 # Declare the variables. x = [] for i in range(num_workers): t = [] for j in range(num_tasks): t.append(model.NewIntVar(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. [model.Add(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. [model.Add(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(model.NewIntVar(0, 1, "work[%i]" % i)) for i in range(num_workers): for j in range(num_tasks): model.Add(work[i] == sum(x[i][j] for j in range(num_tasks))) # Define the allowed groups of worders model.AddAllowedAssignments([work[0], work[1], work[2], work[3]], group1) model.AddAllowedAssignments([work[4], work[5], work[6], work[7]], group2) model.AddAllowedAssignments([work[8], work[9], work[10], work[11]], group3) model.Minimize(sum([np.dot(x_row, cost_row) for (x_row, cost_row) in zip(x, cost)])) solver = cp_model.CpSolver() status = solver.Solve(model) if status == cp_model.OPTIMAL: print('Minimum cost = %i' % solver.ObjectiveValue()) print() for i in range(num_workers): for j in range(num_tasks): if solver.Value(x[i][j]) == 1: print('Worker ', i, ' assigned to task ', j, ' Cost = ', cost[i][j]) print() end = time.time() print("Time = ", round(end - start, 4), "seconds") if __name__ == '__main__': main()