OR-Tools on Qarnot Cloud - 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 cloud platform.

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.

• Create a Tasq account
• Retrieve your authentication token
• Install one of Qarnot’s SDK (Python) (Node.js) (C#) (Commande Line)

Test cases

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

• A nurse scheduling problem : a constraint programming (CP) example
• The Stigler diet problem : a linear programming (LP) example
• A MIP problem : a mixed-integer programming (MIP) example
• A drilling a circuit board example : a traveling salesperson problem (TSP) example
• An example of a company that needs to visit its customers : a vehicle routing problem (VRP) example

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 Cloud. 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 Cloud 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 Tasq. You should now have an output folder in your working directory on your computer and a ortools-out bucket on Tasq 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! You can visit Qarnot Blog to read more articles on other computational use-cases.