Mixed-Integer Programming

The following sections describe how solve mixed-integer programming (MIP) problems with OR-Tools.

MIP solvers

OR-Tools provides an interface to several MIP solvers. By default, it uses Coin-or branch and cut (CBC), an open-source solver. If you build OR-Tools from source, you can install and use the following third-party MIP solvers in place of CBC:

Note: To use a third-party solver other than CBC, you must install it and then build OR-Tools from source.

Using a MIP solver with the OR-Tools linear solver wrapper

To use a MIP solver, you first declare it with the OR-Tools linear solver wrapper — a wrapper for several linear and mixed-integer optimization libraries. The following sections show how to use a MIP solver.

Using a MIP solver

The following shows how to use the MIP solver CBC. Using other MIP solvers is similar. First, you must include or import the linear solver header(s).

Include or import the linear solver

Python

from __future__ import print_function
from ortools.linear_solver import pywraplp

C++

#include "ortools/linear_solver/linear_solver.h"

Java

import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

C#

using System;
using Google.OrTools.LinearSolver;

Declare the linear solver

Python

    # Create the mip solver with the CBC backend.
    solver = pywraplp.Solver('simple_mip_program',
                             pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

C++

  // Create the mip solver with the CBC backend.
  MPSolver solver("simple_mip_program",
                  MPSolver::CBC_MIXED_INTEGER_PROGRAMMING);

Java

    // Create the linear solver with the CBC backend.
    MPSolver solver = new MPSolver(
        "SimpleMipProgram", MPSolver.OptimizationProblemType.CBC_MIXED_INTEGER_PROGRAMMING);

C#

    // Create the linear solver with the CBC backend.
    Solver solver = Solver.CreateSolver("SimpleMipProgram", "CBC_MIXED_INTEGER_PROGRAMMING");

Call the solver

Python

    result_status = solver.Solve()
    # The problem has an optimal solution.
    assert result_status == pywraplp.Solver.OPTIMAL

    # The solution looks legit (when using solvers others than
    # GLOP_LINEAR_PROGRAMMING, verifying the solution is highly recommended!).
    assert solver.VerifySolution(1e-7, True)

C++

  const MPSolver::ResultStatus result_status = solver.Solve();
  // Check that the problem has an optimal solution.
  if (result_status != MPSolver::OPTIMAL) {
    LOG(FATAL) << "The problem does not have an optimal solution!";
  }

Java

    final MPSolver.ResultStatus resultStatus = solver.solve();
    // Check that the problem has an optimal solution.
    if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
      System.err.println("The problem does not have an optimal solution!");
      return;
    }
    // Verify that the solution satisfies all constraints (when using solvers
    // others than GLOP_LINEAR_PROGRAMMING, this is highly recommended!).
    if (!solver.verifySolution(/*tolerance=*/1e-7, /*log_errors=*/true)) {
      System.err.println("The solution returned by the solver violated the"
          + " problem constraints by at least 1e-7");
      return;
    }

C#

    Solver.ResultStatus resultStatus = solver.Solve();
    // Check that the problem has an optimal solution.
    if (resultStatus != Solver.ResultStatus.OPTIMAL)
    {
      Console.WriteLine("The problem does not have an optimal solution!");
      return;
    }

MIP Example

The following is a simple example of a mixed-integer programming problem:

Maximize x + 10y subject to the following constraints:
x + 7 y17.5
x3.5
x0
y0
x, y integers

Since the contraints are linear, this is just a linear optimization problem in which the solutions are required to be integers. The graph below shows the integer points in the feasible region for the problem.

Notice that this problem looks quite similar to the linear optimization problem described in Linear Optimization with Glop, except for the integer conditions. Fortunately, you can easily modify the linear optimization Python program, described in that section, to solve this problem. All you have to change (besides the constraints and objective function) is the solver and the types of variables defined.

The following sections present the main elements of a Python program that solves the integer problem.

Include or import the linear solver

First, you must include or import the linear solver header(s).

Python

from __future__ import print_function
from ortools.linear_solver import pywraplp

C++

#include "ortools/linear_solver/linear_solver.h"

Java

import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

C#

using System;
using Google.OrTools.LinearSolver;

Declare the solver

The following code declares the solver for the problem.

Python

    # Create the mip solver with the CBC backend.
    solver = pywraplp.Solver('simple_mip_program',
                             pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

C++

  // Create the mip solver with the CBC backend.
  MPSolver solver("simple_mip_program",
                  MPSolver::CBC_MIXED_INTEGER_PROGRAMMING);

Java

    // Create the linear solver with the CBC backend.
    MPSolver solver = new MPSolver(
        "SimpleMipProgram", MPSolver.OptimizationProblemType.CBC_MIXED_INTEGER_PROGRAMMING);

C#

    // Create the linear solver with the CBC backend.
    Solver solver = Solver.CreateSolver("SimpleMipProgram", "CBC_MIXED_INTEGER_PROGRAMMING");

Define the variables

The following code defines the variables in the problem.

Python

    infinity = solver.infinity()
    # x and y are integer non-negative variables.
    x = solver.IntVar(0.0, infinity, 'x')
    y = solver.IntVar(0.0, infinity, 'y')

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

C++

  const double infinity = solver.infinity();
  // x and y are integer non-negative variables.
  MPVariable* const x = solver.MakeIntVar(0.0, infinity, "x");
  MPVariable* const y = solver.MakeIntVar(0.0, infinity, "y");

  LOG(INFO) << "Number of variables = " << solver.NumVariables();

Java

    double infinity = java.lang.Double.POSITIVE_INFINITY;
    // x and y are integer non-negative variables.
    MPVariable x = solver.makeIntVar(0.0, infinity, "x");
    MPVariable y = solver.makeIntVar(0.0, infinity, "y");

    System.out.println("Number of variables = " + solver.numVariables());

C#

    // x and y are integer non-negative variables.
    Variable x = solver.MakeIntVar(0.0, double.PositiveInfinity, "x");
    Variable y = solver.MakeIntVar(0.0, double.PositiveInfinity, "y");

    Console.WriteLine("Number of variables = " + solver.NumVariables());

The program uses the IntVar method to create variables x and y that can only take on integer values.

Note: This differs from the linear optimization program, which uses the solver.NumVar method to create variables that can take on any real number values.

Define the constraints

The following code defines the constraints in the problem:

Python

    # x + 7 * y <= 17.5.
    solver.Add(x + 7 * y <= 17.5)

    # x <= 3.5.
    solver.Add(x <= 3.5)

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

C++

  // x + 7 * y <= 17.5.
  MPConstraint* const c0 = solver.MakeRowConstraint(-infinity, 17.5, "c0");
  c0->SetCoefficient(x, 1);
  c0->SetCoefficient(y, 7);

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

  LOG(INFO) << "Number of constraints = " << solver.NumConstraints();

Java

    // x + 7 * y <= 17.5.
    MPConstraint c0 = solver.makeConstraint(-infinity, 17.5, "c0");
    c0.setCoefficient(x, 1);
    c0.setCoefficient(y, 7);

    // x <= 3.5.
    MPConstraint c1 = solver.makeConstraint(-infinity, 3.5, "c1");
    c1.setCoefficient(x, 1);
    c1.setCoefficient(y, 0);

    System.out.println("Number of constraints = " + solver.numConstraints());

C#

    // x + 7 * y <= 17.5.
    solver.Add(x + 7 * y <= 17.5);

    // x <= 3.5.
    solver.Add(x <= 3.5);

    Console.WriteLine("Number of constraints = " + solver.NumConstraints());

Define the objective

The following code defines the objective function for the problem.

Python

    # Maximize x + 10 * y.
    solver.Maximize(x + 10 * y)

C++

  // Maximize x + 10 * y.
  MPObjective* const objective = solver.MutableObjective();
  objective->SetCoefficient(x, 1);
  objective->SetCoefficient(y, 10);
  objective->SetMaximization();

The SetCoefficient method sets the coefficients of the objective function. The SetMaximization method makes this a maximization problem.

Java

    // Maximize x + 10 * y.
    MPObjective objective = solver.objective();
    objective.setCoefficient(x, 1);
    objective.setCoefficient(y, 10);
    objective.setMaximization();

The SetCoefficient method sets the coefficients of the objective function. The SetMaximization method makes this a maximization problem.

C#

    // Maximize x + 10 * y.
    solver.Maximize(x + 10 * y);

Invoke the solver

The following code invokes the solver.

Python

    result_status = solver.Solve()
    # The problem has an optimal solution.
    assert result_status == pywraplp.Solver.OPTIMAL

    # The solution looks legit (when using solvers others than
    # GLOP_LINEAR_PROGRAMMING, verifying the solution is highly recommended!).
    assert solver.VerifySolution(1e-7, True)

C++

  const MPSolver::ResultStatus result_status = solver.Solve();
  // Check that the problem has an optimal solution.
  if (result_status != MPSolver::OPTIMAL) {
    LOG(FATAL) << "The problem does not have an optimal solution!";
  }

Java

    final MPSolver.ResultStatus resultStatus = solver.solve();
    // Check that the problem has an optimal solution.
    if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
      System.err.println("The problem does not have an optimal solution!");
      return;
    }
    // Verify that the solution satisfies all constraints (when using solvers
    // others than GLOP_LINEAR_PROGRAMMING, this is highly recommended!).
    if (!solver.verifySolution(/*tolerance=*/1e-7, /*log_errors=*/true)) {
      System.err.println("The solution returned by the solver violated the"
          + " problem constraints by at least 1e-7");
      return;
    }

C#

    Solver.ResultStatus resultStatus = solver.Solve();
    // Check that the problem has an optimal solution.
    if (resultStatus != Solver.ResultStatus.OPTIMAL)
    {
      Console.WriteLine("The problem does not have an optimal solution!");
      return;
    }

Display the results

The following code displays the results.

Python

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

C++

  LOG(INFO) << "Solution:";
  LOG(INFO) << "Objective value = " << objective->Value();
  LOG(INFO) << "x = " << x->solution_value();
  LOG(INFO) << "y = " << y->solution_value();

Java

    System.out.println("Solution:");
    System.out.println("Objective value = " + objective.value());
    System.out.println("x = " + x.solutionValue());
    System.out.println("y = " + y.solutionValue());

C#

    Console.WriteLine("Solution:");
    Console.WriteLine("Objective value = " + solver.Objective().Value());
    Console.WriteLine("x = " + x.SolutionValue());
    Console.WriteLine("y = " + y.SolutionValue());

Here is the output of the program.

Number of variables = 2
Number of constraints = 2
Solution:
Objective value = 23
x = 3
y = 2

The optimal value of the objective function is 23, which occurs at the point x = 3, y = 2.

The entire program

Finally, here is the entire Python program.

Python

from __future__ import print_function
from ortools.linear_solver import pywraplp


def main():
    # Create the mip solver with the CBC backend.
    solver = pywraplp.Solver('simple_mip_program',
                             pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

    infinity = solver.infinity()
    # x and y are integer non-negative variables.
    x = solver.IntVar(0.0, infinity, 'x')
    y = solver.IntVar(0.0, infinity, 'y')

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

    # x + 7 * y <= 17.5.
    solver.Add(x + 7 * y <= 17.5)

    # x <= 3.5.
    solver.Add(x <= 3.5)

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

    # Maximize x + 10 * y.
    solver.Maximize(x + 10 * y)

    result_status = solver.Solve()
    # The problem has an optimal solution.
    assert result_status == pywraplp.Solver.OPTIMAL

    # The solution looks legit (when using solvers others than
    # GLOP_LINEAR_PROGRAMMING, verifying the solution is highly recommended!).
    assert solver.VerifySolution(1e-7, True)

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

    print('\nAdvanced usage:')
    print('Problem solved in %f milliseconds' % solver.wall_time())
    print('Problem solved in %d iterations' % solver.iterations())
    print('Problem solved in %d branch-and-bound nodes' % solver.nodes())


if __name__ == '__main__':
    main()

C++

#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void simple_mip_program() {
  // Create the mip solver with the CBC backend.
  MPSolver solver("simple_mip_program",
                  MPSolver::CBC_MIXED_INTEGER_PROGRAMMING);

  const double infinity = solver.infinity();
  // x and y are integer non-negative variables.
  MPVariable* const x = solver.MakeIntVar(0.0, infinity, "x");
  MPVariable* const y = solver.MakeIntVar(0.0, infinity, "y");

  LOG(INFO) << "Number of variables = " << solver.NumVariables();

  // x + 7 * y <= 17.5.
  MPConstraint* const c0 = solver.MakeRowConstraint(-infinity, 17.5, "c0");
  c0->SetCoefficient(x, 1);
  c0->SetCoefficient(y, 7);

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

  LOG(INFO) << "Number of constraints = " << solver.NumConstraints();

  // Maximize x + 10 * y.
  MPObjective* const objective = solver.MutableObjective();
  objective->SetCoefficient(x, 1);
  objective->SetCoefficient(y, 10);
  objective->SetMaximization();

  const MPSolver::ResultStatus result_status = solver.Solve();
  // Check that the problem has an optimal solution.
  if (result_status != MPSolver::OPTIMAL) {
    LOG(FATAL) << "The problem does not have an optimal solution!";
  }

  LOG(INFO) << "Solution:";
  LOG(INFO) << "Objective value = " << objective->Value();
  LOG(INFO) << "x = " << x->solution_value();
  LOG(INFO) << "y = " << y->solution_value();

  LOG(INFO) << "\nAdvanced usage:";
  LOG(INFO) << "Problem solved in " << solver.wall_time() << " milliseconds";
  LOG(INFO) << "Problem solved in " << solver.iterations() << " iterations";
  LOG(INFO) << "Problem solved in " << solver.nodes()
            << " branch-and-bound nodes";
}
}  // namespace operations_research

int main(int argc, char** argv) {
  operations_research::simple_mip_program();
  return EXIT_SUCCESS;
}

Java

import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

/** Minimal Mixed Integer Programming example to showcase calling the solver. */
public class SimpleMipProgram {
  static {
    System.loadLibrary("jniortools");
  }

  public static void main(String[] args) throws Exception {
    // Create the linear solver with the CBC backend.
    MPSolver solver = new MPSolver(
        "SimpleMipProgram", MPSolver.OptimizationProblemType.CBC_MIXED_INTEGER_PROGRAMMING);

    double infinity = java.lang.Double.POSITIVE_INFINITY;
    // x and y are integer non-negative variables.
    MPVariable x = solver.makeIntVar(0.0, infinity, "x");
    MPVariable y = solver.makeIntVar(0.0, infinity, "y");

    System.out.println("Number of variables = " + solver.numVariables());

    // x + 7 * y <= 17.5.
    MPConstraint c0 = solver.makeConstraint(-infinity, 17.5, "c0");
    c0.setCoefficient(x, 1);
    c0.setCoefficient(y, 7);

    // x <= 3.5.
    MPConstraint c1 = solver.makeConstraint(-infinity, 3.5, "c1");
    c1.setCoefficient(x, 1);
    c1.setCoefficient(y, 0);

    System.out.println("Number of constraints = " + solver.numConstraints());

    // Maximize x + 10 * y.
    MPObjective objective = solver.objective();
    objective.setCoefficient(x, 1);
    objective.setCoefficient(y, 10);
    objective.setMaximization();

    final MPSolver.ResultStatus resultStatus = solver.solve();
    // Check that the problem has an optimal solution.
    if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
      System.err.println("The problem does not have an optimal solution!");
      return;
    }
    // Verify that the solution satisfies all constraints (when using solvers
    // others than GLOP_LINEAR_PROGRAMMING, this is highly recommended!).
    if (!solver.verifySolution(/*tolerance=*/1e-7, /*log_errors=*/true)) {
      System.err.println("The solution returned by the solver violated the"
          + " problem constraints by at least 1e-7");
      return;
    }

    System.out.println("Solution:");
    System.out.println("Objective value = " + objective.value());
    System.out.println("x = " + x.solutionValue());
    System.out.println("y = " + y.solutionValue());

    System.out.println("\nAdvanced usage:");
    System.out.println("Problem solved in " + solver.wallTime() + " milliseconds");
    System.out.println("Problem solved in " + solver.iterations() + " iterations");
    System.out.println("Problem solved in " + solver.nodes() + " branch-and-bound nodes");
  }
}

C#

using System;
using Google.OrTools.LinearSolver;

public class SimpleMipProgram
{
  static void Main()
  {
    // Create the linear solver with the CBC backend.
    Solver solver = Solver.CreateSolver("SimpleMipProgram", "CBC_MIXED_INTEGER_PROGRAMMING");

    // x and y are integer non-negative variables.
    Variable x = solver.MakeIntVar(0.0, double.PositiveInfinity, "x");
    Variable y = solver.MakeIntVar(0.0, double.PositiveInfinity, "y");

    Console.WriteLine("Number of variables = " + solver.NumVariables());

    // x + 7 * y <= 17.5.
    solver.Add(x + 7 * y <= 17.5);

    // x <= 3.5.
    solver.Add(x <= 3.5);

    Console.WriteLine("Number of constraints = " + solver.NumConstraints());

    // Maximize x + 10 * y.
    solver.Maximize(x + 10 * y);

    Solver.ResultStatus resultStatus = solver.Solve();
    // Check that the problem has an optimal solution.
    if (resultStatus != Solver.ResultStatus.OPTIMAL)
    {
      Console.WriteLine("The problem does not have an optimal solution!");
      return;
    }

    Console.WriteLine("Solution:");
    Console.WriteLine("Objective value = " + solver.Objective().Value());
    Console.WriteLine("x = " + x.SolutionValue());
    Console.WriteLine("y = " + y.SolutionValue());

    Console.WriteLine("\nAdvanced usage:");
    Console.WriteLine("Problem solved in " + solver.WallTime() + " milliseconds");
    Console.WriteLine("Problem solved in " + solver.Iterations() + " iterations");
    Console.WriteLine("Problem solved in " + solver.Nodes() + " branch-and-bound nodes");
  }
}

Comparing Linear and Integer Optimization

Let's compare the solution to the integer optimization problem, shown above, with the solution to the corresponding linear optimization problem, in which integer constraints are removed. You might guess that the solution to the integer problem would be the integer point in the feasible region closest to the linear solution — namely, the point x = 0,  y = 2. But as you will see next, this is not the case.

You can easily modify the program in the preceding section to solve the linear problem by making the following changes:

  • Replace the MIP solver

    Python

        # Create the mip solver with the CBC backend.
        solver = pywraplp.Solver('simple_mip_program',
                                 pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

    C++

      // Create the mip solver with the CBC backend.
      MPSolver solver("simple_mip_program",
                      MPSolver::CBC_MIXED_INTEGER_PROGRAMMING);

    Java

        // Create the linear solver with the CBC backend.
        MPSolver solver = new MPSolver(
            "SimpleMipProgram", MPSolver.OptimizationProblemType.CBC_MIXED_INTEGER_PROGRAMMING);

    C#

        // Create the linear solver with the CBC backend.
        Solver solver = Solver.CreateSolver("SimpleMipProgram", "CBC_MIXED_INTEGER_PROGRAMMING");
    with the LP solver

    Python

        solver = pywraplp.Solver('simple_lp_program',
                                 pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

    C++

      MPSolver solver("simple_lp_program",
                      MPSolver::GLOP_LINEAR_PROGRAMMING);

    Java

        MPSolver solver =
            new MPSolver("SimpleLpProgram",
                         MPSolver.OptimizationProblemType.GLOP_LINEAR_PROGRAMMING);

    C#

    Solver solver = Solver.CreateSolver("SimpleLpProgram",
                                        "GLOP_LINEAR_PROGRAMMING");
  • Replace the integer variables

    Python

        infinity = solver.infinity()
        # x and y are integer non-negative variables.
        x = solver.IntVar(0.0, infinity, 'x')
        y = solver.IntVar(0.0, infinity, 'y')
    
        print('Number of variables =', solver.NumVariables())

    C++

      const double infinity = solver.infinity();
      // x and y are integer non-negative variables.
      MPVariable* const x = solver.MakeIntVar(0.0, infinity, "x");
      MPVariable* const y = solver.MakeIntVar(0.0, infinity, "y");
    
      LOG(INFO) << "Number of variables = " << solver.NumVariables();

    Java

        double infinity = java.lang.Double.POSITIVE_INFINITY;
        // x and y are integer non-negative variables.
        MPVariable x = solver.makeIntVar(0.0, infinity, "x");
        MPVariable y = solver.makeIntVar(0.0, infinity, "y");
    
        System.out.println("Number of variables = " + solver.numVariables());

    C#

        // x and y are integer non-negative variables.
        Variable x = solver.MakeIntVar(0.0, double.PositiveInfinity, "x");
        Variable y = solver.MakeIntVar(0.0, double.PositiveInfinity, "y");
    
        Console.WriteLine("Number of variables = " + solver.NumVariables());
    with continuous variables

    Python

        infinity = solver.infinity()
        x = solver.NumVar(0, infinity, 'x')
        y = solver.NumVar(0, infinity, 'y')
    
        print('Number of variables =', solver.NumVariables())

    C++

      const double infinity = solver.infinity();
      MPVariable* const x = solver.MakeNumVar(0.0, infinity, "x");
      MPVariable* const y = solver.MakeNumVar(0.0, infinity, "y");
    
      LOG(INFO) << "Number of variables = " << solver.NumVariables();

    Java

        double infinity = java.lang.Double.POSITIVE_INFINITY;
        MPVariable x = solver.makeNumVar(0.0, infinity, "x");
        MPVariable y = solver.makeNumVar(0.0, infinity, "y");
    
        System.out.println("Number of variables = " + solver.numVariables());

    C#

        Variable x = solver.MakeNumVar(0.0, double.PositiveInfinity, "x");
        Variable y = solver.MakeNumVar(0.0, double.PositiveInfinity, "y");
    
        Console.WriteLine("Number of variables = " + solver.NumVariables());

After making these changes and running the program again, you get the following output:

Number of variables = 2
Number of constraints = 2
Objective value = 25.000000
x = 0.000000
y = 2.500000

The solution to the linear problem occurs at the point x = 0,  y = 2.5, where the objective function equals 25. Here's a graph showing the solutions to both the linear and integer problems.

Notice that the integer solution is not close to the linear solution, compared with most other integer points in the feasible region. In general, the solutions to a linear optimization problem and the corresponding integer optimization problems can be far apart. Because of this, the two types of problems require different methods for their solution.