Google OR Tools — A Guide

Published in

Google OR Tools

10 min readFeb 23, 2019

Google OR tools are essentially one of the most powerful tools introduced in the world of problem-solving. Google OR Tools is an open source software suite for tracking the toughest problems. The suite contains:

A constraint programming solver;
A linear programming solver;
Wrappers around commercial and other open source solvers, including mixed integer solvers;
Bin packing and knapsack algorithms;
Algorithms for the Traveling Salesman Problem and Vehicle Routing Problem;
Graph algorithms (shortest paths, min cost flow, max flow, linear sum assignment).

OR Tools provide us with solvers we can use in our programming. For instance, SCIP is used for solving constraint integer programs, GLPK is used for GNU linear programming. CP-SAT and GLOP are a few more.

First things first. To get our hands dirty in solving optimization problems, we first need to create a sandbox environment. To install OR-Tools for Python using pip, see Installing OR-Tools. This is the recommended method. However, if you wish, you can install OR-Tools from one of the Python Wheel files.

C++, Java or C#

Linux

Mac

Mac OS X

Windows

FlatZinc

Linux

Mac

FlatZinc — Mac OS X

Windows

Source file downloads

You have a couple of options for the source code to install:

The latest release — tar.gz or zip
The release is a stable version of OR-Tools that has been has been fully tested on all the supported platforms. This is the best option unless you want to try out features that have been added since the most recent release date.
The source code in the or-tools repository on GitHub
These are the latest versions of the files under development. Note that this code may not be fully tested on all the supported platforms.

After downloading, follow the source installation instructions.

Now, let's get started.

Optimization, essentially, means finding the best solution to a problem out of a large set of possible solutions. We all have finite resources and time & we want to make most of them. Either it is the task of scheduling the order at which you will answer the emails or switching to a new route back home to minimize traffic woes, we surely know how important optimization is to data science. One of the main concerns of a data scientist is creating a model that fits the problem like finding optimal heuristics, minimum function losses, etc. Therefore it is crucial to understand optimization frameworks. The first problem we will address will be that of linear optimization.

Linear optimization is a method of computing the best solution to a problem modeled as a set of linear relationships. Google provides us with three ways to solve the linear optimization problem.

Glop - an open source in house solver. It can be used with the linear solver wrapper.
Add-on for Google sheets - lets you solve linear optimization problems by entering variables and constraints in a spreadsheet.
Apps Script - It relies on Glop for pure linear Optimization.

A real-world example can be the problem faced with FedEx delivery. The delivery person will calculate different routes for going to all the 6 destinations and then come up with the shortest route.

Route Optimization based on Minimum Cost

The Glop Linear Solver

Overview

The primary OR-Tools linear optimization solver is Glop, Google’s linear programming system. It’s fast, memory efficient, and numerically stable. To learn how to use Glop to solve a simple linear problem in all of the supported languages, see Getting Started with OR-Tools.

Once you’ve taken a look at that section, you can move on to a more complicated linear optimization problem, the Stigler diet.

Using Glop with the OR-Tools linear solver wrapper

To use the Glop solver, you first declare it with the OR-Tools linear solver wrapper — a wrapper for several linear optimization libraries. The following sections show how to use a MIP solver in C++ and Python. (Doing so in Java or C# is similar to the C++ example.)

Using Glop in C++

To use Glop in C++:

Declare the linear solver wrapper

void RunLinearExample(
  MPSolver::OptimizationProblemType optimization_problem_type) {
  MPSolver solver("LinearExample", optimization_problem_type);

Call the solver wrapper with the argument GLOP_LINEAR_PROGRAMMING, which tells it to use Glop.

RunLinearExample(MPSolver::GLOP_LINEAR_PROGRAMMING);

The input is passed to the solver wrapper through the OptimizationProblemType method.

Using Glop in Python

To use Glop in Python:

Declare the solver using the Python wrapper pywraplp.

from ortools.linear_solver import pywraplp

def main():
  # Instantiate a Glop solver, naming it LinearExample.
  solver = pywraplp.Solver('LinearExample',
                           pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

Call the solver

solver.Solve()

Add-on for Google sheets

Every linear optimization problem can be expressed as a set of linear inequalities and an objective function to be maximized or minimized. The inequalities are called constraints, and like all inequalities, they contain variables
Before you can solve linear optimization problems from a spreadsheet, you need to install the add-on that makes it possible. On that page, just click FREE to install the add-on

Constraint Optimization, or Constraint Programming (CP) is based on feasibility rather than optimization. It focuses on constraints and variables rather than the objective function.

Feasible Solution: A set of values for the decision variables that satisfies all of the constraints in an optimization problem

Let’s take a simple example of scheduling 4 employees into 3 shifts with an aim to assign 3 of its employees to 8 hours each while giving the fourth one a day off.

How many possible ways are there for a manager to assign employees per day?
How many possible ways are there for a manager to assign employees per week?

Here, our goal is to narrow down a very large set of possible solutions to a more manageable subset by adding the following constraints to the problem:

Each employee should work some minimum hours per week.
No employee should work two shifts in a row.

OR tools provide two solvers for constraint programming:

CP-SAT solver
Original CP solver

Note: CP-SAT solver is technologically superior to the original CP solver and should be preferred in almost all situations

Some of the interesting examples of constraint programming are the cryptarithmetic problem and N Queens problem

Cryptarithmetic Problem

A cryptarithmetic puzzle is a mathematical exercise where the digits of some numbers are represented by letters (or symbols)

The goal is to find the digits such that a given mathematical equation is verified

Variables: Letters that can take any single digit value

Constraints:

CP + IS + FUN = TRUE
Each of the ten letters must be a different digit
C, I, F, and T can’t be zero (since we don’t write leading zeros in numbers)

N Queens Problem

How can N queens be placed on an N x N chessboard so that no two of them attack each other?

Constraint: No two queens are on the same row, column, or diagonal

Integer Optimization problems require some or all variables to be Integers.

For example, The number of consumer items to manufacture per month. A manufacturing company is considering expansion in Boston, New York or in both the cities with one new warehouse in any one of the cities. This problem involves “yes-or-no” decisions for building the warehouse.

Google’s OR tools provides two types of solvers for such problems:

Mixed Integer Programming (MIP) solver

Mixed Integer Programming Solver can be used when the variables are a pure integer or a combination of integer and continuous. Let’s take an example of a table and chair manufacturing company, XYZ:

Background: Suppose XYZ considers producing chairs and tables using only 21 Sq m of wood. Each chair requires 6 Sq m and table requires 7 Sq m of wood. Each chair is sold at $12 and each table is sold at $13.
Problem: Let c denote chairs and t denote table, find out how many table and chairs could be manufactured out of 21 Sq m wood with maximum revenue.

CP Approach to Integer Optimization solver

The CP Approach to Integer Optimization Solver is based on feasibility (i.e. finding a feasible solution) rather than optimization (i.e. finding an optimal solution) and focuses on the constraints and variables’ domain rather than the objective function. Constraint programming looks first to reduce the set of possible values of the decision variables. The usage of both Integer Programming and Constraint Programming depends on the problem.

Integer Programming: For standard integer programming problems, in which an optimal solution must satisfy all constraints.
Constraint Programming: For problems when the optimal solution satisfies one of the constraints.

Routing

Routing means to find efficient paths for transporting items through a complex network. Routing problems can be divided into two main types:

node-routing problems
arc-routing problems

OR-Tools includes a specialized routing library to solve many types of node-routing problems:

Traveling Salesman Problems (TSP)
Vehicle Routing Problems (VRP)
Capacitated Vehicle Routing Problems (CVRP)
Vehicle Routing Problems with Time Windows (VRPTW)
Vehicle Routing Problems with Resource Constraints
Vehicle Routing Problems with Pickup and Delivery (VRPPD)

Traveling Salesman Problem

Traveling Salesman Problem is a famous problem in the field of operations research. Suppose you decide to drive a car around northeast of the US, you will start in Boston. The goal is to visit New York City, Pittsburg, Baltimore, and Syracuse before returning to Boston. What is the best itinerary? How can you minimize the number of kilometers yet make sure you visit all the cities?

If there are only 5 cities it’s not too hard to figure out the optimal tour. As we add cities to our tour, however, it is much harder to figure out the optimal tour. The following is achieved using Google OR tools:

Vehicle Routing Problem

The goal is to find the optimal set of routes for a fleet of vehicles delivering goods or services to various locations.

Vehicle Routing Constraints

Capacity Constraint: the total demand of the locations on a vehicle’s route cannot exceed its capacity
Time Window: each location must be serviced within a time window [ai, bi] and waiting times are allowed
Consider where we have a depot surrounded by a number of customers who are to be supplied from the depot

Vehicle Routing Problem with Time Window Constraints, is the m-TSP where a demand is associated with each city, and vehicle has a certain capacity.

If we add a time window to each customer we get the vehicle routing problem with time windows. In addition to the capacity constraint, a vehicle now has to visit a customer within a certain time frame.
The vehicle may arrive before the time window opens but the customer cannot be serviced until the time windows open. It is not allowed to arrive after the time window has closed.

Vehicle Routing Problem With Time Constraints

Capacitated Vehicle Routing Problem is a vehicle routing problem with additional constraints on the capacities of vehicles. It is a physical quantity, such as weight or volume, corresponding to an item.

For example, at each location, there is a demand corresponding to an item to be picked up. Also, each vehicle has a maximum capacity of 15. And we do the same with our demand callback, so the solver can compute the demand of each node.

Dropping Visits in Infeasible Problems — Penalties

If you are given a capacitated vehicle routing problem (CVRP) in which the total demands at all locations exceed the total capacity of the vehicles, no solution is possible. In such cases, the vehicles must drop visits to some locations. The question is how to decide which visits to drop. To make the problem meaningful, we introduce new costs — called penalties — at all locations. Whenever a visit to a location is dropped, the penalty is added to the total distance traveled. The solver then finds a route that minimizes the total distance plus the sum of the penalties for all dropped locations.

Depot -> A -> C -> Depot . This is the shortest route that visits two of the three locations (the distance is 55).

Google Directions API

Google also provides a way to solve simple TSPs of real-world locations without downloading OR-Tools. If you have a Google Directions API key, you can solve TSPs of real-world locations with the Directions API, providing the locations in a URL and getting the response back as JSON. You’ll need your own free Directions API key for development, or an enterprise key for commercial use. As an example, here’s a URL that can be used to find a short tour of Boston to New York. If you want to try this from your browser, replace API_KEY at the end of the URL with your key.

This is our link for the TSP by Google maps from Boston to New York. Even you can do it!!

References: https://developers.google.com/optimization/introduction/get_started

For more references and insights, you might want to refer to our resources and code on our GitHub and YouTube.