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.
Release year | Version |
---|---|
2022 | 9.5 |
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.
- Create an account (here)
- Retrieve your authentication token (here)
- 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 exampleinput_LP/
: data and script to run the linear programming exampleinput_MILP/
: data and script to run the mixed-integer linear programming exampleinput_TSP/
: data and script to run the traveling salesperson problem exampleinput_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.