In previous posts I have already introduced Google OR tools for linear programming. In this post I want to demonstrate the capabilities of Google OR tools for constraint programming. More specifically, I will solve a job scheduling problem using constraint programming with Google OR tools.

Unlike linear programming constraint programming allows for arbitrary types of constraint functions. Moreover, constraint programming often focuses on identifying a feasible solution rather than optimal solutions. That is, in constraint programming the problem being solved might often not have an objective function to optimize.

Job scheduling is a good example of constraint programming. In this example a factory wants to make a job schedule for a week. The shift model allows for 3 shifts on all 7 days of the week, with 24 hrs operation per day.

The factory has 5 workers. A worker should not be working 2 shifts in a row on a given day. Also, the difference in amount of shifts per worker should not exceed 1 shift.

A shift can only assigned to one worker.

A worker should not work 2 shifts on the same day.

Using Google OR-tools for constraint programming I find a feasible work schedule in the code below:

# importing google or tools and declaring model template
from ortools.sat.python import cp_model
model = cp_model.CpModel()
# declare empty list that will be used for storing indices for worker-shift-day combination
shiftoptions = {}

# set number of workers, days and schedules as well as max schedules per day, 
# as well as max shift amount difference per worker
workers = 5
shifts = 3
days = 7
maxshiftsperday = 1
maxdifference = 1

# create a tuple as a shift option list index, for each combination of worker, shift and day
# use google or tools to create a boolean variable indicating if given worker works on that day, in that shift
for x in range(workers):
    for y in range(days):
        for z in range(shifts):
            shiftoptions[(x,y,z)] = model.NewBoolVar("shift with id" + str(x) + " " + str(y) + " " + str(z))

# now we add the constraint of shift only being assigned to one worker
for y in range(days):
    for z in range(shifts):
        model.Add(sum(shiftoptions[(x, y, z)] for x in range(workers)) == 1)
# now we add the constraint of a worker only working one shift per day
for x in range(workers):
    for y in range(days):
        model.Add(sum(shiftoptions[(x,y,z)] for z in range(shifts)) <= 1)
# now we add the constraint of all workers having the same amount of shifts, with some deviations allowed for with a maximum allowed difference
minshiftsperworker = (shifts * days) // workers
print(minshiftsperworker)
maxshiftsperworker = minshiftsperworker + maxdifference
for x in range(workers):
    shiftsassigned = 0
    for y in range(days):
        for z in range(shifts):
            shiftsassigned += shiftoptions[(x,y,z)]
    model.Add(minshiftsperworker <= shiftsassigned)
    model.Add(shiftsassigned <= maxshiftsperworker)

# before solving the problem I add a solution printer (this code is taken directly from Google's documentation)
class SolutionPrinterClass(cp_model.CpSolverSolutionCallback):
    def __init__(self, shiftoptions, workers, days, shifts, sols):
        val = cp_model.CpSolverSolutionCallback.__init__(self)
        self._shiftoptions = shiftoptions
        self._workers = workers
        self._days = days
        self._shifts = shifts
        self._solutions = set(sols)
        self._solution_count = 0
    def on_solution_callback(self):
        if self._solution_count in self._solutions:
            print("solution " + str(self._solution_count))
            for y in range(self._days):
                print("day " + str(y))
                for x in range(self._workers):
                    is_working = False
                    for z in range(self._shifts):
                        if self.Value(self._shiftoptions[(x,y,z)]):
                            is_working = True
                            print("worker " +str(x) +" works day " + str(y) +" shift " + str(z))
                    if not is_working:
                        print('  Worker {} does not work'.format(x))
            print()
        self._solution_count += 1
    def solution_count(self):
        return self._solution_count

# solve the model
solver = cp_model.CpSolver()
solver.parameters.linearization_level = 0
# solve it and check if solution was feasible
solutionrange = range(1) # we want to display 1 feasible results (the first one in the feasible set)
solution_printer = SolutionPrinterClass(shiftoptions, workers,
                                        days, shifts, solutionrange)
solver.SearchForAllSolutions(model, solution_printer)

4
solution 0
day 0
  Worker 0 does not work
worker 1 works day 0 shift 0
  Worker 2 does not work
worker 3 works day 0 shift 2
worker 4 works day 0 shift 1
day 1
  Worker 0 does not work
  Worker 1 does not work
worker 2 works day 1 shift 0
worker 3 works day 1 shift 2
worker 4 works day 1 shift 1
day 2
  Worker 0 does not work
  Worker 1 does not work
worker 2 works day 2 shift 0
worker 3 works day 2 shift 1
worker 4 works day 2 shift 2
day 3
worker 0 works day 3 shift 2
  Worker 1 does not work
  Worker 2 does not work
worker 3 works day 3 shift 1
worker 4 works day 3 shift 0
day 4
worker 0 works day 4 shift 0
worker 1 works day 4 shift 2
worker 2 works day 4 shift 1
  Worker 3 does not work
  Worker 4 does not work
day 5
worker 0 works day 5 shift 0
worker 1 works day 5 shift 1
worker 2 works day 5 shift 2
  Worker 3 does not work
  Worker 4 does not work
day 6
worker 0 works day 6 shift 1
worker 1 works day 6 shift 2
worker 2 works day 6 shift 0
  Worker 3 does not work
  Worker 4 does not work

This was just one of the feasible work schedules identified by the cp solver, and an example how cosntraint programming can be used for searching feasible solutions rather than “optimal” solutions.

I have written a series of posts on optimization in both Python and R, covering e.g.:

• simple linear optimization with lpSolve in R
• linear integer programming with lpSolve in R
• solving the transportation problem with lpSolve in R
• linear optimization with Pulp in Python
• linear optimization with SciPy in Python
• non-linear optimization with nloptr in R
• simple linear optimization with Google OR-tools in Python

I will keep covering additional examples in Google OR-tools, e.g. for routing problems in transportation networks.

Linnart Felkl

Data scientist focusing on simulation, optimization and modeling in R, SQL, VBA and Python