Supported Solvers

Supported solvers in shift scheduling problems

A how-to guide for working with different solvers.

These are the supported solvers for shift scheduling problems:

ProviderDescriptionUse with
NextmvOur shift-scheduling marketplace app. Get started here.Nextmv marketplace app
OR-ToolsOpen-source solver.Nextmv platofrm & Python

When working locally with the Nextmv Platform make sure all necessary assets are up to date by running the following command:

nextmv sdk install
Copy

OR-Tools

OR-Tools

OR-Tools is an open-source solver. It is a software suite for optimization, tuned for tackling the world's toughest problems in vehicle routing, flows, integer and linear programming, and constraint programming.

  • This solver is supported using Python.
  • When running locally, this solver is not supported natively using Nextmv's SDK and you need to run with the Python command directly.
  • Does not require additional licensing or setup, for running locally or in the cloud.

Get started by initializing the ortools template. The template contains an example of getting started with Mixed Integer Programming (MIP).

nextmv sdk init -t ortools
Copy

Change directories into the ortools folder.

We are going to modify the template to solve a sample nurse scheduling problem with shift requests. This is an adapted example taken from the OR-Tools Scheduling guides.

Replace the input.json contained in the template with sample data for the scheduling problem.

{
  "num_nurses": 5,
  "num_shifts": 3,
  "num_days": 7,
  "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]
    ]
  ]
}
Copy

Similarly, replace the main.py included in the template with the code to solve the problem.

"""
Adapted example of the nurse scheduling problem with Google OR-Tools.
"""

import argparse
import json
import sys
from typing import Any, Dict

from ortools.sat.python import cp_model


def main():
    """Entry point for the template."""
    parser = argparse.ArgumentParser(description="Solve problems with OR-Tools.")
    parser.add_argument(
        "-input",
        default="",
        help="Path to input file. Default is stdin.",
    )
    parser.add_argument(
        "-output",
        default="",
        help="Path to output file. Default is stdout.",
    )
    parser.add_argument(
        "-duration",
        default=30,
        help="Max runtime duration (in seconds). Default is 30.",
        type=int,
    )
    args = parser.parse_args()

    # Read input data, solve the problem and write the solution.
    input_data = read_input(args.input)
    solution = solve(input_data, args.duration)
    write_output(args.output, solution)


def solve(input_data: Dict[str, Any], duration: int) -> Dict[str, Any]:
    """Solves the given problem and returns the solution."""

    all_nurses = range(input_data["num_nurses"])
    all_shifts = range(input_data["num_shifts"])
    all_days = range(input_data["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 nurse in all_nurses:
        for day in all_days:
            for shift in all_shifts:
                shifts[(nurse, day, shift)] = model.NewBoolVar(f"shift_n{nurse}_d{day}_s{shift}")

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

    # Each nurse works at most one shift per day.
    for nurse in all_nurses:
        for day in all_days:
            model.AddAtMostOne(shifts[(nurse, day, 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.
    total_shifts = input_data["num_shifts"] * input_data["num_days"]
    min_shifts_per_nurse = total_shifts // input_data["num_nurses"]
    if input_data["num_shifts"] * input_data["num_days"] % input_data["num_nurses"] == 0:
        max_shifts_per_nurse = min_shifts_per_nurse
    else:
        max_shifts_per_nurse = min_shifts_per_nurse + 1
    for nurse in all_nurses:
        num_shifts_worked = 0
        for day in all_days:
            for shift in all_shifts:
                num_shifts_worked += shifts[(nurse, day, shift)]
        model.Add(min_shifts_per_nurse <= num_shifts_worked)
        model.Add(num_shifts_worked <= max_shifts_per_nurse)

    model.Maximize(
        sum(
            input_data["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()
    solver.parameters.max_time_in_seconds = duration
    status = solver.Solve(model)

    # Determines the shifts.
    final_shifts = []
    for day in all_days:
        day_shifts = []
        for nurse in all_nurses:
            for shift in all_shifts:
                if solver.Value(shifts[(nurse, day, shift)]) >= 0.99:
                    day_shift = {
                        "nurse": nurse,
                        "shift": shift,
                        "requested": False,
                    }
                    if input_data["shift_requests"][nurse][day][shift] == 1:
                        day_shift["requested"] = True

                    day_shifts.append(day_shift)

        final_shift = {
            "day": day,
            "shifts": day_shifts,
        }
        final_shifts.append(final_shift)

    # Creates the statistics.
    min_shifts = input_data["num_nurses"] * min_shifts_per_nurse
    statistics = {
        "result": {
            "custom": {
                "branches": solver.NumBranches(),
                "conflicts": solver.NumConflicts(),
                "status": status,
                "shift_preference_fulfillment": solver.ObjectiveValue() / min_shifts,
            },
            "duration": solver.WallTime(),
            "value": solver.ObjectiveValue(),
        },
        "run": {
            "duration": solver.WallTime(),
        },
        "schema": "v1",
    }

    return {
        "solutions": [{"shifts": final_shifts}],
        "statistics": statistics,
    }


def read_input(input_path) -> Dict[str, Any]:
    """Reads the input from stdin or a given input file."""
    input_file = {}
    if input_path:
        with open(input_path) as file:
            input_file = json.load(file)
    else:
        input_file = json.load(sys.stdin)

    return input_file


def write_output(output_path, output) -> None:
    """Writes the output to stdout or a given output file."""
    content = json.dumps(output, indent=2)
    if output_path:
        with open(output_path, "w") as file:
            file.write(content + "\n")
    else:
        print(content)


if __name__ == "__main__":
    main()
Copy

Because this is a Python template, make sure that the requirements described in the requirements.txt file are installed.

pip3 install -r requirements.txt
Copy

Run the code, specifying the file to be used as input.

python3 main.py -input input.json -duration 10
Copy

After running, the output should have been printed to stdout, similar to this one:

{
  "solutions": [
    {
      "shifts": [
        {
          "day": 0,
          "shifts": [
            {
              "nurse": 2,
              "shift": 1,
              "requested": true
            },
            {
              "nurse": 3,
              "shift": 2,
              "requested": true
            },
            {
              "nurse": 4,
              "shift": 0,
              "requested": false
            }
          ]
        },
        {
          "day": 1,
          "shifts": [
            {
              "nurse": 0,
              "shift": 0,
              "requested": false
            },
            {
              "nurse": 2,
              "shift": 1,
              "requested": true
            },
            {
              "nurse": 4,
              "shift": 2,
              "requested": true
            }
          ]
        },
        {
          "day": 2,
          "shifts": [
            {
              "nurse": 1,
              "shift": 1,
              "requested": true
            },
            {
              "nurse": 3,
              "shift": 0,
              "requested": true
            },
            {
              "nurse": 4,
              "shift": 2,
              "requested": false
            }
          ]
        },
        {
          "day": 3,
          "shifts": [
            {
              "nurse": 0,
              "shift": 2,
              "requested": false
            },
            {
              "nurse": 1,
              "shift": 1,
              "requested": true
            },
            {
              "nurse": 2,
              "shift": 0,
              "requested": true
            }
          ]
        },
        {
          "day": 4,
          "shifts": [
            {
              "nurse": 0,
              "shift": 2,
              "requested": true
            },
            {
              "nurse": 1,
              "shift": 0,
              "requested": true
            },
            {
              "nurse": 2,
              "shift": 1,
              "requested": false
            }
          ]
        },
        {
          "day": 5,
          "shifts": [
            {
              "nurse": 0,
              "shift": 1,
              "requested": true
            },
            {
              "nurse": 1,
              "shift": 2,
              "requested": false
            },
            {
              "nurse": 3,
              "shift": 0,
              "requested": true
            }
          ]
        },
        {
          "day": 6,
          "shifts": [
            {
              "nurse": 0,
              "shift": 2,
              "requested": true
            },
            {
              "nurse": 3,
              "shift": 0,
              "requested": false
            },
            {
              "nurse": 4,
              "shift": 1,
              "requested": false
            }
          ]
        }
      ]
    }
  ],
  "statistics": {
    "result": {
      "custom": {
        "branches": 208,
        "conflicts": 0,
        "status": 4,
        "shift_preference_fulfillment": 0.65
      },
      "duration": 0.12345,
      "value": 13.0
    },
    "run": {
      "duration": 0.12345
    },
    "schema": "v1"
  }
}
Copy

The template contains an app.yaml manifest that specifies how to execute the app in the cloud.

# This manifest holds the information the app needs to run on the Nextmv Cloud.
type: python
runtime: ghcr.io/nextmv-io/runtime/ortools:latest
# List all files/directories that should be included in the app. Globbing
# (e.g.: configs/*.json) is supported.
files:
  - main.py
Copy
  • type (do not modify this value): specifies that the app uses Python instead of the Nextmv SDK.
  • runtime (do not modify this value): specifies the docker runtime where the app is run. This value must not be modified because the runtime is specific for OR-Tools.
  • files: a list of all the files that should be included in the app. Globbing is supported, so you may specify individual files or whole directories. In the simple template, just the main.py needs to be included.

The OR-Tools runtime has no access to network calls. This means that importing other packages or performing HTTP requests is not yet available. If you would like more Python packages to be supported in the runtime, please contact support.

After running locally, and making sure your app manifest is correctly set up, you may follow the steps for deploying a custom app.

Page last updated

Contents

Go to on-page nav menu