Computing Power to the People

The Official Qarnot Blog

< Back

OR-Tools on Qarnot- documentation


by Tiphaine Bonniot - October 20, 2021 - Documentation

Introduction

OR-Tools is an open source software for combinatorial optimization, which seeks to find the best solution to a problem out of a very large set of possible solutions. Here are some examples of problems that OR-Tools solves:

  • Vehicle routing: Find optimal routes for vehicle fleets that pick up and deliver packages with given constraints (e.g., “this truck can’t hold more than 20,000 pounds” or “all deliveries must be made within a two-hour window”).
  • Scheduling: Find the optimal schedule for a complex set of tasks, some of which need to be performed before others on a fixed set of machines or other resources.
  • Bin packing: Pack as many objects of various sizes as possible into a fixed number of bins with maximum capacities.

In most cases, problems like these have a vast number of possible solutions—too many for a computer to search them all. To overcome this, OR-Tools uses state-of-the-art algorithms to narrow down the search set in order to find an optimal (or close to optimal) solution.

Versions

Versions available on Qarnot’s plateform.

Release year Version
2021 9.0

If you are interested in another version, please send us an email at qlab@qarnot.com.

Prerequisites

Before launching the case, please ensure that the following prerequisites have been met.

Test cases

We use Python examples provided by the OR-Tools guide :

You can download scripts and data to run these examples here. You need to unzip this folder to be able to use it on Qarnot.

This article focuses on the nurse scheduling problem but other examples run similarly.

Nurse scheduling problem

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.

In this test case, a hospital supervisor needs to create a schedule for five nurses over a seven-day period subject to the following conditions :

  • Each day is divided into three 8-hour shifts (3 shifts per day).
  • Every day, each shift is assigned to a single nurse, and no nurse works more than one shift.
  • Each nurse can request shifts.

The following code creates the data for the example :

data.py

Launching a case

Copy the following code in a Python script and save it next to the or-tools-examples folder you unzipped before. Be sure you have copied your authentication token in the script (instead of <<<MY_SECRET_TOKEN>>>) to be able to launch the task on Qarnot.

ortools.py

By default, the script ortools.py launches the nurse scheduling problem. To launch another example, change the source of the input bucket in line 14 :

input_bucket.sync_directory('or-tools-examples/input_CP/')

Replace input_CP by one of input_LP, input_MILP, input_TSP or input_VRP.

Make sure that all input files are in the same folder named or-tools-examples. Your working directory should look like this :

  • or-tools-examples/ :
    • input_CP/ : data and script to run the constraint programming example
    • input_LP/ : data and script to run the linear programming example
    • input_MILP/ : data and script to run the mixed-integer linear programming example
    • input_TSP/ : data and script to run the traveling salesperson problem example
    • input_VRP/ : data and script to run the vehicle routing problem example
  • ortools.py : python script to run the computations on Qarnot using OR-Tools

To launch this script, open a terminal in your working directory and execute python3 ortools.py &. It will launch the execution of run_md.sh on Qarnot and wait in the background until the execution is over to download the results.

Results

At any given time, you can monitor the status of your task on Console. You should now have an output folder in your working directory on your computer and a ortools-out bucket on Qarnot’s Console containing all output files. For example, two solutions were found for the nurse scheduling problem. The output displays the shifts satisfying the constraints for these two solutions:

 

Solution 0
Day 0
Nurse 0 works shift 2 (requested).
Nurse 2 works shift 1 (requested).
Nurse 4 works shift 0 (not requested).
Day 1
Nurse 2 works shift 1 (requested).
Nurse 3 works shift 0 (not requested).
Nurse 4 works shift 2 (requested).
Day 2
Nurse 1 works shift 1 (requested).
Nurse 2 works shift 2 (not requested).
Nurse 3 works shift 0 (requested).
Day 3
Nurse 1 works shift 1 (requested).
Nurse 2 works shift 0 (requested).
Nurse 4 works shift 2 (not requested).
Day 4
Nurse 0 works shift 2 (requested).
Nurse 3 works shift 1 (not requested).
Nurse 4 works shift 0 (requested).
Day 5
Nurse 0 works shift 1 (requested).
Nurse 1 works shift 0 (not requested).
Nurse 3 works shift 2 (not requested).
Day 6
Nurse 0 works shift 2 (requested).
Nurse 1 works shift 1 (not requested).
Nurse 2 works shift 0 (not requested).
Solution 1
Day 0
Nurse 0 works shift 2 (requested).
Nurse 2 works shift 1 (requested).
Nurse 4 works shift 0 (not requested).
Day 1
Nurse 2 works shift 1 (requested).
Nurse 3 works shift 0 (not 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 1 works shift 1 (requested).
Nurse 2 works shift 0 (requested).
Nurse 3 works shift 2 (not requested).
Day 4
Nurse 0 works shift 2 (requested).
Nurse 2 works shift 1 (not requested).
Nurse 4 works shift 0 (requested).
Day 5
Nurse 0 works shift 1 (requested).
Nurse 1 works shift 2 (not requested).
Nurse 3 works shift 0 (requested).
Day 6
Nurse 0 works shift 1 (not requested).
Nurse 1 works shift 2 (requested).
Nurse 2 works shift 0 (not requested).
Statistics
- Number of shift requests met = 13(out of 20)
- conflicts       : 2
- branches        : 276
- wall time       : 0.069783 s
- solutions found : 2

Wrapping up

That’s it! If you have any questions, please contact qlab@qarnot.com and we will help you with pleasure!

comments

Leave a Reply

Your email address will not be published. Required fields are marked *