Assignment with Allowed Groups

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, 11
For 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.

MIP program
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()
CP-SAT program
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()

Send feedback about...