Workers and Tasks 2025-06-27

This post is mostly to try to get myself back in the habit of posting new blog content. I was looking over some of the examples in the OR-Tools repository, and I started playing around with the tasks and workers assignment problem. The original example can be found here: https://github.com/google/or-tools/blob/master/examples/python/tasks_and_workers_assignment_sat.py. In this post I go through the code bit by bit to understand what is going on, and then try some small changes to see what happens. I hope a newcomer to OR-Tools or CP-SAT might find this useful for starting their own exploration of the examples in the repository.

As is usual with the OR-Tools examples, there is very little description of the problem that the program is trying to solve. In this case, there is a one-line description at the top of the file:

Tasks and workers to group assignment to average sum(cost) / #workers.

So what this means is that there are a bunch of tasks with varying costs, and a bunch of workers. The problem is to divide workers up into groups, and have each group get some tasks. The goal is to have each worker do approximately the same amount of work.

A more practical example is to imagine a bunch of second graders setting up for a class play. If anybody works more than anybody else, they’re going to complain loudly (they are second graders, after all). There are tasks like painting, decorating, making lemonade, and so on. Nobody wants to work independently (they are second graders, after all), so the teacher figures she could use four groups and wants to parcel out the tasks to each group. The other advantage of having each person do about the same amount of work is that all the work should end at about the same time, right before the parents arrive to watch the play.

I’ll break up the original program step by step. First, the variables are declared.

Declare the important variables

# CP-SAT solver is integer only.
task_cost = [24, 10, 7, 2, 11, 16, 1, 13, 9, 27]
num_tasks = len(task_cost)
num_workers = 3
num_groups = 2
all_workers = range(num_workers)
all_groups = range(num_groups)
all_tasks = range(num_tasks)

This problem has 10 tasks, 3 workers, and 2 groups. Sometimes when I’m testing out a problem I randomize these kinds of values, just to see how the formulation performs. But it is also good to have hard-coded values so that you can directly compare the impact of model changes on the total running time of the solver.

Declare the OR Tools variables

# Variables

## x_ij = 1 if worker i is assigned to group j
x = {}
for i in all_workers:
    for j in all_groups:
        x[i, j] = model.new_bool_var("x[%i,%i]" % (i, j))

## y_kj is 1 if task k is assigned to group j
y = {}
for k in all_tasks:
    for j in all_groups:
        y[k, j] = model.new_bool_var("x[%i,%i]" % (k, j))

Next up the solver’s variables are declared. It is important to try to keep as much as possible a boolean value in CP-SAT, because then it can take advantage of boolean logic. Here a boolean is created for each worker in each group to indicate if a worker is assigned to a group. If the value is true, then the solver has assigned the worker to the group. If it is false, then it has not made that assignment.

Similarly, a boolean is created for each group to indicate if a task is assigned to the group. If the boolean is true, then the workers in the group must perform the task. If it is false, then some other group must work on it.

Note that nothing has been required yet. As it stands, the solver is free to assign no tasks to any group, and no workers to any group. Constraining these variables is the job of the next block of code.

Constrain the OR Tools variables

# Constraints

# Each task k is assigned to a group and only one.
for k in all_tasks:
    model.add(sum(y[k, j] for j in all_groups) == 1)

# Each worker i is assigned to a group and only one.
for i in all_workers:
    model.add(sum(x[i, j] for j in all_groups) == 1)

The first set of constraints say that a task must be assigned to a group, and further that the task can only be assigned to one group. This is accomplished because boolean variables are also zero-one integers. If a BoolVar is true, then it has an integer value of 1. So summing up an array of BoolVars is simply counting up those that are true. By limiting the sum to exactly 1, that means a task k must be assigned to exactly one group j.

Similarly, the second for loop requires that each worker i must be assigned to one and only one group j. Again, the sum over all of the groups for each worker must be 1, so at least one of those BoolVars must be true.

Next come the definitions of the costs per group, which feed into the objective function.

Define the average cost per group

# Cost per group
sum_of_costs = sum(task_cost)
averages = []
num_workers_in_group = []
scaled_sum_of_costs_in_group = []
scaling = 1000  # We introduce scaling to deal with floating point average.
for j in all_groups:
    n = model.new_int_var(1, num_workers, "num_workers_in_group_%i" % j)
    model.add(n == sum(x[i, j] for i in all_workers))
    c = model.new_int_var(0, sum_of_costs * scaling, "sum_of_costs_of_group_%i" % j)
    model.add(c == sum(y[k, j] * task_cost[k] * scaling for k in all_tasks))
    a = model.new_int_var(0, sum_of_costs * scaling, "average_cost_of_group_%i" % j)
    model.add_division_equality(a, c, n)

    averages.append(a)
    num_workers_in_group.append(n)
    scaled_sum_of_costs_in_group.append(c)

This code block is a bit more complex than the others. The goal here is to define the average cost per worker for each group. You don’t know in advance which task is assigned to which group, or which worker is assigned to which group, but you do have boolean variables that the solver can manipulate.

The notion of an average needs a bit more discussion. Ordinarily, one would just divide the total cost by the number of workers to get the average cost per worker. However, that generates a decimal value, which is not useful here. Newcomers to CP-SAT always seem to forget that it is an integer solver. So the concept of an average cost can’t be expressed directly. Instead, the usual procedure is to multiply the variables of interest by some constant, and then compute the fraction based on those scaled up variables. This effectively shifts the decimal place over a few places, so that the “fraction” is still an integer value.

In this example, a scaling constant of 1000 is used.

So the first variable defined for each group is the number of workers in the group. This is an IntVar ranging from 1 (every group must have at least one worker) to the total number of workers. I guess the maximum value could be the total number of workers minus the number of groups minus 1, but the solver will likely figure that out pretty quickly on its own. Then the value of this variable is set equal to the sum of the true over all workers who might belong to the jth group:

Then another IntVar is created for the cost of the tasks assigned to the group. This int var ranges from 0 (although it could be the minimum cost over all tasks, I guess) to the sum of all task costs. With an IntVar, if you get the bounds wrong, the solver will fail. So even though we know that the maximum cost assigned to a group must be less than the cost of all of the tasks, it is safe to define the cost variable with this bound. Similar to the number of tasks, the cost of all of the tasks assigned is then defined by equating the variable to the sum over all tasks that might be assigned to the jth group:

Finally the average cost for each worker in the group must be defined. This variable definition is a little bit different than the others. As before a new IntVar is declared with a minimum value of 0 and a maximum value of the sum of all of the task costs. But instead of defining the average in terms sums or divisions directly it is defined by the API call add_division_equality:

This API call links the first argument (the variable a, which represents the average) to the result of dividing the second argument (the cost of the tasks assigned to the group c) by the third (the number of workers in the group, n), or c/n. This variable is exactly what we want, the average cost of work performed by the workers assigned to that group.

The next line of code is a strange throwaway that is probably redundant.

We already specified above that all of the workers must be assigned to exactly one group, so it seems redundant to also specify that the sum of all of the individual numbers of workers per group is equal to the total number of workers. However, the solver doesn’t necessarily recognize this fact up front. It is often useful to “help” the solver by defining the relationships between secondary variables, like the individual, per-group sums of workers, with global values like the total number of workers. One could do a similar thing with the costs, but it wasn’t done here.

The final step is to define the objective value and call the solver.

Define the objective function

# Objective.
obj = model.new_int_var(0, sum_of_costs * scaling, "obj")
model.add_max_equality(obj, averages)
model.minimize(obj)

Once again, a new IntVar is defined with a minimum of 0 and a maximum of the sum of the task costs. This variable obj is then assigned a value by another API call, add_max_equality. This call assigns the value of its first argument to be the maximum value of the variables in the array passed to its second argument. In this case, that array is the list of individual group average costs. So the objective variable obj represents the maximum average cost over all of the groups.

The solver’s goal is to minimize obj, or to drive down the value of the current maximum average cost per worker for one of the groups. The only way for this cost to go down is to add a worker from another group, or to remove a task from the group and assign it to another. Both of these actions will have a simultaneous impact on another group, which will increase its average cost (either because it lost a worker or gained a task). Thus the objective will work to make all of the average costs across all of the groups as uniform as possible. Running the program produces the following.

The result of running the solver

$ time python tasks_and_workers_assignment_sat.py
Solution 0, time = 0.001703 s, objective = 60000
Solution 1, time = 0.001933 s, objective = 59500
Solution 2, time = 0.002050 s, objective = 48000
Solution 3, time = 0.002124 s, objective = 47500
Solution 4, time = 0.002195 s, objective = 43000
Solution 5, time = 0.002338 s, objective = 42500
Solution 6, time = 0.002556 s, objective = 41000
Solution 7, time = 0.002731 s, objective = 40500
Solution 8, time = 0.002808 s, objective = 40000
CpSolverResponse summary:
status: OPTIMAL
objective: 40000
best_bound: 40000
integers: 14
booleans: 24
conflicts: 3
branches: 148
propagations: 43
integer_propagations: 575
restarts: 69
lp_iterations: 0
walltime: 0.00612375
usertime: 0.00612378
deterministic_time: 0.000100229
gap_integral: 0.000675153
solution_fingerprint: 0x6fb21c535ec0e3ff

Group 0
  - worker 1
  - task 1 with cost 10
  - task 3 with cost 2
  - task 4 with cost 11
  - task 5 with cost 16
  - task 6 with cost 1
  - sum_of_costs = 40
  - average cost = 40.000000
Group 1
  - worker 0
  - worker 2
  - task 0 with cost 24
  - task 2 with cost 7
  - task 7 with cost 13
  - task 8 with cost 9
  - task 9 with cost 27
  - sum_of_costs = 80
  - average cost = 40.000000

real	0m0.412s
user	0m0.933s
sys	0m0.039s

The solver generated a double handful of solutions, found the optimum, and printed the results in a few hundredths of a second on my laptop. It worked out that one of the three workers should work alone, and the other two should form group two, and it figured out the optimal allocation of tasks to each group such that the average per-worker cost is 40.

Unfortunately, this result is so fast that it is not very useful. I want to play around with a hard problem that takes a while to solve, to see what tweaks can be done to speed things up.

The first step is to increase the number of tasks, workers, and groups.

This problem is a bit harder, as it takes between 5 and 10 seconds to settle on a good solution on my laptop, so it is actually worth switching to my fast server. However, it then sits for a very long time doing nothing, working on the lower bound to prove optimality. I had to turn on logging in order to see what the solver was doing. I also dialed the time limit down to 120s. I also noticed that the full solution dump was only being printed if the solution is optimal, so I changed that to accept feasible as well:

That let me see what was going on after the solver settles on a good solution:

The CP-SAT solver has some randomness to it, and so the time to the 14000 objective value bounces around a little bit. But the real issue seems to be the lower bound is barely moving.

So far I haven’t had much luck improving the speed of that lower bound computation, but before I get to what I did there, I want to explore the impact of some small changes to the model formulation.

First, the current constraints on the assignment of workers to groups and tasks to groups relies on summing the boolean variables and requiring that the summation equals 1. There are a few other ways to accomplish this including using the API call add_exactly_one, as so:

Using the add_exactly_one API

# Each task k is assigned to a group and only one.
for k in all_tasks:
    # model.add(sum(y[k, j] for j in all_groups) == 1)
    model.add_exactly_one([y[k, j] for j in all_groups])

# Each worker i is assigned to a group and only one.
for i in all_workers:
    # model.add(sum(x[i, j] for j in all_groups) == 1)
    model.add_exactly_one([x[i, j] for j in all_groups])

You can usually see the impact of these sorts of model formulation changes by looking at the presolve summary that is printed out when the log_search_progress parameter is set to true. The two outputs are shown below:

The solver pre-solve report from the original formulation

Presolve summary:
  - 50 affine relations were detected.
  - rule 'TODO dual: only one blocking constraint?' was applied 300 times.
  - rule 'TODO dual: only one unspecified blocking constraint?' was applied 6 times.
  - rule 'affine: new relation' was applied 50 times.
  - rule 'lin_max: rewrite with precedences' was applied 1 time.
  - rule 'linear: divide by GCD' was applied 50 times.
  - rule 'linear: positive equal one' was applied 218 times.
  - rule 'linear: reduced variable domains' was applied 1 time.
  - rule 'linear: remapped using affine relations' was applied 100 times.
  - rule 'presolve: 0 unused variables removed.' was applied 1 time.
  - rule 'presolve: iteration' was applied 2 times.
  - rule 'variables: canonicalize affine domain' was applied 50 times.

Presolved optimization model '': (model_fingerprint: 0xeab463ec229412c9)
#Variables: 11'051 (#ints: 1 in objective) (10'733 primary variables)
  - 10'900 Booleans in [0,1]
  - 50 in [0,1372]
  - 51 in [0,1372000]
  - 50 in [1,53]
#kExactlyOne: 218 (#literals: 10'900)
#kIntDiv: 50
#kLinear2: 50
#kLinearN: 101 (#terms: 11'050)

The solver pre-solve report after changing to add_exactly_one

Presolve summary:
  - 50 affine relations were detected.
  - rule 'TODO dual: only one blocking constraint?' was applied 300 times.
  - rule 'TODO dual: only one unspecified blocking constraint?' was applied 6 times.
  - rule 'affine: new relation' was applied 50 times.
  - rule 'lin_max: rewrite with precedences' was applied 1 time.
  - rule 'linear: divide by GCD' was applied 50 times.
  - rule 'linear: reduced variable domains' was applied 1 time.
  - rule 'linear: remapped using affine relations' was applied 100 times.
  - rule 'presolve: 0 unused variables removed.' was applied 1 time.
  - rule 'presolve: iteration' was applied 2 times.
  - rule 'variables: canonicalize affine domain' was applied 50 times.

Presolved optimization model '': (model_fingerprint: 0xff0d6bc8493dc98e)
#Variables: 11'051 (#ints: 1 in objective) (10'733 primary variables)
  - 10'900 Booleans in [0,1]
  - 50 in [0,1372]
  - 51 in [0,1372000]
  - 50 in [1,53]
#kExactlyOne: 218 (#literals: 10'900)
#kIntDiv: 50
#kLinear2: 50
#kLinearN: 101 (#terms: 11'050)

Inspecting these two outputs, I spot one significant difference. The first one, the version that uses the sum(bool) == 1 constraint, has the following line in the presolve summary:

The version that uses the add_exactly_one call does not. And both versions have the same number of add_exactly_one constraints:

So in this case, the presolve step is magically fixing boolean additions to use boolean logic under the hood.

Earlier in this post I suggested that one real-world problem might be a group of second graders forming into groups to work on their class play. But this solution would be terrible for that application, and perhaps for any real-world application. The problem is that the groups generated for this particular problem are very uneven.

Most of the groups have 1 worker, with two really large groups. The solver seems to be “cheating” by using very large groups with lots of tasks. To see if this was just because I used so many groups, I switched to just five, which produced the following result:

Again, one really big group with most of the tasks.

What I want is another constraint to try to make the groups roughly even sized.

The current model has a single variable as its objective. Now I want two variables, and I need to balance them against each other with weights. My first try is as follows:

I chose the weights somewhat arbitrarily. However, I know from earlier runs that the average cost value scaled optimum is 14000, which converts to a per-worker average work cost of 14.000. I also know that the size of each group is roughly on the order of 10. So if I leave both weights at 1, I would expect the solver to favor minimizing the per-worker average cost, but if it has a choice, it will do so by reducing the largest group size. Put another way, the group size has about the same impact on the objective function as the second decimal place of the average cost.

Running with this new objective, the result is much more balanced for 5 groups:

With 50 groups, the results are not quite as good. The groups range from 1 to 3 workers, and the average cost ranges from 10 to 14. So there is some compromise for that case.