Employee Scheduling

Organizations whose employees work multiple shifts need to schedule sufficient workers for each daily shift. Typically, the schedules will have constraints, such as "no employee should work two shifts in a row". Finding a schedule that satisfies all constraints can be computationally difficult.

The following sections present two examples of employee scheduling problems, and show how to solve them using the CP-SAT solver.

For a more sophisticated example, see this shift scheduling program on GitHub.

A nurse scheduling problem

In the next example, a hospital supervisor needs to create a schedule for four nurses over a three-day period, subject to the following conditions:

Each day is divided into three 8-hour shifts.
Every day, each shift is assigned to a single nurse, and no nurse works more than one shift.
Each nurse is assigned to at least two shifts during the three-day period.

The following sections present a solution to the nurse scheduling problem.

Import the libraries

The following code imports the required library.

Python

from ortools.sat.python import cp_model

C++

#include <stdlib.h>

#include <atomic>
#include <map>
#include <numeric>
#include <string>
#include <tuple>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"
#include "ortools/sat/model.h"
#include "ortools/sat/sat_parameters.pb.h"
#include "ortools/util/time_limit.h"

Java

import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverSolutionCallback;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.LinearExpr;
import com.google.ortools.sat.LinearExprBuilder;
import com.google.ortools.sat.Literal;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

C#

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using Google.OrTools.Sat;

Data for the example

The following code creates the data for the example.

Python

num_nurses = 4
num_shifts = 3
num_days = 3
all_nurses = range(num_nurses)
all_shifts = range(num_shifts)
all_days = range(num_days)

C++

const int num_nurses = 4;
const int num_shifts = 3;
const int num_days = 3;

std::vector<int> all_nurses(num_nurses);
std::iota(all_nurses.begin(), all_nurses.end(), 0);

std::vector<int> all_shifts(num_shifts);
std::iota(all_shifts.begin(), all_shifts.end(), 0);

std::vector<int> all_days(num_days);
std::iota(all_days.begin(), all_days.end(), 0);

Java

final int numNurses = 4;
final int numDays = 3;
final int numShifts = 3;

final int[] allNurses = IntStream.range(0, numNurses).toArray();
final int[] allDays = IntStream.range(0, numDays).toArray();
final int[] allShifts = IntStream.range(0, numShifts).toArray();

C#

const int numNurses = 4;
const int numDays = 3;
const int numShifts = 3;

int[] allNurses = Enumerable.Range(0, numNurses).ToArray();
int[] allDays = Enumerable.Range(0, numDays).ToArray();
int[] allShifts = Enumerable.Range(0, numShifts).ToArray();

Create the model

The following code creates the model.

Python

model = cp_model.CpModel()

C++

CpModelBuilder cp_model;

Java

CpModel model = new CpModel();

C#

CpModel model = new CpModel();
model.Model.Variables.Capacity = numNurses * numDays * numShifts;

Create the variables

The following code creates an array of variables.

Python

shifts = {}
for n in all_nurses:
    for d in all_days:
        for s in all_shifts:
            shifts[(n, d, s)] = model.new_bool_var(f"shift_n{n}_d{d}_s{s}")

C++

std::map<std::tuple<int, int, int>, BoolVar> shifts;
for (int n : all_nurses) {
  for (int d : all_days) {
    for (int s : all_shifts) {
      auto key = std::make_tuple(n, d, s);
      shifts[key] = cp_model.NewBoolVar().WithName(
          absl::StrFormat("shift_n%dd%ds%d", n, d, s));
    }
  }
}

Java

Literal[][][] shifts = new Literal[numNurses][numDays][numShifts];
for (int n : allNurses) {
  for (int d : allDays) {
    for (int s : allShifts) {
      shifts[n][d][s] = model.newBoolVar("shifts_n" + n + "d" + d + "s" + s);
    }
  }
}

C#

Dictionary<(int, int, int), BoolVar> shifts =
    new Dictionary<(int, int, int), BoolVar>(numNurses * numDays * numShifts);
foreach (int n in allNurses)
{
    foreach (int d in allDays)
    {
        foreach (int s in allShifts)
        {
            shifts.Add((n, d, s), model.NewBoolVar($"shifts_n{n}d{d}s{s}"));
        }
    }
}

The array defines assignments for shifts to nurses as follows: shifts[(n, d, s)] equals 1 if shift s is assigned to nurse n on day d, and 0 otherwise.

Assign nurses to shifts

Next, we show how to assign nurses to shifts subject to the following constraints:

Each shift is assigned to a single nurse per day.
Each nurse works at most one shift per day.

Here's the code that creates the first condition.

Python

for d in all_days:
    for s in all_shifts:
        model.add_exactly_one(shifts[(n, d, s)] for n in all_nurses)

C++

for (int d : all_days) {
  for (int s : all_shifts) {
    std::vector<BoolVar> nurses;
    for (int n : all_nurses) {
      auto key = std::make_tuple(n, d, s);
      nurses.push_back(shifts[key]);
    }
    cp_model.AddExactlyOne(nurses);
  }
}

Java

for (int d : allDays) {
  for (int s : allShifts) {
    List<Literal> nurses = new ArrayList<>();
    for (int n : allNurses) {
      nurses.add(shifts[n][d][s]);
    }
    model.addExactlyOne(nurses);
  }
}

C#

List<ILiteral> literals = new List<ILiteral>();
foreach (int d in allDays)
{
    foreach (int s in allShifts)
    {
        foreach (int n in allNurses)
        {
            literals.Add(shifts[(n, d, s)]);
        }
        model.AddExactlyOne(literals);
        literals.Clear();
    }
}

The last line says that for each shift, the sum of the nurses assigned to that shift is 1.

Next, here's the code that requires that each nurse works at most one shift per day.

Python

for n in all_nurses:
    for d in all_days:
        model.add_at_most_one(shifts[(n, d, s)] for s in all_shifts)

C++

for (int n : all_nurses) {
  for (int d : all_days) {
    std::vector<BoolVar> work;
    for (int s : all_shifts) {
      auto key = std::make_tuple(n, d, s);
      work.push_back(shifts[key]);
    }
    cp_model.AddAtMostOne(work);
  }
}

Java

for (int n : allNurses) {
  for (int d : allDays) {
    List<Literal> work = new ArrayList<>();
    for (int s : allShifts) {
      work.add(shifts[n][d][s]);
    }
    model.addAtMostOne(work);
  }
}

C#

foreach (int n in allNurses)
{
    foreach (int d in allDays)
    {
        foreach (int s in allShifts)
        {
            literals.Add(shifts[(n, d, s)]);
        }
        model.AddAtMostOne(literals);
        literals.Clear();
    }
}

For each nurse, the sum of shifts assigned to that nurse is at most 1 ("at most" because a nurse might have the day off).

Assign shifts evenly

Next, we show how to assign shifts to nurses as evenly as possible. Since there are nine shifts over the three-day period, we can assign two shifts to each of the four nurses. After that there will be one shift left over, which can be assigned to any nurse.

The following code ensures that each nurse works at least two shifts in the three-day period.

Python

# Try to distribute the shifts evenly, so that each nurse works
# min_shifts_per_nurse shifts. If this is not possible, because the total
# number of shifts is not divisible by the number of nurses, some nurses will
# be assigned one more shift.
min_shifts_per_nurse = (num_shifts * num_days) // num_nurses
if num_shifts * num_days % num_nurses == 0:
    max_shifts_per_nurse = min_shifts_per_nurse
else:
    max_shifts_per_nurse = min_shifts_per_nurse + 1
for n in all_nurses:
    shifts_worked = []
    for d in all_days:
        for s in all_shifts:
            shifts_worked.append(shifts[(n, d, s)])
    model.add(min_shifts_per_nurse <= sum(shifts_worked))
    model.add(sum(shifts_worked) <= max_shifts_per_nurse)

C++

// Try to distribute the shifts evenly, so that each nurse works
// min_shifts_per_nurse shifts. If this is not possible, because the total
// number of shifts is not divisible by the number of nurses, some nurses will
// be assigned one more shift.
int min_shifts_per_nurse = (num_shifts * num_days) / num_nurses;
int max_shifts_per_nurse;
if ((num_shifts * num_days) % num_nurses == 0) {
  max_shifts_per_nurse = min_shifts_per_nurse;
} else {
  max_shifts_per_nurse = min_shifts_per_nurse + 1;
}
for (int n : all_nurses) {
  std::vector<BoolVar> shifts_worked;
  for (int d : all_days) {
    for (int s : all_shifts) {
      auto key = std::make_tuple(n, d, s);
      shifts_worked.push_back(shifts[key]);
    }
  }
  cp_model.AddLessOrEqual(min_shifts_per_nurse,
                          LinearExpr::Sum(shifts_worked));
  cp_model.AddLessOrEqual(LinearExpr::Sum(shifts_worked),
                          max_shifts_per_nurse);
}

Java

// Try to distribute the shifts evenly, so that each nurse works
// minShiftsPerNurse shifts. If this is not possible, because the total
// number of shifts is not divisible by the number of nurses, some nurses will
// be assigned one more shift.
int minShiftsPerNurse = (numShifts * numDays) / numNurses;
int maxShiftsPerNurse;
if ((numShifts * numDays) % numNurses == 0) {
  maxShiftsPerNurse = minShiftsPerNurse;
} else {
  maxShiftsPerNurse = minShiftsPerNurse + 1;
}
for (int n : allNurses) {
  LinearExprBuilder shiftsWorked = LinearExpr.newBuilder();
  for (int d : allDays) {
    for (int s : allShifts) {
      shiftsWorked.add(shifts[n][d][s]);
    }
  }
  model.addLinearConstraint(shiftsWorked, minShiftsPerNurse, maxShiftsPerNurse);
}

C#

// Try to distribute the shifts evenly, so that each nurse works
// minShiftsPerNurse shifts. If this is not possible, because the total
// number of shifts is not divisible by the number of nurses, some nurses will
// be assigned one more shift.
int minShiftsPerNurse = (numShifts * numDays) / numNurses;
int maxShiftsPerNurse;
if ((numShifts * numDays) % numNurses == 0)
{
    maxShiftsPerNurse = minShiftsPerNurse;
}
else
{
    maxShiftsPerNurse = minShiftsPerNurse + 1;
}

List<IntVar> shiftsWorked = new List<IntVar>();
foreach (int n in allNurses)
{
    foreach (int d in allDays)
    {
        foreach (int s in allShifts)
        {
            shiftsWorked.Add(shifts[(n, d, s)]);
        }
    }
    model.AddLinearConstraint(LinearExpr.Sum(shiftsWorked), minShiftsPerNurse, maxShiftsPerNurse);
    shiftsWorked.Clear();
}

Since there are num_shifts * num_days total shifts in the schedule period, you can assign at least (num_shifts * num_days) // num_nurses

shifts to each nurse, but some shifts may be left over. (Here // is the Python integer division operator, which returns the floor of the usual quotient.)

For the given values of num_nurses = 4, num_shifts = 3, and num_days = 3, the expression min_shifts_per_nurse has the value (3 * 3 // 4) = 2, so you can assign at least two shifts to each nurse. This is specified by the constraint (here in Python)

model.add(min_shifts_per_nurse <= sum(shifts_worked))

Since there are nine total shifts over the three-day period, there is one remaining shift after assigning two shifts to each nurse. The extra shift can be assigned to any nurse.

The final line (here in Python)

model.add(sum(shifts_worked) <= max_shifts_per_nurse)

ensures that no nurse is assigned more than one extra shift.

The constraint isn't necessary in this case, because there's only one extra shift. But for different parameter values, there could be several extra shifts, in which case the constraint is necessary.

Update solver parameters

In a non-optimization model, you can enable the search for all solutions.

Python

solver = cp_model.CpSolver()
solver.parameters.linearization_level = 0
# Enumerate all solutions.
solver.parameters.enumerate_all_solutions = True

C++

Model model;
SatParameters parameters;
parameters.set_linearization_level(0);
// Enumerate all solutions.
parameters.set_enumerate_all_solutions(true);
model.Add(NewSatParameters(parameters));

Java

CpSolver solver = new CpSolver();
solver.getParameters().setLinearizationLevel(0);
// Tell the solver to enumerate all solutions.
solver.getParameters().setEnumerateAllSolutions(true);

C#

CpSolver solver = new CpSolver();
// Tell the solver to enumerate all solutions.
solver.StringParameters += "linearization_level:0 " + "enumerate_all_solutions:true ";

Register a Solutions Callback

You need to register a callback on the solver that will be called at each solution.

Python

class NursesPartialSolutionPrinter(cp_model.CpSolverSolutionCallback):
    """Print intermediate solutions."""

    def __init__(self, shifts, num_nurses, num_days, num_shifts, limit):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self._shifts = shifts
        self._num_nurses = num_nurses
        self._num_days = num_days
        self._num_shifts = num_shifts
        self._solution_count = 0
        self._solution_limit = limit

    def on_solution_callback(self):
        self._solution_count += 1
        print(f"Solution {self._solution_count}")
        for d in range(self._num_days):
            print(f"Day {d}")
            for n in range(self._num_nurses):
                is_working = False
                for s in range(self._num_shifts):
                    if self.value(self._shifts[(n, d, s)]):
                        is_working = True
                        print(f"  Nurse {n} works shift {s}")
                if not is_working:
                    print(f"  Nurse {n} does not work")
        if self._solution_count >= self._solution_limit:
            print(f"Stop search after {self._solution_limit} solutions")
            self.stop_search()

    def solutionCount(self):
        return self._solution_count

# Display the first five solutions.
solution_limit = 5
solution_printer = NursesPartialSolutionPrinter(
    shifts, num_nurses, num_days, num_shifts, solution_limit
)

C++

// Create an atomic Boolean that will be periodically checked by the limit.
std::atomic<bool> stopped(false);
model.GetOrCreate<TimeLimit>()->RegisterExternalBooleanAsLimit(&stopped);

const int kSolutionLimit = 5;
int num_solutions = 0;
model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse& r) {
  LOG(INFO) << "Solution " << num_solutions;
  for (int d : all_days) {
    LOG(INFO) << "Day " << std::to_string(d);
    for (int n : all_nurses) {
      bool is_working = false;
      for (int s : all_shifts) {
        auto key = std::make_tuple(n, d, s);
        if (SolutionIntegerValue(r, shifts[key])) {
          is_working = true;
          LOG(INFO) << "  Nurse " << std::to_string(n) << " works shift "
                    << std::to_string(s);
        }
      }
      if (!is_working) {
        LOG(INFO) << "  Nurse " << std::to_string(n) << " does not work";
      }
    }
  }
  num_solutions++;
  if (num_solutions >= kSolutionLimit) {
    stopped = true;
    LOG(INFO) << "Stop search after " << kSolutionLimit << " solutions.";
  }
}));

Java

final int solutionLimit = 5;
class VarArraySolutionPrinterWithLimit extends CpSolverSolutionCallback {
  public VarArraySolutionPrinterWithLimit(
      int[] allNurses, int[] allDays, int[] allShifts, Literal[][][] shifts, int limit) {
    solutionCount = 0;
    this.allNurses = allNurses;
    this.allDays = allDays;
    this.allShifts = allShifts;
    this.shifts = shifts;
    solutionLimit = limit;
  }

  @Override
  public void onSolutionCallback() {
    System.out.printf("Solution #%d:%n", solutionCount);
    for (int d : allDays) {
      System.out.printf("Day %d%n", d);
      for (int n : allNurses) {
        boolean isWorking = false;
        for (int s : allShifts) {
          if (booleanValue(shifts[n][d][s])) {
            isWorking = true;
            System.out.printf("  Nurse %d work shift %d%n", n, s);
          }
        }
        if (!isWorking) {
          System.out.printf("  Nurse %d does not work%n", n);
        }
      }
    }
    solutionCount++;
    if (solutionCount >= solutionLimit) {
      System.out.printf("Stop search after %d solutions%n", solutionLimit);
      stopSearch();
    }
  }

  public int getSolutionCount() {
    return solutionCount;
  }

  private int solutionCount;
  private final int[] allNurses;
  private final int[] allDays;
  private final int[] allShifts;
  private final Literal[][][] shifts;
  private final int solutionLimit;
}

VarArraySolutionPrinterWithLimit cb =
    new VarArraySolutionPrinterWithLimit(allNurses, allDays, allShifts, shifts, solutionLimit);

C#

First define the SolutionPrinter class.

public class SolutionPrinter : CpSolverSolutionCallback
{
    public SolutionPrinter(int[] allNurses, int[] allDays, int[] allShifts,
                           Dictionary<(int, int, int), BoolVar> shifts, int limit)
    {
        solutionCount_ = 0;
        allNurses_ = allNurses;
        allDays_ = allDays;
        allShifts_ = allShifts;
        shifts_ = shifts;
        solutionLimit_ = limit;
    }

    public override void OnSolutionCallback()
    {
        Console.WriteLine($"Solution #{solutionCount_}:");
        foreach (int d in allDays_)
        {
            Console.WriteLine($"Day {d}");
            foreach (int n in allNurses_)
            {
                bool isWorking = false;
                foreach (int s in allShifts_)
                {
                    if (Value(shifts_[(n, d, s)]) == 1L)
                    {
                        isWorking = true;
                        Console.WriteLine($"  Nurse {n} work shift {s}");
                    }
                }
                if (!isWorking)
                {
                    Console.WriteLine($"  Nurse {d} does not work");
                }
            }
        }
        solutionCount_++;
        if (solutionCount_ >= solutionLimit_)
        {
            Console.WriteLine($"Stop search after {solutionLimit_} solutions");
            StopSearch();
        }
    }

    public int SolutionCount()
    {
        return solutionCount_;
    }

    private int solutionCount_;
    private int[] allNurses_;
    private int[] allDays_;
    private int[] allShifts_;
    private Dictionary<(int, int, int), BoolVar> shifts_;
    private int solutionLimit_;
}

Then instantiate it using:

const int solutionLimit = 5;
SolutionPrinter cb = new SolutionPrinter(allNurses, allDays, allShifts, shifts, solutionLimit);

Invoke the solver

The following code calls the solver and displays the first five solutions.

Python

solver.solve(model, solution_printer)

C++

const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model);

Java

CpSolverStatus status = solver.solve(model, cb);
System.out.println("Status: " + status);
System.out.println(cb.getSolutionCount() + " solutions found.");

C#

CpSolverStatus status = solver.Solve(model, cb);
Console.WriteLine($"Solve status: {status}");

Solutions

Here are the first five solutions.

Solution 0
Day 0
Nurse 0 does not work
Nurse 1 works shift 0
Nurse 2 works shift 1
Nurse 3 works shift 2
Day 1
Nurse 0 works shift 2
Nurse 1 does not work
Nurse 2 works shift 1
Nurse 3 works shift 0
Day 2
Nurse 0 works shift 2
Nurse 1 works shift 1
Nurse 2 works shift 0
Nurse 3 does not work

Solution 1
Day 0
Nurse 0 works shift 0
Nurse 1 does not work
Nurse 2 works shift 1
Nurse 3 works shift 2
Day 1
Nurse 0 does not work
Nurse 1 works shift 2
Nurse 2 works shift 1
Nurse 3 works shift 0
Day 2
Nurse 0 works shift 2
Nurse 1 works shift 1
Nurse 2 works shift 0
Nurse 3 does not work

Solution 2
Day 0 Nurse 0 works shift 0
Nurse 1 does not work
Nurse 2 works shift 1
Nurse 3 works shift 2
Day 1
Nurse 0 works shift 1
Nurse 1 works shift 2
Nurse 2 does not work
Nurse 3 works shift 0
Day 2
Nurse 0 works shift 2
Nurse 1 works shift 1
Nurse 2 works shift 0
Nurse 3 does not work

Solution 3
Day 0 Nurse 0 does not work
Nurse 1 works shift 0
Nurse 2 works shift 1
Nurse 3 works shift 2
Day 1
Nurse 0 works shift 1
Nurse 1 works shift 2
Nurse 2 does not work
Nurse 3 works shift 0
Day 2
Nurse 0 works shift 2
Nurse 1 works shift 1
Nurse 2 works shift 0
Nurse 3 does not work

Solution 4
Day 0
Nurse 0 does not work
Nurse 1 works shift 0
Nurse 2 works shift 1
Nurse 3 works shift 2
Day 1
Nurse 0 works shift 2
Nurse 1 works shift 1
Nurse 2 does not work
Nurse 3 works shift 0
Day 2
Nurse 0 works shift 2
Nurse 1 works shift 1
Nurse 2 works shift 0
Nurse 3 does not work

Statistics
  - conflicts      : 5
  - branches       : 142
  - wall time      : 0.002484 s
  - solutions found: 5

The total number of solutions is 5184. The following counting argument explains why.

First, there are 4 choices for the one nurse who works an extra shift. Having chosen that nurse, there are 3 shifts the nurse can be assigned to on each of the 3 days, so the number of possible ways to assign the nurse with the extra shift is 4 · 3³ = 108. After assigning this nurse, there are two remaining unassigned shifts on each day.

Of the remaining three nurses, one works days 0 and 1, one works days 0 and 2, and one works days 1 and 2. There are 3! = 6 ways to assign the nurses to these days, as shown in the diagram below. (The three nurses are labeled A, B, and C, and we have not yet assigned them to shifts.)

Day 0    Day 1    Day 2
 A B      A C      B C
 A B      B C      A C
 A C      A B      B C
 A C      B C      A B
 B C      A B      A C
 B C      A C      A B

For each row in the above diagram, there are 2³ = 8 possible ways to assign the remaining shifts to the nurses (two choices on each day). So the total number of possible assignments is 108·6·8 = 5184.

Entire program

Here is the entire program for the nurse scheduling problem.

Python

"""Example of a simple nurse scheduling problem."""
from ortools.sat.python import cp_model


def main() -> None:
    # Data.
    num_nurses = 4
    num_shifts = 3
    num_days = 3
    all_nurses = range(num_nurses)
    all_shifts = range(num_shifts)
    all_days = range(num_days)

    # Creates the model.
    model = cp_model.CpModel()

    # Creates shift variables.
    # shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'.
    shifts = {}
    for n in all_nurses:
        for d in all_days:
            for s in all_shifts:
                shifts[(n, d, s)] = model.new_bool_var(f"shift_n{n}_d{d}_s{s}")

    # Each shift is assigned to exactly one nurse in the schedule period.
    for d in all_days:
        for s in all_shifts:
            model.add_exactly_one(shifts[(n, d, s)] for n in all_nurses)

    # Each nurse works at most one shift per day.
    for n in all_nurses:
        for d in all_days:
            model.add_at_most_one(shifts[(n, d, s)] for s in all_shifts)

    # Try to distribute the shifts evenly, so that each nurse works
    # min_shifts_per_nurse shifts. If this is not possible, because the total
    # number of shifts is not divisible by the number of nurses, some nurses will
    # be assigned one more shift.
    min_shifts_per_nurse = (num_shifts * num_days) // num_nurses
    if num_shifts * num_days % num_nurses == 0:
        max_shifts_per_nurse = min_shifts_per_nurse
    else:
        max_shifts_per_nurse = min_shifts_per_nurse + 1
    for n in all_nurses:
        shifts_worked = []
        for d in all_days:
            for s in all_shifts:
                shifts_worked.append(shifts[(n, d, s)])
        model.add(min_shifts_per_nurse <= sum(shifts_worked))
        model.add(sum(shifts_worked) <= max_shifts_per_nurse)

    # Creates the solver and solve.
    solver = cp_model.CpSolver()
    solver.parameters.linearization_level = 0
    # Enumerate all solutions.
    solver.parameters.enumerate_all_solutions = True

    class NursesPartialSolutionPrinter(cp_model.CpSolverSolutionCallback):
        """Print intermediate solutions."""

        def __init__(self, shifts, num_nurses, num_days, num_shifts, limit):
            cp_model.CpSolverSolutionCallback.__init__(self)
            self._shifts = shifts
            self._num_nurses = num_nurses
            self._num_days = num_days
            self._num_shifts = num_shifts
            self._solution_count = 0
            self._solution_limit = limit

        def on_solution_callback(self):
            self._solution_count += 1
            print(f"Solution {self._solution_count}")
            for d in range(self._num_days):
                print(f"Day {d}")
                for n in range(self._num_nurses):
                    is_working = False
                    for s in range(self._num_shifts):
                        if self.value(self._shifts[(n, d, s)]):
                            is_working = True
                            print(f"  Nurse {n} works shift {s}")
                    if not is_working:
                        print(f"  Nurse {n} does not work")
            if self._solution_count >= self._solution_limit:
                print(f"Stop search after {self._solution_limit} solutions")
                self.stop_search()

        def solutionCount(self):
            return self._solution_count

    # Display the first five solutions.
    solution_limit = 5
    solution_printer = NursesPartialSolutionPrinter(
        shifts, num_nurses, num_days, num_shifts, solution_limit
    )

    solver.solve(model, solution_printer)

    # Statistics.
    print("\nStatistics")
    print(f"  - conflicts      : {solver.num_conflicts}")
    print(f"  - branches       : {solver.num_branches}")
    print(f"  - wall time      : {solver.wall_time} s")
    print(f"  - solutions found: {solution_printer.solutionCount()}")


if __name__ == "__main__":
    main()

C++

// Example of a simple nurse scheduling problem.
#include <stdlib.h>

#include <atomic>
#include <map>
#include <numeric>
#include <string>
#include <tuple>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"
#include "ortools/sat/model.h"
#include "ortools/sat/sat_parameters.pb.h"
#include "ortools/util/time_limit.h"

namespace operations_research {
namespace sat {

void NurseSat() {
  const int num_nurses = 4;
  const int num_shifts = 3;
  const int num_days = 3;

  std::vector<int> all_nurses(num_nurses);
  std::iota(all_nurses.begin(), all_nurses.end(), 0);

  std::vector<int> all_shifts(num_shifts);
  std::iota(all_shifts.begin(), all_shifts.end(), 0);

  std::vector<int> all_days(num_days);
  std::iota(all_days.begin(), all_days.end(), 0);

  // Creates the model.
  CpModelBuilder cp_model;

  // Creates shift variables.
  // shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'.
  std::map<std::tuple<int, int, int>, BoolVar> shifts;
  for (int n : all_nurses) {
    for (int d : all_days) {
      for (int s : all_shifts) {
        auto key = std::make_tuple(n, d, s);
        shifts[key] = cp_model.NewBoolVar().WithName(
            absl::StrFormat("shift_n%dd%ds%d", n, d, s));
      }
    }
  }

  // Each shift is assigned to exactly one nurse in the schedule period.
  for (int d : all_days) {
    for (int s : all_shifts) {
      std::vector<BoolVar> nurses;
      for (int n : all_nurses) {
        auto key = std::make_tuple(n, d, s);
        nurses.push_back(shifts[key]);
      }
      cp_model.AddExactlyOne(nurses);
    }
  }

  // Each nurse works at most one shift per day.
  for (int n : all_nurses) {
    for (int d : all_days) {
      std::vector<BoolVar> work;
      for (int s : all_shifts) {
        auto key = std::make_tuple(n, d, s);
        work.push_back(shifts[key]);
      }
      cp_model.AddAtMostOne(work);
    }
  }

  // Try to distribute the shifts evenly, so that each nurse works
  // min_shifts_per_nurse shifts. If this is not possible, because the total
  // number of shifts is not divisible by the number of nurses, some nurses will
  // be assigned one more shift.
  int min_shifts_per_nurse = (num_shifts * num_days) / num_nurses;
  int max_shifts_per_nurse;
  if ((num_shifts * num_days) % num_nurses == 0) {
    max_shifts_per_nurse = min_shifts_per_nurse;
  } else {
    max_shifts_per_nurse = min_shifts_per_nurse + 1;
  }
  for (int n : all_nurses) {
    std::vector<BoolVar> shifts_worked;
    for (int d : all_days) {
      for (int s : all_shifts) {
        auto key = std::make_tuple(n, d, s);
        shifts_worked.push_back(shifts[key]);
      }
    }
    cp_model.AddLessOrEqual(min_shifts_per_nurse,
                            LinearExpr::Sum(shifts_worked));
    cp_model.AddLessOrEqual(LinearExpr::Sum(shifts_worked),
                            max_shifts_per_nurse);
  }

  Model model;
  SatParameters parameters;
  parameters.set_linearization_level(0);
  // Enumerate all solutions.
  parameters.set_enumerate_all_solutions(true);
  model.Add(NewSatParameters(parameters));

  // Display the first five solutions.
  // Create an atomic Boolean that will be periodically checked by the limit.
  std::atomic<bool> stopped(false);
  model.GetOrCreate<TimeLimit>()->RegisterExternalBooleanAsLimit(&stopped);

  const int kSolutionLimit = 5;
  int num_solutions = 0;
  model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse& r) {
    LOG(INFO) << "Solution " << num_solutions;
    for (int d : all_days) {
      LOG(INFO) << "Day " << std::to_string(d);
      for (int n : all_nurses) {
        bool is_working = false;
        for (int s : all_shifts) {
          auto key = std::make_tuple(n, d, s);
          if (SolutionIntegerValue(r, shifts[key])) {
            is_working = true;
            LOG(INFO) << "  Nurse " << std::to_string(n) << " works shift "
                      << std::to_string(s);
          }
        }
        if (!is_working) {
          LOG(INFO) << "  Nurse " << std::to_string(n) << " does not work";
        }
      }
    }
    num_solutions++;
    if (num_solutions >= kSolutionLimit) {
      stopped = true;
      LOG(INFO) << "Stop search after " << kSolutionLimit << " solutions.";
    }
  }));

  const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model);

  // Statistics.
  LOG(INFO) << "Statistics";
  LOG(INFO) << CpSolverResponseStats(response);
  LOG(INFO) << "solutions found : " << std::to_string(num_solutions);
}

}  // namespace sat
}  // namespace operations_research

int main() {
  operations_research::sat::NurseSat();
  return EXIT_SUCCESS;
}

Java

package com.google.ortools.sat.samples;
import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverSolutionCallback;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.LinearExpr;
import com.google.ortools.sat.LinearExprBuilder;
import com.google.ortools.sat.Literal;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

/** Nurses problem. */
public class NursesSat {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    final int numNurses = 4;
    final int numDays = 3;
    final int numShifts = 3;

    final int[] allNurses = IntStream.range(0, numNurses).toArray();
    final int[] allDays = IntStream.range(0, numDays).toArray();
    final int[] allShifts = IntStream.range(0, numShifts).toArray();

    // Creates the model.
    CpModel model = new CpModel();

    // Creates shift variables.
    // shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'.
    Literal[][][] shifts = new Literal[numNurses][numDays][numShifts];
    for (int n : allNurses) {
      for (int d : allDays) {
        for (int s : allShifts) {
          shifts[n][d][s] = model.newBoolVar("shifts_n" + n + "d" + d + "s" + s);
        }
      }
    }

    // Each shift is assigned to exactly one nurse in the schedule period.
    for (int d : allDays) {
      for (int s : allShifts) {
        List<Literal> nurses = new ArrayList<>();
        for (int n : allNurses) {
          nurses.add(shifts[n][d][s]);
        }
        model.addExactlyOne(nurses);
      }
    }

    // Each nurse works at most one shift per day.
    for (int n : allNurses) {
      for (int d : allDays) {
        List<Literal> work = new ArrayList<>();
        for (int s : allShifts) {
          work.add(shifts[n][d][s]);
        }
        model.addAtMostOne(work);
      }
    }

    // Try to distribute the shifts evenly, so that each nurse works
    // minShiftsPerNurse shifts. If this is not possible, because the total
    // number of shifts is not divisible by the number of nurses, some nurses will
    // be assigned one more shift.
    int minShiftsPerNurse = (numShifts * numDays) / numNurses;
    int maxShiftsPerNurse;
    if ((numShifts * numDays) % numNurses == 0) {
      maxShiftsPerNurse = minShiftsPerNurse;
    } else {
      maxShiftsPerNurse = minShiftsPerNurse + 1;
    }
    for (int n : allNurses) {
      LinearExprBuilder shiftsWorked = LinearExpr.newBuilder();
      for (int d : allDays) {
        for (int s : allShifts) {
          shiftsWorked.add(shifts[n][d][s]);
        }
      }
      model.addLinearConstraint(shiftsWorked, minShiftsPerNurse, maxShiftsPerNurse);
    }

    CpSolver solver = new CpSolver();
    solver.getParameters().setLinearizationLevel(0);
    // Tell the solver to enumerate all solutions.
    solver.getParameters().setEnumerateAllSolutions(true);

    // Display the first five solutions.
    final int solutionLimit = 5;
    class VarArraySolutionPrinterWithLimit extends CpSolverSolutionCallback {
      public VarArraySolutionPrinterWithLimit(
          int[] allNurses, int[] allDays, int[] allShifts, Literal[][][] shifts, int limit) {
        solutionCount = 0;
        this.allNurses = allNurses;
        this.allDays = allDays;
        this.allShifts = allShifts;
        this.shifts = shifts;
        solutionLimit = limit;
      }

      @Override
      public void onSolutionCallback() {
        System.out.printf("Solution #%d:%n", solutionCount);
        for (int d : allDays) {
          System.out.printf("Day %d%n", d);
          for (int n : allNurses) {
            boolean isWorking = false;
            for (int s : allShifts) {
              if (booleanValue(shifts[n][d][s])) {
                isWorking = true;
                System.out.printf("  Nurse %d work shift %d%n", n, s);
              }
            }
            if (!isWorking) {
              System.out.printf("  Nurse %d does not work%n", n);
            }
          }
        }
        solutionCount++;
        if (solutionCount >= solutionLimit) {
          System.out.printf("Stop search after %d solutions%n", solutionLimit);
          stopSearch();
        }
      }

      public int getSolutionCount() {
        return solutionCount;
      }

      private int solutionCount;
      private final int[] allNurses;
      private final int[] allDays;
      private final int[] allShifts;
      private final Literal[][][] shifts;
      private final int solutionLimit;
    }

    VarArraySolutionPrinterWithLimit cb =
        new VarArraySolutionPrinterWithLimit(allNurses, allDays, allShifts, shifts, solutionLimit);

    // Creates a solver and solves the model.
    CpSolverStatus status = solver.solve(model, cb);
    System.out.println("Status: " + status);
    System.out.println(cb.getSolutionCount() + " solutions found.");

    // Statistics.
    System.out.println("Statistics");
    System.out.printf("  conflicts: %d%n", solver.numConflicts());
    System.out.printf("  branches : %d%n", solver.numBranches());
    System.out.printf("  wall time: %f s%n", solver.wallTime());
  }

  private NursesSat() {}
}

C#

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using Google.OrTools.Sat;

public class NursesSat
{
    public class SolutionPrinter : CpSolverSolutionCallback
    {
        public SolutionPrinter(int[] allNurses, int[] allDays, int[] allShifts,
                               Dictionary<(int, int, int), BoolVar> shifts, int limit)
        {
            solutionCount_ = 0;
            allNurses_ = allNurses;
            allDays_ = allDays;
            allShifts_ = allShifts;
            shifts_ = shifts;
            solutionLimit_ = limit;
        }

        public override void OnSolutionCallback()
        {
            Console.WriteLine($"Solution #{solutionCount_}:");
            foreach (int d in allDays_)
            {
                Console.WriteLine($"Day {d}");
                foreach (int n in allNurses_)
                {
                    bool isWorking = false;
                    foreach (int s in allShifts_)
                    {
                        if (Value(shifts_[(n, d, s)]) == 1L)
                        {
                            isWorking = true;
                            Console.WriteLine($"  Nurse {n} work shift {s}");
                        }
                    }
                    if (!isWorking)
                    {
                        Console.WriteLine($"  Nurse {d} does not work");
                    }
                }
            }
            solutionCount_++;
            if (solutionCount_ >= solutionLimit_)
            {
                Console.WriteLine($"Stop search after {solutionLimit_} solutions");
                StopSearch();
            }
        }

        public int SolutionCount()
        {
            return solutionCount_;
        }

        private int solutionCount_;
        private int[] allNurses_;
        private int[] allDays_;
        private int[] allShifts_;
        private Dictionary<(int, int, int), BoolVar> shifts_;
        private int solutionLimit_;
    }

    public static void Main(String[] args)
    {
        const int numNurses = 4;
        const int numDays = 3;
        const int numShifts = 3;

        int[] allNurses = Enumerable.Range(0, numNurses).ToArray();
        int[] allDays = Enumerable.Range(0, numDays).ToArray();
        int[] allShifts = Enumerable.Range(0, numShifts).ToArray();

        // Creates the model.
        CpModel model = new CpModel();
        model.Model.Variables.Capacity = numNurses * numDays * numShifts;

        // Creates shift variables.
        // shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'.
        Dictionary<(int, int, int), BoolVar> shifts =
            new Dictionary<(int, int, int), BoolVar>(numNurses * numDays * numShifts);
        foreach (int n in allNurses)
        {
            foreach (int d in allDays)
            {
                foreach (int s in allShifts)
                {
                    shifts.Add((n, d, s), model.NewBoolVar($"shifts_n{n}d{d}s{s}"));
                }
            }
        }

        // Each shift is assigned to exactly one nurse in the schedule period.
        List<ILiteral> literals = new List<ILiteral>();
        foreach (int d in allDays)
        {
            foreach (int s in allShifts)
            {
                foreach (int n in allNurses)
                {
                    literals.Add(shifts[(n, d, s)]);
                }
                model.AddExactlyOne(literals);
                literals.Clear();
            }
        }

        // Each nurse works at most one shift per day.
        foreach (int n in allNurses)
        {
            foreach (int d in allDays)
            {
                foreach (int s in allShifts)
                {
                    literals.Add(shifts[(n, d, s)]);
                }
                model.AddAtMostOne(literals);
                literals.Clear();
            }
        }

        // Try to distribute the shifts evenly, so that each nurse works
        // minShiftsPerNurse shifts. If this is not possible, because the total
        // number of shifts is not divisible by the number of nurses, some nurses will
        // be assigned one more shift.
        int minShiftsPerNurse = (numShifts * numDays) / numNurses;
        int maxShiftsPerNurse;
        if ((numShifts * numDays) % numNurses == 0)
        {
            maxShiftsPerNurse = minShiftsPerNurse;
        }
        else
        {
            maxShiftsPerNurse = minShiftsPerNurse + 1;
        }

        List<IntVar> shiftsWorked = new List<IntVar>();
        foreach (int n in allNurses)
        {
            foreach (int d in allDays)
            {
                foreach (int s in allShifts)
                {
                    shiftsWorked.Add(shifts[(n, d, s)]);
                }
            }
            model.AddLinearConstraint(LinearExpr.Sum(shiftsWorked), minShiftsPerNurse, maxShiftsPerNurse);
            shiftsWorked.Clear();
        }

        CpSolver solver = new CpSolver();
        // Tell the solver to enumerate all solutions.
        solver.StringParameters += "linearization_level:0 " + "enumerate_all_solutions:true ";

        // Display the first five solutions.
        const int solutionLimit = 5;
        SolutionPrinter cb = new SolutionPrinter(allNurses, allDays, allShifts, shifts, solutionLimit);

        // Solve
        CpSolverStatus status = solver.Solve(model, cb);
        Console.WriteLine($"Solve status: {status}");

        Console.WriteLine("Statistics");
        Console.WriteLine($"  conflicts: {solver.NumConflicts()}");
        Console.WriteLine($"  branches : {solver.NumBranches()}");
        Console.WriteLine($"  wall time: {solver.WallTime()}s");
    }
}

Scheduling with shift requests

In this section, we take the previous example and add nurse requests for specific shifts. We then look for a schedule that maximizes the number of requests that are met. For most scheduling problems, it's best to optimize an objective function, as it is usually not practical to print all possible schedules.

This example has the same constraints as the previous example.

Import the libraries

The following code imports the required library.

Python

from typing import Union

from ortools.sat.python import cp_model

C++

#include <stdlib.h>

#include <cstdint>
#include <map>
#include <numeric>
#include <string>
#include <tuple>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"

Java

import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.LinearExpr;
import com.google.ortools.sat.LinearExprBuilder;
import com.google.ortools.sat.Literal;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

C#

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Sat;

Data for the example

The data for this example is shown after.

Python

num_nurses = 5
num_shifts = 3
num_days = 7
all_nurses = range(num_nurses)
all_shifts = range(num_shifts)
all_days = range(num_days)
shift_requests = [
    [[0, 0, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 1]],
    [[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 1, 0], [1, 0, 0], [0, 0, 0], [0, 0, 1]],
    [[0, 1, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0], [0, 1, 0], [0, 0, 0]],
    [[0, 0, 1], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0]],
    [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0]],
]

C++

const int num_nurses = 5;
const int num_days = 7;
const int num_shifts = 3;

std::vector<int> all_nurses(num_nurses);
std::iota(all_nurses.begin(), all_nurses.end(), 0);

std::vector<int> all_days(num_days);
std::iota(all_days.begin(), all_days.end(), 0);

std::vector<int> all_shifts(num_shifts);
std::iota(all_shifts.begin(), all_shifts.end(), 0);

std::vector<std::vector<std::vector<int64_t>>> shift_requests = {
    {
        {0, 0, 1},
        {0, 0, 0},
        {0, 0, 0},
        {0, 0, 0},
        {0, 0, 1},
        {0, 1, 0},
        {0, 0, 1},
    },
    {
        {0, 0, 0},
        {0, 0, 0},
        {0, 1, 0},
        {0, 1, 0},
        {1, 0, 0},
        {0, 0, 0},
        {0, 0, 1},
    },
    {
        {0, 1, 0},
        {0, 1, 0},
        {0, 0, 0},
        {1, 0, 0},
        {0, 0, 0},
        {0, 1, 0},
        {0, 0, 0},
    },
    {
        {0, 0, 1},
        {0, 0, 0},
        {1, 0, 0},
        {0, 1, 0},
        {0, 0, 0},
        {1, 0, 0},
        {0, 0, 0},
    },
    {
        {0, 0, 0},
        {0, 0, 1},
        {0, 1, 0},
        {0, 0, 0},
        {1, 0, 0},
        {0, 1, 0},
        {0, 0, 0},
    },
};

Java

final int numNurses = 5;
final int numDays = 7;
final int numShifts = 3;

final int[] allNurses = IntStream.range(0, numNurses).toArray();
final int[] allDays = IntStream.range(0, numDays).toArray();
final int[] allShifts = IntStream.range(0, numShifts).toArray();

final int[][][] shiftRequests = new int[][][] {
    {
        {0, 0, 1},
        {0, 0, 0},
        {0, 0, 0},
        {0, 0, 0},
        {0, 0, 1},
        {0, 1, 0},
        {0, 0, 1},
    },
    {
        {0, 0, 0},
        {0, 0, 0},
        {0, 1, 0},
        {0, 1, 0},
        {1, 0, 0},
        {0, 0, 0},
        {0, 0, 1},
    },
    {
        {0, 1, 0},
        {0, 1, 0},
        {0, 0, 0},
        {1, 0, 0},
        {0, 0, 0},
        {0, 1, 0},
        {0, 0, 0},
    },
    {
        {0, 0, 1},
        {0, 0, 0},
        {1, 0, 0},
        {0, 1, 0},
        {0, 0, 0},
        {1, 0, 0},
        {0, 0, 0},
    },
    {
        {0, 0, 0},
        {0, 0, 1},
        {0, 1, 0},
        {0, 0, 0},
        {1, 0, 0},
        {0, 1, 0},
        {0, 0, 0},
    },
};

C#

const int numNurses = 5;
const int numDays = 7;
const int numShifts = 3;

int[] allNurses = Enumerable.Range(0, numNurses).ToArray();
int[] allDays = Enumerable.Range(0, numDays).ToArray();
int[] allShifts = Enumerable.Range(0, numShifts).ToArray();

int[,,] shiftRequests = new int[,,] {
    {
        { 0, 0, 1 },
        { 0, 0, 0 },
        { 0, 0, 0 },
        { 0, 0, 0 },
        { 0, 0, 1 },
        { 0, 1, 0 },
        { 0, 0, 1 },
    },
    {
        { 0, 0, 0 },
        { 0, 0, 0 },
        { 0, 1, 0 },
        { 0, 1, 0 },
        { 1, 0, 0 },
        { 0, 0, 0 },
        { 0, 0, 1 },
    },
    {
        { 0, 1, 0 },
        { 0, 1, 0 },
        { 0, 0, 0 },
        { 1, 0, 0 },
        { 0, 0, 0 },
        { 0, 1, 0 },
        { 0, 0, 0 },
    },
    {
        { 0, 0, 1 },
        { 0, 0, 0 },
        { 1, 0, 0 },
        { 0, 1, 0 },
        { 0, 0, 0 },
        { 1, 0, 0 },
        { 0, 0, 0 },
    },
    {
        { 0, 0, 0 },
        { 0, 0, 1 },
        { 0, 1, 0 },
        { 0, 0, 0 },
        { 1, 0, 0 },
        { 0, 1, 0 },
        { 0, 0, 0 },
    },
};

Create the model

The following code creates the model.

Python

model = cp_model.CpModel()

C++

CpModelBuilder cp_model;

Java

CpModel model = new CpModel();

C#

CpModel model = new CpModel();

Create the variables

The following code an array of variables for the problem.

In addition to the variables from the previous example, the data also contains a set of triples, corresponding to the three shifts per day. Each element of the triple is 0 or 1, indicating whether a shift was requested. For example, the triple [0, 0, 1] in the fifth position of row 1 indicates that nurse 1 requests shift 3 on day 5.

Python

shifts = {}
for n in all_nurses:
    for d in all_days:
        for s in all_shifts:
            shifts[(n, d, s)] = model.new_bool_var(f"shift_n{n}_d{d}_s{s}")

C++

std::map<std::tuple<int, int, int>, BoolVar> shifts;
for (int n : all_nurses) {
  for (int d : all_days) {
    for (int s : all_shifts) {
      auto key = std::make_tuple(n, d, s);
      shifts[key] = cp_model.NewBoolVar().WithName(
          absl::StrFormat("shift_n%dd%ds%d", n, d, s));
    }
  }
}

Java

Literal[][][] shifts = new Literal[numNurses][numDays][numShifts];
for (int n : allNurses) {
  for (int d : allDays) {
    for (int s : allShifts) {
      shifts[n][d][s] = model.newBoolVar("shifts_n" + n + "d" + d + "s" + s);
    }
  }
}

C#

Dictionary<Tuple<int, int, int>, IntVar> shifts = new Dictionary<Tuple<int, int, int>, IntVar>();
foreach (int n in allNurses)
{
    foreach (int d in allDays)
    {
        foreach (int s in allShifts)
        {
            shifts.Add(Tuple.Create(n, d, s), model.NewBoolVar($"shifts_n{n}d{d}s{s}"));
        }
    }
}

Create the constraints

The following code create the constraints for the problem.

Python

for d in all_days:
    for s in all_shifts:
        model.add_exactly_one(shifts[(n, d, s)] for n in all_nurses)

C++

for (int d : all_days) {
  for (int s : all_shifts) {
    std::vector<BoolVar> nurses;
    for (int n : all_nurses) {
      auto key = std::make_tuple(n, d, s);
      nurses.push_back(shifts[key]);
    }
    cp_model.AddExactlyOne(nurses);
  }
}

Java

for (int d : allDays) {
  for (int s : allShifts) {
    List<Literal> nurses = new ArrayList<>();
    for (int n : allNurses) {
      nurses.add(shifts[n][d][s]);
    }
    model.addExactlyOne(nurses);
  }
}

C#

foreach (int d in allDays)
{
    foreach (int s in allShifts)
    {
        IntVar[] x = new IntVar[numNurses];
        foreach (int n in allNurses)
        {
            var key = Tuple.Create(n, d, s);
            x[n] = shifts[key];
        }
        model.Add(LinearExpr.Sum(x) == 1);
    }
}

Python

for n in all_nurses:
    for d in all_days:
        model.add_at_most_one(shifts[(n, d, s)] for s in all_shifts)

C++

for (int n : all_nurses) {
  for (int d : all_days) {
    std::vector<BoolVar> work;
    for (int s : all_shifts) {
      auto key = std::make_tuple(n, d, s);
      work.push_back(shifts[key]);
    }
    cp_model.AddAtMostOne(work);
  }
}

Java

for (int n : allNurses) {
  for (int d : allDays) {
    List<Literal> work = new ArrayList<>();
    for (int s : allShifts) {
      work.add(shifts[n][d][s]);
    }
    model.addAtMostOne(work);
  }
}

C#

foreach (int n in allNurses)
{
    foreach (int d in allDays)
    {
        IntVar[] x = new IntVar[numShifts];
        foreach (int s in allShifts)
        {
            var key = Tuple.Create(n, d, s);
            x[s] = shifts[key];
        }
        model.Add(LinearExpr.Sum(x) <= 1);
    }
}

Python

# Try to distribute the shifts evenly, so that each nurse works
# min_shifts_per_nurse shifts. If this is not possible, because the total
# number of shifts is not divisible by the number of nurses, some nurses will
# be assigned one more shift.
min_shifts_per_nurse = (num_shifts * num_days) // num_nurses
if num_shifts * num_days % num_nurses == 0:
    max_shifts_per_nurse = min_shifts_per_nurse
else:
    max_shifts_per_nurse = min_shifts_per_nurse + 1
for n in all_nurses:
    num_shifts_worked: Union[cp_model.LinearExpr, int] = 0
    for d in all_days:
        for s in all_shifts:
            num_shifts_worked += shifts[(n, d, s)]
    model.add(min_shifts_per_nurse <= num_shifts_worked)
    model.add(num_shifts_worked <= max_shifts_per_nurse)

C++

// Try to distribute the shifts evenly, so that each nurse works
// min_shifts_per_nurse shifts. If this is not possible, because the total
// number of shifts is not divisible by the number of nurses, some nurses will
// be assigned one more shift.
int min_shifts_per_nurse = (num_shifts * num_days) / num_nurses;
int max_shifts_per_nurse;
if ((num_shifts * num_days) % num_nurses == 0) {
  max_shifts_per_nurse = min_shifts_per_nurse;
} else {
  max_shifts_per_nurse = min_shifts_per_nurse + 1;
}
for (int n : all_nurses) {
  LinearExpr num_worked_shifts;
  for (int d : all_days) {
    for (int s : all_shifts) {
      auto key = std::make_tuple(n, d, s);
      num_worked_shifts += shifts[key];
    }
  }
  cp_model.AddLessOrEqual(min_shifts_per_nurse, num_worked_shifts);
  cp_model.AddLessOrEqual(num_worked_shifts, max_shifts_per_nurse);
}

Java

// Try to distribute the shifts evenly, so that each nurse works
// minShiftsPerNurse shifts. If this is not possible, because the total
// number of shifts is not divisible by the number of nurses, some nurses will
// be assigned one more shift.
int minShiftsPerNurse = (numShifts * numDays) / numNurses;
int maxShiftsPerNurse;
if ((numShifts * numDays) % numNurses == 0) {
  maxShiftsPerNurse = minShiftsPerNurse;
} else {
  maxShiftsPerNurse = minShiftsPerNurse + 1;
}
for (int n : allNurses) {
  LinearExprBuilder numShiftsWorked = LinearExpr.newBuilder();
  for (int d : allDays) {
    for (int s : allShifts) {
      numShiftsWorked.add(shifts[n][d][s]);
    }
  }
  model.addLinearConstraint(numShiftsWorked, minShiftsPerNurse, maxShiftsPerNurse);
}

C#

// Try to distribute the shifts evenly, so that each nurse works
// minShiftsPerNurse shifts. If this is not possible, because the total
// number of shifts is not divisible by the number of nurses, some nurses will
// be assigned one more shift.
int minShiftsPerNurse = (numShifts * numDays) / numNurses;
int maxShiftsPerNurse;
if ((numShifts * numDays) % numNurses == 0)
{
    maxShiftsPerNurse = minShiftsPerNurse;
}
else
{
    maxShiftsPerNurse = minShiftsPerNurse + 1;
}
foreach (int n in allNurses)
{
    IntVar[] numShiftsWorked = new IntVar[numDays * numShifts];
    foreach (int d in allDays)
    {
        foreach (int s in allShifts)
        {
            var key = Tuple.Create(n, d, s);
            numShiftsWorked[d * numShifts + s] = shifts[key];
        }
    }
    model.AddLinearConstraint(LinearExpr.Sum(numShiftsWorked), minShiftsPerNurse, maxShiftsPerNurse);
}

Objective for the example

We want to optimize the following objective function.

Python

model.maximize(
    sum(
        shift_requests[n][d][s] * shifts[(n, d, s)]
        for n in all_nurses
        for d in all_days
        for s in all_shifts
    )
)

C++

LinearExpr objective_expr;
for (int n : all_nurses) {
  for (int d : all_days) {
    for (int s : all_shifts) {
      if (shift_requests[n][d][s] == 1) {
        auto key = std::make_tuple(n, d, s);
        objective_expr += shifts[key] * shift_requests[n][d][s];
      }
    }
  }
}
cp_model.Maximize(objective_expr);

Java

LinearExprBuilder obj = LinearExpr.newBuilder();
for (int n : allNurses) {
  for (int d : allDays) {
    for (int s : allShifts) {
      obj.addTerm(shifts[n][d][s], shiftRequests[n][d][s]);
    }
  }
}
model.maximize(obj);

C#

IntVar[] flatShifts = new IntVar[numNurses * numDays * numShifts];
int[] flatShiftRequests = new int[numNurses * numDays * numShifts];
foreach (int n in allNurses)
{
    foreach (int d in allDays)
    {
        foreach (int s in allShifts)
        {
            var key = Tuple.Create(n, d, s);
            flatShifts[n * numDays * numShifts + d * numShifts + s] = shifts[key];
            flatShiftRequests[n * numDays * numShifts + d * numShifts + s] = shiftRequests[n, d, s];
        }
    }
}
model.Maximize(LinearExpr.WeightedSum(flatShifts, flatShiftRequests));

Since shift_requests[n][d][s] * shifts[(n, d, s) is 1 if shift s is assigned to nurse n on day d and that nurse requested that shift (and 0 otherwise), the objective is the number shift of assignments that meet a request.

Invoke the solver

The following code calls the solver.

Python

solver = cp_model.CpSolver()
status = solver.solve(model)

C++

const CpSolverResponse response = Solve(cp_model.Build());

Java

CpSolver solver = new CpSolver();
CpSolverStatus status = solver.solve(model);

C#

CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);
Console.WriteLine($"Solve status: {status}");

Display the results

The following code displays the following output, which contains an optimal schedule (although perhaps not the only one). The output shows which shift assignments were requested and the number of request that were met.

Python

if status == cp_model.OPTIMAL:
    print("Solution:")
    for d in all_days:
        print("Day", d)
        for n in all_nurses:
            for s in all_shifts:
                if solver.value(shifts[(n, d, s)]) == 1:
                    if shift_requests[n][d][s] == 1:
                        print("Nurse", n, "works shift", s, "(requested).")
                    else:
                        print("Nurse", n, "works shift", s, "(not requested).")
        print()
    print(
        f"Number of shift requests met = {solver.objective_value}",
        f"(out of {num_nurses * min_shifts_per_nurse})",
    )
else:
    print("No optimal solution found !")

C++

if (response.status() == CpSolverStatus::OPTIMAL) {
  LOG(INFO) << "Solution:";
  for (int d : all_days) {
    LOG(INFO) << "Day " << std::to_string(d);
    for (int n : all_nurses) {
      for (int s : all_shifts) {
        auto key = std::make_tuple(n, d, s);
        if (SolutionIntegerValue(response, shifts[key]) == 1) {
          if (shift_requests[n][d][s] == 1) {
            LOG(INFO) << "  Nurse " << std::to_string(n) << " works shift "
                      << std::to_string(s) << " (requested).";
          } else {
            LOG(INFO) << "  Nurse " << std::to_string(n) << " works shift "
                      << std::to_string(s) << " (not requested).";
          }
        }
      }
    }
    LOG(INFO) << "";
  }
  LOG(INFO) << "Number of shift requests met = " << response.objective_value()
            << " (out of " << num_nurses * min_shifts_per_nurse << ")";
} else {
  LOG(INFO) << "No optimal solution found !";
}

Java

if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
  System.out.printf("Solution:%n");
  for (int d : allDays) {
    System.out.printf("Day %d%n", d);
    for (int n : allNurses) {
      for (int s : allShifts) {
        if (solver.booleanValue(shifts[n][d][s])) {
          if (shiftRequests[n][d][s] == 1) {
            System.out.printf("  Nurse %d works shift %d (requested).%n", n, s);
          } else {
            System.out.printf("  Nurse %d works shift %d (not requested).%n", n, s);
          }
        }
      }
    }
  }
  System.out.printf("Number of shift requests met = %f (out of %d)%n", solver.objectiveValue(),
      numNurses * minShiftsPerNurse);
} else {
  System.out.printf("No optimal solution found !");
}

C#

if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
{
    Console.WriteLine("Solution:");
    foreach (int d in allDays)
    {
        Console.WriteLine($"Day {d}");
        foreach (int n in allNurses)
        {
            bool isWorking = false;
            foreach (int s in allShifts)
            {
                var key = Tuple.Create(n, d, s);
                if (solver.Value(shifts[key]) == 1L)
                {
                    if (shiftRequests[n, d, s] == 1)
                    {
                        Console.WriteLine($"  Nurse {n} work shift {s} (requested).");
                    }
                    else
                    {
                        Console.WriteLine($"  Nurse {n} work shift {s} (not requested).");
                    }
                }
            }
        }
    }
    Console.WriteLine(
        $"Number of shift requests met = {solver.ObjectiveValue} (out of {numNurses * minShiftsPerNurse}).");
}
else
{
    Console.WriteLine("No solution found.");
}

When you run the program, it displays the following output:

Day 0
Nurse 1 works shift 0 (not requested).
Nurse 2 works shift 1 (requested).
Nurse 3 works shift 2 (requested).

Day 1
Nurse 0 works shift 0 (not requested).
Nurse 2 works shift 1 (requested).
Nurse 4 works shift 2 (requested).

Day 2
Nurse 1 works shift 2 (not requested).
Nurse 3 works shift 0 (requested).
Nurse 4 works shift 1 (requested).

Day 3
Nurse 2 works shift 0 (requested).
Nurse 3 works shift 1 (requested).
Nurse 4 works shift 2 (not requested).

Day 4
Nurse 0 works shift 2 (requested).
Nurse 1 works shift 0 (requested).
Nurse 4 works shift 1 (not requested).

Day 5
Nurse 0 works shift 2 (not requested).
Nurse 2 works shift 1 (requested).
Nurse 3 works shift 0 (requested).

Day 6
Nurse 0 works shift 1 (not requested).
Nurse 1 works shift 2 (requested).
Nurse 4 works shift 0 (not requested).

Statistics
  - Number of shift requests met = 13 (out of 20 )
  - wall time       : 0.003571 s

Entire program

Here is the entire program for scheduling with shift requests.

Python

"""Nurse scheduling problem with shift requests."""
from typing import Union

from ortools.sat.python import cp_model


def main() -> None:
    # This program tries to find an optimal assignment of nurses to shifts
    # (3 shifts per day, for 7 days), subject to some constraints (see below).
    # Each nurse can request to be assigned to specific shifts.
    # The optimal assignment maximizes the number of fulfilled shift requests.
    num_nurses = 5
    num_shifts = 3
    num_days = 7
    all_nurses = range(num_nurses)
    all_shifts = range(num_shifts)
    all_days = range(num_days)
    shift_requests = [
        [[0, 0, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 1]],
        [[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 1, 0], [1, 0, 0], [0, 0, 0], [0, 0, 1]],
        [[0, 1, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0], [0, 1, 0], [0, 0, 0]],
        [[0, 0, 1], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0]],
        [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0]],
    ]

    # Creates the model.
    model = cp_model.CpModel()

    # Creates shift variables.
    # shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'.
    shifts = {}
    for n in all_nurses:
        for d in all_days:
            for s in all_shifts:
                shifts[(n, d, s)] = model.new_bool_var(f"shift_n{n}_d{d}_s{s}")

    # Each shift is assigned to exactly one nurse in .
    for d in all_days:
        for s in all_shifts:
            model.add_exactly_one(shifts[(n, d, s)] for n in all_nurses)

    # Each nurse works at most one shift per day.
    for n in all_nurses:
        for d in all_days:
            model.add_at_most_one(shifts[(n, d, s)] for s in all_shifts)

    # Try to distribute the shifts evenly, so that each nurse works
    # min_shifts_per_nurse shifts. If this is not possible, because the total
    # number of shifts is not divisible by the number of nurses, some nurses will
    # be assigned one more shift.
    min_shifts_per_nurse = (num_shifts * num_days) // num_nurses
    if num_shifts * num_days % num_nurses == 0:
        max_shifts_per_nurse = min_shifts_per_nurse
    else:
        max_shifts_per_nurse = min_shifts_per_nurse + 1
    for n in all_nurses:
        num_shifts_worked: Union[cp_model.LinearExpr, int] = 0
        for d in all_days:
            for s in all_shifts:
                num_shifts_worked += shifts[(n, d, s)]
        model.add(min_shifts_per_nurse <= num_shifts_worked)
        model.add(num_shifts_worked <= max_shifts_per_nurse)

    model.maximize(
        sum(
            shift_requests[n][d][s] * shifts[(n, d, s)]
            for n in all_nurses
            for d in all_days
            for s in all_shifts
        )
    )

    # Creates the solver and solve.
    solver = cp_model.CpSolver()
    status = solver.solve(model)

    if status == cp_model.OPTIMAL:
        print("Solution:")
        for d in all_days:
            print("Day", d)
            for n in all_nurses:
                for s in all_shifts:
                    if solver.value(shifts[(n, d, s)]) == 1:
                        if shift_requests[n][d][s] == 1:
                            print("Nurse", n, "works shift", s, "(requested).")
                        else:
                            print("Nurse", n, "works shift", s, "(not requested).")
            print()
        print(
            f"Number of shift requests met = {solver.objective_value}",
            f"(out of {num_nurses * min_shifts_per_nurse})",
        )
    else:
        print("No optimal solution found !")

    # Statistics.
    print("\nStatistics")
    print(f"  - conflicts: {solver.num_conflicts}")
    print(f"  - branches : {solver.num_branches}")
    print(f"  - wall time: {solver.wall_time}s")


if __name__ == "__main__":
    main()

C++

// Nurse scheduling problem with shift requests.
#include <stdlib.h>

#include <cstdint>
#include <map>
#include <numeric>
#include <string>
#include <tuple>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"

namespace operations_research {
namespace sat {

void ScheduleRequestsSat() {
  const int num_nurses = 5;
  const int num_days = 7;
  const int num_shifts = 3;

  std::vector<int> all_nurses(num_nurses);
  std::iota(all_nurses.begin(), all_nurses.end(), 0);

  std::vector<int> all_days(num_days);
  std::iota(all_days.begin(), all_days.end(), 0);

  std::vector<int> all_shifts(num_shifts);
  std::iota(all_shifts.begin(), all_shifts.end(), 0);

  std::vector<std::vector<std::vector<int64_t>>> shift_requests = {
      {
          {0, 0, 1},
          {0, 0, 0},
          {0, 0, 0},
          {0, 0, 0},
          {0, 0, 1},
          {0, 1, 0},
          {0, 0, 1},
      },
      {
          {0, 0, 0},
          {0, 0, 0},
          {0, 1, 0},
          {0, 1, 0},
          {1, 0, 0},
          {0, 0, 0},
          {0, 0, 1},
      },
      {
          {0, 1, 0},
          {0, 1, 0},
          {0, 0, 0},
          {1, 0, 0},
          {0, 0, 0},
          {0, 1, 0},
          {0, 0, 0},
      },
      {
          {0, 0, 1},
          {0, 0, 0},
          {1, 0, 0},
          {0, 1, 0},
          {0, 0, 0},
          {1, 0, 0},
          {0, 0, 0},
      },
      {
          {0, 0, 0},
          {0, 0, 1},
          {0, 1, 0},
          {0, 0, 0},
          {1, 0, 0},
          {0, 1, 0},
          {0, 0, 0},
      },
  };

  // Creates the model.
  CpModelBuilder cp_model;

  // Creates shift variables.
  // shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'.
  std::map<std::tuple<int, int, int>, BoolVar> shifts;
  for (int n : all_nurses) {
    for (int d : all_days) {
      for (int s : all_shifts) {
        auto key = std::make_tuple(n, d, s);
        shifts[key] = cp_model.NewBoolVar().WithName(
            absl::StrFormat("shift_n%dd%ds%d", n, d, s));
      }
    }
  }

  // Each shift is assigned to exactly one nurse in the schedule period.
  for (int d : all_days) {
    for (int s : all_shifts) {
      std::vector<BoolVar> nurses;
      for (int n : all_nurses) {
        auto key = std::make_tuple(n, d, s);
        nurses.push_back(shifts[key]);
      }
      cp_model.AddExactlyOne(nurses);
    }
  }

  // Each nurse works at most one shift per day.
  for (int n : all_nurses) {
    for (int d : all_days) {
      std::vector<BoolVar> work;
      for (int s : all_shifts) {
        auto key = std::make_tuple(n, d, s);
        work.push_back(shifts[key]);
      }
      cp_model.AddAtMostOne(work);
    }
  }

  // Try to distribute the shifts evenly, so that each nurse works
  // min_shifts_per_nurse shifts. If this is not possible, because the total
  // number of shifts is not divisible by the number of nurses, some nurses will
  // be assigned one more shift.
  int min_shifts_per_nurse = (num_shifts * num_days) / num_nurses;
  int max_shifts_per_nurse;
  if ((num_shifts * num_days) % num_nurses == 0) {
    max_shifts_per_nurse = min_shifts_per_nurse;
  } else {
    max_shifts_per_nurse = min_shifts_per_nurse + 1;
  }
  for (int n : all_nurses) {
    LinearExpr num_worked_shifts;
    for (int d : all_days) {
      for (int s : all_shifts) {
        auto key = std::make_tuple(n, d, s);
        num_worked_shifts += shifts[key];
      }
    }
    cp_model.AddLessOrEqual(min_shifts_per_nurse, num_worked_shifts);
    cp_model.AddLessOrEqual(num_worked_shifts, max_shifts_per_nurse);
  }

  LinearExpr objective_expr;
  for (int n : all_nurses) {
    for (int d : all_days) {
      for (int s : all_shifts) {
        if (shift_requests[n][d][s] == 1) {
          auto key = std::make_tuple(n, d, s);
          objective_expr += shifts[key] * shift_requests[n][d][s];
        }
      }
    }
  }
  cp_model.Maximize(objective_expr);

  const CpSolverResponse response = Solve(cp_model.Build());

  if (response.status() == CpSolverStatus::OPTIMAL) {
    LOG(INFO) << "Solution:";
    for (int d : all_days) {
      LOG(INFO) << "Day " << std::to_string(d);
      for (int n : all_nurses) {
        for (int s : all_shifts) {
          auto key = std::make_tuple(n, d, s);
          if (SolutionIntegerValue(response, shifts[key]) == 1) {
            if (shift_requests[n][d][s] == 1) {
              LOG(INFO) << "  Nurse " << std::to_string(n) << " works shift "
                        << std::to_string(s) << " (requested).";
            } else {
              LOG(INFO) << "  Nurse " << std::to_string(n) << " works shift "
                        << std::to_string(s) << " (not requested).";
            }
          }
        }
      }
      LOG(INFO) << "";
    }
    LOG(INFO) << "Number of shift requests met = " << response.objective_value()
              << " (out of " << num_nurses * min_shifts_per_nurse << ")";
  } else {
    LOG(INFO) << "No optimal solution found !";
  }

  // Statistics.
  LOG(INFO) << "Statistics";
  LOG(INFO) << CpSolverResponseStats(response);
}

}  // namespace sat
}  // namespace operations_research

int main() {
  operations_research::sat::ScheduleRequestsSat();
  return EXIT_SUCCESS;
}

Java

package com.google.ortools.sat.samples;
import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.LinearExpr;
import com.google.ortools.sat.LinearExprBuilder;
import com.google.ortools.sat.Literal;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

/** Nurses problem with schedule requests. */
public class ScheduleRequestsSat {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    final int numNurses = 5;
    final int numDays = 7;
    final int numShifts = 3;

    final int[] allNurses = IntStream.range(0, numNurses).toArray();
    final int[] allDays = IntStream.range(0, numDays).toArray();
    final int[] allShifts = IntStream.range(0, numShifts).toArray();

    final int[][][] shiftRequests = new int[][][] {
        {
            {0, 0, 1},
            {0, 0, 0},
            {0, 0, 0},
            {0, 0, 0},
            {0, 0, 1},
            {0, 1, 0},
            {0, 0, 1},
        },
        {
            {0, 0, 0},
            {0, 0, 0},
            {0, 1, 0},
            {0, 1, 0},
            {1, 0, 0},
            {0, 0, 0},
            {0, 0, 1},
        },
        {
            {0, 1, 0},
            {0, 1, 0},
            {0, 0, 0},
            {1, 0, 0},
            {0, 0, 0},
            {0, 1, 0},
            {0, 0, 0},
        },
        {
            {0, 0, 1},
            {0, 0, 0},
            {1, 0, 0},
            {0, 1, 0},
            {0, 0, 0},
            {1, 0, 0},
            {0, 0, 0},
        },
        {
            {0, 0, 0},
            {0, 0, 1},
            {0, 1, 0},
            {0, 0, 0},
            {1, 0, 0},
            {0, 1, 0},
            {0, 0, 0},
        },
    };

    // Creates the model.
    CpModel model = new CpModel();

    // Creates shift variables.
    // shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'.
    Literal[][][] shifts = new Literal[numNurses][numDays][numShifts];
    for (int n : allNurses) {
      for (int d : allDays) {
        for (int s : allShifts) {
          shifts[n][d][s] = model.newBoolVar("shifts_n" + n + "d" + d + "s" + s);
        }
      }
    }

    // Each shift is assigned to exactly one nurse in the schedule period.
    for (int d : allDays) {
      for (int s : allShifts) {
        List<Literal> nurses = new ArrayList<>();
        for (int n : allNurses) {
          nurses.add(shifts[n][d][s]);
        }
        model.addExactlyOne(nurses);
      }
    }

    // Each nurse works at most one shift per day.
    for (int n : allNurses) {
      for (int d : allDays) {
        List<Literal> work = new ArrayList<>();
        for (int s : allShifts) {
          work.add(shifts[n][d][s]);
        }
        model.addAtMostOne(work);
      }
    }

    // Try to distribute the shifts evenly, so that each nurse works
    // minShiftsPerNurse shifts. If this is not possible, because the total
    // number of shifts is not divisible by the number of nurses, some nurses will
    // be assigned one more shift.
    int minShiftsPerNurse = (numShifts * numDays) / numNurses;
    int maxShiftsPerNurse;
    if ((numShifts * numDays) % numNurses == 0) {
      maxShiftsPerNurse = minShiftsPerNurse;
    } else {
      maxShiftsPerNurse = minShiftsPerNurse + 1;
    }
    for (int n : allNurses) {
      LinearExprBuilder numShiftsWorked = LinearExpr.newBuilder();
      for (int d : allDays) {
        for (int s : allShifts) {
          numShiftsWorked.add(shifts[n][d][s]);
        }
      }
      model.addLinearConstraint(numShiftsWorked, minShiftsPerNurse, maxShiftsPerNurse);
    }

    LinearExprBuilder obj = LinearExpr.newBuilder();
    for (int n : allNurses) {
      for (int d : allDays) {
        for (int s : allShifts) {
          obj.addTerm(shifts[n][d][s], shiftRequests[n][d][s]);
        }
      }
    }
    model.maximize(obj);

    // Creates a solver and solves the model.
    CpSolver solver = new CpSolver();
    CpSolverStatus status = solver.solve(model);

    if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
      System.out.printf("Solution:%n");
      for (int d : allDays) {
        System.out.printf("Day %d%n", d);
        for (int n : allNurses) {
          for (int s : allShifts) {
            if (solver.booleanValue(shifts[n][d][s])) {
              if (shiftRequests[n][d][s] == 1) {
                System.out.printf("  Nurse %d works shift %d (requested).%n", n, s);
              } else {
                System.out.printf("  Nurse %d works shift %d (not requested).%n", n, s);
              }
            }
          }
        }
      }
      System.out.printf("Number of shift requests met = %f (out of %d)%n", solver.objectiveValue(),
          numNurses * minShiftsPerNurse);
    } else {
      System.out.printf("No optimal solution found !");
    }
    // Statistics.
    System.out.println("Statistics");
    System.out.printf("  conflicts: %d%n", solver.numConflicts());
    System.out.printf("  branches : %d%n", solver.numBranches());
    System.out.printf("  wall time: %f s%n", solver.wallTime());
  }

  private ScheduleRequestsSat() {}
}

C#

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Sat;

public class ScheduleRequestsSat
{
    public static void Main(String[] args)
    {
        const int numNurses = 5;
        const int numDays = 7;
        const int numShifts = 3;

        int[] allNurses = Enumerable.Range(0, numNurses).ToArray();
        int[] allDays = Enumerable.Range(0, numDays).ToArray();
        int[] allShifts = Enumerable.Range(0, numShifts).ToArray();

        int[,,] shiftRequests = new int[,,] {
            {
                { 0, 0, 1 },
                { 0, 0, 0 },
                { 0, 0, 0 },
                { 0, 0, 0 },
                { 0, 0, 1 },
                { 0, 1, 0 },
                { 0, 0, 1 },
            },
            {
                { 0, 0, 0 },
                { 0, 0, 0 },
                { 0, 1, 0 },
                { 0, 1, 0 },
                { 1, 0, 0 },
                { 0, 0, 0 },
                { 0, 0, 1 },
            },
            {
                { 0, 1, 0 },
                { 0, 1, 0 },
                { 0, 0, 0 },
                { 1, 0, 0 },
                { 0, 0, 0 },
                { 0, 1, 0 },
                { 0, 0, 0 },
            },
            {
                { 0, 0, 1 },
                { 0, 0, 0 },
                { 1, 0, 0 },
                { 0, 1, 0 },
                { 0, 0, 0 },
                { 1, 0, 0 },
                { 0, 0, 0 },
            },
            {
                { 0, 0, 0 },
                { 0, 0, 1 },
                { 0, 1, 0 },
                { 0, 0, 0 },
                { 1, 0, 0 },
                { 0, 1, 0 },
                { 0, 0, 0 },
            },
        };

        // Creates the model.
        CpModel model = new CpModel();

        // Creates shift variables.
        // shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'.
        Dictionary<Tuple<int, int, int>, IntVar> shifts = new Dictionary<Tuple<int, int, int>, IntVar>();
        foreach (int n in allNurses)
        {
            foreach (int d in allDays)
            {
                foreach (int s in allShifts)
                {
                    shifts.Add(Tuple.Create(n, d, s), model.NewBoolVar($"shifts_n{n}d{d}s{s}"));
                }
            }
        }

        // Each shift is assigned to exactly one nurse in the schedule period.
        foreach (int d in allDays)
        {
            foreach (int s in allShifts)
            {
                IntVar[] x = new IntVar[numNurses];
                foreach (int n in allNurses)
                {
                    var key = Tuple.Create(n, d, s);
                    x[n] = shifts[key];
                }
                model.Add(LinearExpr.Sum(x) == 1);
            }
        }

        // Each nurse works at most one shift per day.
        foreach (int n in allNurses)
        {
            foreach (int d in allDays)
            {
                IntVar[] x = new IntVar[numShifts];
                foreach (int s in allShifts)
                {
                    var key = Tuple.Create(n, d, s);
                    x[s] = shifts[key];
                }
                model.Add(LinearExpr.Sum(x) <= 1);
            }
        }

        // Try to distribute the shifts evenly, so that each nurse works
        // minShiftsPerNurse shifts. If this is not possible, because the total
        // number of shifts is not divisible by the number of nurses, some nurses will
        // be assigned one more shift.
        int minShiftsPerNurse = (numShifts * numDays) / numNurses;
        int maxShiftsPerNurse;
        if ((numShifts * numDays) % numNurses == 0)
        {
            maxShiftsPerNurse = minShiftsPerNurse;
        }
        else
        {
            maxShiftsPerNurse = minShiftsPerNurse + 1;
        }
        foreach (int n in allNurses)
        {
            IntVar[] numShiftsWorked = new IntVar[numDays * numShifts];
            foreach (int d in allDays)
            {
                foreach (int s in allShifts)
                {
                    var key = Tuple.Create(n, d, s);
                    numShiftsWorked[d * numShifts + s] = shifts[key];
                }
            }
            model.AddLinearConstraint(LinearExpr.Sum(numShiftsWorked), minShiftsPerNurse, maxShiftsPerNurse);
        }

        IntVar[] flatShifts = new IntVar[numNurses * numDays * numShifts];
        int[] flatShiftRequests = new int[numNurses * numDays * numShifts];
        foreach (int n in allNurses)
        {
            foreach (int d in allDays)
            {
                foreach (int s in allShifts)
                {
                    var key = Tuple.Create(n, d, s);
                    flatShifts[n * numDays * numShifts + d * numShifts + s] = shifts[key];
                    flatShiftRequests[n * numDays * numShifts + d * numShifts + s] = shiftRequests[n, d, s];
                }
            }
        }
        model.Maximize(LinearExpr.WeightedSum(flatShifts, flatShiftRequests));

        // Solve
        CpSolver solver = new CpSolver();
        CpSolverStatus status = solver.Solve(model);
        Console.WriteLine($"Solve status: {status}");

        if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
        {
            Console.WriteLine("Solution:");
            foreach (int d in allDays)
            {
                Console.WriteLine($"Day {d}");
                foreach (int n in allNurses)
                {
                    bool isWorking = false;
                    foreach (int s in allShifts)
                    {
                        var key = Tuple.Create(n, d, s);
                        if (solver.Value(shifts[key]) == 1L)
                        {
                            if (shiftRequests[n, d, s] == 1)
                            {
                                Console.WriteLine($"  Nurse {n} work shift {s} (requested).");
                            }
                            else
                            {
                                Console.WriteLine($"  Nurse {n} work shift {s} (not requested).");
                            }
                        }
                    }
                }
            }
            Console.WriteLine(
                $"Number of shift requests met = {solver.ObjectiveValue} (out of {numNurses * minShiftsPerNurse}).");
        }
        else
        {
            Console.WriteLine("No solution found.");
        }

        Console.WriteLine("Statistics");
        Console.WriteLine($"  conflicts: {solver.NumConflicts()}");
        Console.WriteLine($"  branches : {solver.NumBranches()}");
        Console.WriteLine($"  wall time: {solver.WallTime()}s");
    }
}