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.

## Leave a Reply