Using OR-Tools

The following sections introduce you to solving optimization problems using OR-Tools:

What is an optimization problem?

The goal of optimization is to find the best solution to a problem out of a large set of possible solutions. Here's an example. Suppose that a shipping company delivers packages to its customers using a fleet of trucks. Every day, the company must assign packages to trucks, and then a choose a route for each truck to deliver its packages. Each possible assignment of packages and routes has a cost, based on the total travel distance for the trucks, and possibly other factors as well. The problem is to choose the assignments of packages and routes that has the least cost.

Like all optimization problems, this problem has the following elements:

  • The objective — the quantity you want to optimize. In the example above, the objective is to minimize cost. To set up an optimization problem, you need to define a function that calculates the value of the objective for any possible solution. This is called the objective function. In the preceding example, the objective function would calculate the total cost of any assignment of packages and routes.

    An optimal solution is one for which the value of the objective function is the best. ("Best" will be either a maximum or a minimum, depending on the problem statement.)
  • The constraints — restrictions on the set of possible solutions, based on the specific requirements of the problem. For example, if the shipping company can't assign packages above a given size to certain trucks, due to space limitations, this would impose a constraint on the solutions. A feasible solution is one that satisfies all the given constraints for the problem.
The first step in solving an optimization problem is identifying the objective and constraints.

Setting up and solving an optimization problem

Next, we give an example of an optimization problem, and show how to set up and solve it in each of the supported languages.

A simple 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 + 4y subject to the following constraints:
x + 2y14
3xy0
xy2

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

The constraints define the feasible region, which is the triangle shown below, including its interior.

Main steps in solving the problem

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

  • Create the variables.
  • Define the constraints.
  • Define the objective function.
  • Declare the solver — the method that implements an algorithm for finding the optimal solution.
  • Invoke the solver and display the results.

The following sections show how to implement these steps in each of the supported languages to solve the linear optimization problem:

Finding information in the C++ Reference pages

You can find detailed information about OR-Tools solvers and methods in the C++ Reference pages. Because OR-Tools is written in C++, the reference pages describe these methods in terms of their C++ code. If you are writing in Python, Java, or C#, the names of the corresponding methods in those languages are, for the most part, the same as the C++ names (with a few minor differences). So you can find useful information in the Reference pages no matter which language you are working in.

C++ example

Let's start by showing how to set up the problem in C++. We've added links from the methods used in this example to their reference pages, in case you want to learn about them in more detail. Here are the steps for setting up and solving the problem in C++:

  • Create the variables using the method MakeNumVar.
      MPVariable* const x = solver.MakeNumVar(0.0, infinity, "x");
      MPVariable* const y = solver.MakeNumVar(0.0, infinity, "y");
  • Define the constraints using the methods MakeRowConstraint and SetCoefficient.
        // x + 2y <= 14.
      MPConstraint* const c0 = solver.MakeRowConstraint(-infinity, 14.0);
      c0->SetCoefficient(x, 1);
      c0->SetCoefficient(y, 2);
    
      // 3x - y >= 0.
      MPConstraint* const c1 = solver.MakeRowConstraint(0.0, infinity);
      c1->SetCoefficient(x, 3);
      c1->SetCoefficient(y, -1);
    
      // x - y <= 2.
      MPConstraint* const c2 = solver.MakeRowConstraint(-infinity, 2.0);
      c2->SetCoefficient(x, 1);
      c2->SetCoefficient(y, -1);
    For example, for the first inequality, $$x + 2y \leq 14$$ the constraint is defined as follows:
    • MakeRowConstraint(-infinity, 14) creates an inequality constraint in which the left side is less than or equal to 14.
    • c0->SetCoefficient(x, 1); sets the coefficient of x to 1.
    • c0->SetCoefficient(y, 2); sets the coefficient of y to 2.
  • Define the objective function. The method SetCoefficient sets the coefficients of the function. The method SetMaximization makes this a maximization problem.
      // Objective function: 3x + 4y.
      MPObjective* const objective = solver.MutableObjective();
      objective->SetCoefficient(x, 3);
      objective->SetCoefficient(y, 4);
      objective->SetMaximization();
  • Declare the solver. In this example, we use the OR-Tools linear solver wrapper to invoke Glop, Google's linear optimizer. The following code declares the solver.
    void RunLinearExample(
      MPSolver::OptimizationProblemType optimization_problem_type) {
      MPSolver solver("LinearExample", optimization_problem_type);
    When the program calls the solver by
      RunLinearExample(MPSolver::GLOP_LINEAR_PROGRAMMING);
    the argument GLOP_LINEAR_PROGRAMMING, which tells the solver to use Glop, is passed to the solver through the OptimizationProblemType method.
  • Invoke the solver and display the results.
      printf("\nNumber of variables = %d", solver.NumVariables());
      printf("\nNumber of constraints = %d", solver.NumConstraints());
      solver.Solve();
      // The value of each variable in the solution.
      printf("\nSolution:");
      printf("\nx = %.1f", x->solution_value());
      printf("\ny = %.1f", y->solution_value());
    
      // The objective value of the solution.
      printf("\nOptimal objective value = %.1f", objective->Value());
      printf("\n");

Python example

Here are the steps for setting up and solving the problem in Python:

  • Create the variables.
      x = solver.NumVar(-solver.infinity(), solver.infinity(), 'x')
      y = solver.NumVar(-solver.infinity(), solver.infinity(), 'y')
    Note: NumVar is the Python name for the C++ method MakeNumVar.
  • Define the constraints.
      # Constraint 1: x + 2y <= 14.
      constraint1 = solver.Constraint(-solver.infinity(), 14)
      constraint1.SetCoefficient(x, 1)
      constraint1.SetCoefficient(y, 2)
    
      # Constraint 2: 3x - y >= 0.
      constraint2 = solver.Constraint(0, solver.infinity())
      constraint2.SetCoefficient(x, 3)
      constraint2.SetCoefficient(y, -1)
    
      # Constraint 3: x - y <= 2.
      constraint3 = solver.Constraint(-solver.infinity(), 2)
      constraint3.SetCoefficient(x, 1)
      constraint3.SetCoefficient(y, -1)
    Note: Constraint is the Python name for the C++ method MakeRowConstraint
  • Define the objective function.
      # Objective function: 3x + 4y.
      objective = solver.Objective()
      objective.SetCoefficient(x, 3)
      objective.SetCoefficient(y, 4)
      objective.SetMaximization()
  • Declare the solver. pywraplp is a Python wrapper for the underlying C++ solver. As in the C++ program, the argument GLOP_LINEAR_PROGRAMMING tells the solver to use Glop.
    from ortools.linear_solver import pywraplp
    
    def main():
      # Instantiate a Glop solver, naming it LinearExample.
      solver = pywraplp.Solver('LinearExample',
                               pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
  • Invoke the solver and display the results.
      # Solve the system.
      solver.Solve()
      opt_solution = 3 * x.solution_value() + 4 * y.solution_value()
      print('Number of variables =', solver.NumVariables())
      print('Number of constraints =', solver.NumConstraints())
      # The value of each variable in the solution.
      print('Solution:')
      print('x = ', x.solution_value())
      print('y = ', y.solution_value())
      # The objective value of the solution.
      print('Optimal objective value =', opt_solution)

Java example

Here are the steps for setting up and solving the problem in Java:

  • Create the variables.
        double infinity = MPSolver.infinity();
        // x and y are continuous non-negative variables.
        MPVariable x = solver.makeNumVar(0.0, infinity, "x");
        MPVariable y = solver.makeNumVar(0.0, infinity, "y");
  • Define the constraints.
        // x + 2y <= 14.
        MPConstraint c0 = solver.makeConstraint(-infinity, 14.0);
        c0.setCoefficient(x, 1);
        c0.setCoefficient(y, 2);
    
        // 3x - y >= 0.
        MPConstraint c1 = solver.makeConstraint(0.0, infinity);
        c1.setCoefficient(x, 3);
        c1.setCoefficient(y, -1);
    
        // x - y <= 2.
        MPConstraint c2 = solver.makeConstraint(-infinity, 2.0);
        c2.setCoefficient(x, 1);
        c2.setCoefficient(y, -1);
    Note: MakeConstraint is the Java name for the C++ method MakeRowConstraint.
  • Define the objective function.
        // Maximize 3 * x + 4 * y.
        MPObjective objective = solver.objective();
        objective.setCoefficient(x, 3);
        objective.setCoefficient(y, 4);
        objective.setMaximization();
  • Declare the solver. In this example, we use the OR-Tools linear solver wrapper to invoke Glop, Google's linear optimizer. The following code creates the solver.
        private static MPSolver createSolver (String solverType) {
        return new MPSolver("LinearExample",
                              MPSolver.OptimizationProblemType.valueOf(solverType));
      }
    When the program calls the solver by
        runLinearExample("GLOP_LINEAR_PROGRAMMING");
    the argument GLOP_LINEAR_PROGRAMMING, which tells the solver to use Glop, is passed to the solver through the OptimizationProblemType method.
  • Invoke the solver and display the results.
        System.out.println("Number of variables = " + solver.numVariables());
        System.out.println("Number of constraints = " + solver.numConstraints());
        solver.solve();
    
         // The value of each variable in the solution.
        System.out.println("Solution");
        System.out.println("x = " + x.solutionValue());
        System.out.println("y = " + y.solutionValue());
    
        // The objective value of the solution.
        System.out.println("Optimal objective value = " + solver.objective().value());

C# example

Here are the steps for setting up and solving the problem in C#:

  • Create the variables.
        Variable x = solver.MakeNumVar(0.0, double.PositiveInfinity, "x");
        Variable y = solver.MakeNumVar(0.0, double.PositiveInfinity, "y");
  • Define the constraints.
        // x + 2y <= 14.
        Constraint c0 = solver.MakeConstraint(double.NegativeInfinity, 14.0);
        c0.SetCoefficient(x, 1);
        c0.SetCoefficient(y, 2);
    
        // 3x - y >= 0.
        Constraint c1 = solver.MakeConstraint(0.0, double.PositiveInfinity);
        c1.SetCoefficient(x, 3);
        c1.SetCoefficient(y, -1);
    
        // x - y <= 2.
        Constraint c2 = solver.MakeConstraint(double.NegativeInfinity, 2.0);
        c2.SetCoefficient(x, 1);
        c2.SetCoefficient(y, -1);
    Note: MakeConstraint is the C# name for the C++ method MakeRowConstraint.
  • Define the objective function.
        // Objective function: 3x + 4y.
        Objective objective = solver.Objective();
        objective.SetCoefficient(x, 3);
        objective.SetCoefficient(y, 4);
        objective.SetMaximization();
  • Declare the solver. In this example, we use the OR-Tools linear solver wrapper to invoke Glop, Google's linear optimizer. The following code creates the solver.
        private static void RunLinearExample(String solverType)
      {
        Solver solver = Solver.CreateSolver("LinearExample", solverType);
    When the program calls the solver by
        RunLinearExample("GLOP_LINEAR_PROGRAMMING");
    the argument GLOP_LINEAR_PROGRAMMING, which tells the solver to use Glop, is passed to the solver through the OptimizationProblemType method.
  • Invoke the solver and display the results.
        Console.WriteLine("Number of variables = " + solver.NumVariables());
        Console.WriteLine("Number of constraints = " + solver.NumConstraints());
        solver.Solve();
        // The value of each variable in the solution.
        Console.WriteLine("Solution:");
        Console.WriteLine("x = " + x.SolutionValue());
        Console.WriteLine("y = " + y.SolutionValue());
        // The objective value of the solution.
        Console.WriteLine("Optimal objective value = " +
                          solver.Objective().Value());

Optimal solution

Each program returns the optimal solution to the problem, as shown below.

Number of variables = 2
Number of constraints = 3
Solution:
x = 6.0
y = 4.0
Optimal objective value = 34.0

Here is a graph showing the solution:

The dashed green line is defined by setting the objective function equal to its optimal value of 34. Any line whose equation has the form 3x + 4y = c is parallel to the dashed line, and 34 is the largest value of c for which the line intersects the feasible region.

If you think about the geometry in the above graph, in any linear optimization problem at least one vertex of the feasible region must be an optimal solution. As a result, you can find an optimal solution by traversing the vertices of the feasible region until there is no more improvement in the objective function. This is the idea behind simplex algorithm, the most widely-used method for solving linear optimization problems.

To learn more about solving linear optimization problems, see The Glop linear solver.

Complete programs in all the languages

The complete programs in all four languages are shown below.

C++ program
#include "ortools/linear_solver/linear_solver.h"
#include "ortools/linear_solver/linear_solver.pb.h"

namespace operations_research {
void RunLinearExample(
  MPSolver::OptimizationProblemType optimization_problem_type) {
  MPSolver solver("LinearExample", optimization_problem_type);
  const double infinity = solver.infinity();
  // x and y are non-negative variables.
  MPVariable* const x = solver.MakeNumVar(0.0, infinity, "x");
  MPVariable* const y = solver.MakeNumVar(0.0, infinity, "y");
  // Objective function: 3x + 4y.
  MPObjective* const objective = solver.MutableObjective();
  objective->SetCoefficient(x, 3);
  objective->SetCoefficient(y, 4);
  objective->SetMaximization();
  // x + 2y <= 14.
  MPConstraint* const c0 = solver.MakeRowConstraint(-infinity, 14.0);
  c0->SetCoefficient(x, 1);
  c0->SetCoefficient(y, 2);

  // 3x - y >= 0.
  MPConstraint* const c1 = solver.MakeRowConstraint(0.0, infinity);
  c1->SetCoefficient(x, 3);
  c1->SetCoefficient(y, -1);

  // x - y <= 2.
  MPConstraint* const c2 = solver.MakeRowConstraint(-infinity, 2.0);
  c2->SetCoefficient(x, 1);
  c2->SetCoefficient(y, -1);
  printf("\nNumber of variables = %d", solver.NumVariables());
  printf("\nNumber of constraints = %d", solver.NumConstraints());
  solver.Solve();
  // The value of each variable in the solution.
  printf("\nSolution:");
  printf("\nx = %.1f", x->solution_value());
  printf("\ny = %.1f", y->solution_value());

  // The objective value of the solution.
  printf("\nOptimal objective value = %.1f", objective->Value());
  printf("\n");
}

void RunExample() {
  RunLinearExample(MPSolver::GLOP_LINEAR_PROGRAMMING);
}
}  // namespace operations_research

int main(int argc, char** argv) {
  operations_research::RunExample();
  return 0;
}
Python program
from __future__ import print_function
from ortools.linear_solver import pywraplp

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

# Create the two variables and let them take on any value.
  x = solver.NumVar(-solver.infinity(), solver.infinity(), 'x')
  y = solver.NumVar(-solver.infinity(), solver.infinity(), 'y')

  # Constraint 1: x + 2y <= 14.
  constraint1 = solver.Constraint(-solver.infinity(), 14)
  constraint1.SetCoefficient(x, 1)
  constraint1.SetCoefficient(y, 2)

  # Constraint 2: 3x - y >= 0.
  constraint2 = solver.Constraint(0, solver.infinity())
  constraint2.SetCoefficient(x, 3)
  constraint2.SetCoefficient(y, -1)

  # Constraint 3: x - y <= 2.
  constraint3 = solver.Constraint(-solver.infinity(), 2)
  constraint3.SetCoefficient(x, 1)
  constraint3.SetCoefficient(y, -1)

  # Objective function: 3x + 4y.
  objective = solver.Objective()
  objective.SetCoefficient(x, 3)
  objective.SetCoefficient(y, 4)
  objective.SetMaximization()

  # Solve the system.
  solver.Solve()
  opt_solution = 3 * x.solution_value() + 4 * y.solution_value()
  print('Number of variables =', solver.NumVariables())
  print('Number of constraints =', solver.NumConstraints())
  # The value of each variable in the solution.
  print('Solution:')
  print('x = ', x.solution_value())
  print('y = ', y.solution_value())
  # The objective value of the solution.
  print('Optimal objective value =', opt_solution)
if __name__ == '__main__':
  main()
Java program
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

public class LinearExample {
  static { System.loadLibrary("jniortools"); }
  private static MPSolver createSolver (String solverType) {
    return new MPSolver("LinearExample",
                          MPSolver.OptimizationProblemType.valueOf(solverType));
  }
  private static void runLinearExample(String solverType) {
    MPSolver solver = createSolver(solverType);
    double infinity = MPSolver.infinity();
    // x and y are continuous non-negative variables.
    MPVariable x = solver.makeNumVar(0.0, infinity, "x");
    MPVariable y = solver.makeNumVar(0.0, infinity, "y");
    // Maximize 3 * x + 4 * y.
    MPObjective objective = solver.objective();
    objective.setCoefficient(x, 3);
    objective.setCoefficient(y, 4);
    objective.setMaximization();
    // x + 2y <= 14.
    MPConstraint c0 = solver.makeConstraint(-infinity, 14.0);
    c0.setCoefficient(x, 1);
    c0.setCoefficient(y, 2);

    // 3x - y >= 0.
    MPConstraint c1 = solver.makeConstraint(0.0, infinity);
    c1.setCoefficient(x, 3);
    c1.setCoefficient(y, -1);

    // x - y <= 2.
    MPConstraint c2 = solver.makeConstraint(-infinity, 2.0);
    c2.setCoefficient(x, 1);
    c2.setCoefficient(y, -1);
    System.out.println("Number of variables = " + solver.numVariables());
    System.out.println("Number of constraints = " + solver.numConstraints());
    solver.solve();

     // The value of each variable in the solution.
    System.out.println("Solution");
    System.out.println("x = " + x.solutionValue());
    System.out.println("y = " + y.solutionValue());

    // The objective value of the solution.
    System.out.println("Optimal objective value = " + solver.objective().value());
  }

  public static void main(String[] args) throws Exception {
    runLinearExample("GLOP_LINEAR_PROGRAMMING");
  }
}
C# program
using System;
using Google.OrTools.LinearSolver;

public class LinearExample
{
  private static void RunLinearExample(String solverType)
  {
    Solver solver = Solver.CreateSolver("LinearExample", solverType);
    // x and y are continuous non-negative variables.
    Variable x = solver.MakeNumVar(0.0, double.PositiveInfinity, "x");
    Variable y = solver.MakeNumVar(0.0, double.PositiveInfinity, "y");
    // Objective function: 3x + 4y.
    Objective objective = solver.Objective();
    objective.SetCoefficient(x, 3);
    objective.SetCoefficient(y, 4);
    objective.SetMaximization();
    // x + 2y <= 14.
    Constraint c0 = solver.MakeConstraint(double.NegativeInfinity, 14.0);
    c0.SetCoefficient(x, 1);
    c0.SetCoefficient(y, 2);

    // 3x - y >= 0.
    Constraint c1 = solver.MakeConstraint(0.0, double.PositiveInfinity);
    c1.SetCoefficient(x, 3);
    c1.SetCoefficient(y, -1);

    // x - y <= 2.
    Constraint c2 = solver.MakeConstraint(double.NegativeInfinity, 2.0);
    c2.SetCoefficient(x, 1);
    c2.SetCoefficient(y, -1);
    Console.WriteLine("Number of variables = " + solver.NumVariables());
    Console.WriteLine("Number of constraints = " + solver.NumConstraints());
    solver.Solve();
    // The value of each variable in the solution.
    Console.WriteLine("Solution:");
    Console.WriteLine("x = " + x.SolutionValue());
    Console.WriteLine("y = " + y.SolutionValue());
    // The objective value of the solution.
    Console.WriteLine("Optimal objective value = " +
                      solver.Objective().Value());
  }

  static void Main()
  {
    RunLinearExample("GLOP_LINEAR_PROGRAMMING");
  }
}

Identifying the type of problem you wish to solve

There are many different types of optimization problems in the world. For each type of problem, there are different approaches and algorithms for finding an optimal solution. Before you can start writing a program to solve an optimization problem, you need to identify what type of problem you are dealing with, and then choose an appropriate solver — an algorithm for finding an optimal solution.

Below you will find a brief overview of the types of problems that OR-Tools solves, and links to the sections in this guide that explain how to solve each problem type.

Linear optimization

As you learned in the previous section, a linear optimization problem is one in which the objective function and the constraints linear expressions in the variables. The primary solver in OR-Tools for this type of problem is the linear optimization solver, which is actually a wrapper for several different libraries for linear and mixed-integer optimization, including third-party libraries.

Learn more about linear optimization

Mixed-integer optimization

A mixed integer optimization problem is one in which some or all of the variables are required to be integers. An example is the assignment problem, in which a group of workers needs be assigned to a set of tasks. For each worker and task, you define a variable whose value is 1 if the given worker is assigned to the given task, and 0 otherwise. In this case, the variables can only take on the values 0 or 1.

Learn more about mixed-integer optimization

Bin packing

Bin packing is the problem of packing a set of objects of different sizes into containers with different capacities. The goal is to pack as many of the objects as possible, subject to the capacities of the containers. A special case of this is the knapsack problem, in which there is just one container.

Learn more about bin packing

Network flows

Many optimization problems can be represented by a directed graph consisting of nodes and directed arcs between them. For example, transportation problems, in which goods are shipped across a railway network, can be represented by a graph in which the arcs are rail lines and the nodes are distribution centers. In the maximum flow problem, each arc has a maximum capacity that can be transported across it. The problem is to assign the amount of goods to be shipped across each arc so that the total quantity being transported is as large as possible.

Learn more about network flows

Assignment

Assignment problems involve assigning a group of agents (say, workers or machines) to a set of tasks, where there is a fixed cost for assigning each agent to a specific task. The problem is to find the assignment with the least total cost. Assignment problems are actually a special case of network flow problems.

Learn more about assignment

Scheduling

Scheduling problems involve assigning resources to perform a set of tasks at specific times. An important example is the job shop problem, in which multiple jobs are processed on several machines. Each job consists of a sequence of tasks, which must be performed in a given order, and each task must be processed on a specific machine. The problem is to assign a schedule so that all jobs are completed in as short an interval of time as possible.

Learn more about scheduling

Routing

Routing problems involve finding the optimal routes for a fleet of vehicles to traverse a network, defined by a directed graph. The problem of assigning packages to delivery trucks, described in What is an optimization problem?, is one example of a routing problem. Another is the traveling salesman problem.

Learn more about routing

Send feedback about...

Optimization
Optimization