OR-Tools is 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 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.

OR-Tools includes solvers for:

Constraint Programming

A set of techniques for finding feasible solutions to a problem expressed as constraints (e.g., a room can’t be used for two events simultaneously, or the distance to the crops must be less than the length of the hose, or no more than five TV shows can be recorded at once).

Linear and Mixed-Integer Programming

The Glop linear optimizer finds the optimal value of a linear objective function, given a set of linear inequalities as constraints (e.g., assigning people to jobs, or finding the best allocation of a set of resources while minimizing cost). Glop and the mixed-integer programming software SCIP are also available via the Google Apps Script Optimization Service.

Vehicle Routing

A specialized library for identifying best vehicle routes given constraints.

Graph Algorithms

Code for finding shortest paths in graphs, min-cost flows, max flows, and linear sum assignments.

Solving an optimization problem in Python

Next, we give an example of an optimization problem, and show how to set up and solve it in Python.

A linear optimization example

One of the oldest and most widely-used areas of optimization is linear optimization (or linear programming), in which the objective function and the constraints can be written as linear expressions. Here’s a simple example of this type of problem.

Maximize 3x + y subject to the following constraints:

0	≤	x	≤	1
0	≤	y	≤	2
		x + y	≤	2

The objective function in this example is 3x + y. Both the objective function and the constraints are given by linear expressions, which makes this a linear problem.

Main steps in solving the problem

For each language, the basic steps for setting up and solving a problem are the same:

• Import the linear solver.
• Create the variables.
• Define the constraints.
• Define the objective function.
• Declare the linear solver.
• Invoke the solver and display the results.

Python program

This section walks through a Python program that sets up and solves the problem.

Here are the steps:

• • Import the linear solver.

from __future__ import print_function
from ortools.linear_solver import pywraplp

• Create the variables.

  # Create the variables x and y.
  x = solver.NumVar(0, 1, 'x')
  y = solver.NumVar(0, 2, 'y')
  
  print('Number of variables =', solver.NumVariables())
• Define the constraints.

  The first two constraints, 0 ≤ x ≤ 1 and 0 ≤ y ≤ 2, are already set by the definitions of the variables. The following code defines the constraint x + y ≤ 2:

  # Create a linear constraint, 0 <= x + y <= 2.
  ct = solver.Constraint(0, 2, 'ct')
  ct.SetCoefficient(x, 1)
  ct.SetCoefficient(y, 1)
  
  print('Number of constraints =', solver.NumConstraints())

  The method SetCoefficient sets the coefficients of x and y in the expression for the constraint.

• Define the objective function.

  # Create the objective function, 3 * x + y.
  objective = solver.Objective()
  objective.SetCoefficient(x, 3)
  objective.SetCoefficient(y, 1)
  objective.SetMaximization()

  The method SetMaximization declares this to be a maximization problem.

• Declare the solver.

  # Create the linear solver with the GLOP backend.
  solver = pywraplp.Solver('simple_lp_program',
                           pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

  pywraplp is a Python wrapper for the underlying C++ solver. The argument GLOP_LINEAR_PROGRAMMING specifies GLOP, the OR-Tools linear solver.

• Invoke the solver and display the results.

  solver.Solve()
  print('Solution:')
  print('Objective value =', objective.Value())
  print('x =', x.solution_value())
  print('y =', y.solution_value())

Complete program

The complete program is shown below.

from __future__ import print_function
from ortools.linear_solver import pywraplp


def main():
# Create the linear solver with the GLOP backend.
    solver = pywraplp.Solver('simple_lp_program',
                             pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

# Create the variables x and y.
    x = solver.NumVar(0, 1, 'x')
    y = solver.NumVar(0, 2, 'y')

print('Number of variables =', solver.NumVariables())

# Create a linear constraint, 0 <= x + y <= 2.
    ct = solver.Constraint(0, 2, 'ct')
    ct.SetCoefficient(x, 1)
    ct.SetCoefficient(y, 1)

print('Number of constraints =', solver.NumConstraints())

# Create the objective function, 3 * x + y.
    objective = solver.Objective()
    objective.SetCoefficient(x, 3)
    objective.SetCoefficient(y, 1)
    objective.SetMaximization()

    solver.Solve()

print('Solution:')
print('Objective value =', objective.Value())
print('x =', x.solution_value())
print('y =', y.solution_value())


if __name__ == '__main__':
    main()

Running the program

You can run the program above as follows:

1. Copy and paste the code above into new file and save it as program.py.
2. Open a command window and change to the directory where you saved program.py.
3. At the command prompt, enter

   python relative/path/to/program.py

   where relative/path/to/ is the path to the directory where you saved the program.

The program returns the values of x and y that maximize the objective function:

Solution:
x =  1.0
y =  1.0