The following sections describe how solve mixedinteger programming (MIP) problems with ORTools.
MIP solvers
ORTools provides an interface to several MIP solvers. By default, it uses Coinor branch and cut (CBC), an opensource solver. If you build ORTools from source, you can install and use the following thirdparty MIP solvers in place of CBC:
Note: To use a thirdparty solver other than CBC, you must install it and then build ORTools from source.Using a MIP solver with the ORTools linear solver wrapper
To use a MIP solver, you first declare it with the ORTools linear solver wrapper — a wrapper for several linear and mixedinteger 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 a MIP solver in C++
The following shows how to use the MIP solver CBC in C++. Using other MIP solvers is similar. Declare the linear solver wrapper.
void RunMIPExample( MPSolver::OptimizationProblemType optimization_problem_type) { MPSolver solver("MIPExample", optimization_problem_type);
 Call the solver wrapper with the argument
CBC_MIXED_INTEGER_PROGRAMMING
, which tells it to use CBC.RunMIPExample(MPSolver::CBC_MIXED_INTEGER_PROGRAMMING);
The input is passed to the solver wrapper through theOptimizationProblemType
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 mixedinteger solver, naming it SolveIntegerProblem. solver = pywraplp.Solver('SolveIntegerProblem', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
Note that this also passes the argumentCBC_MIXED_INTEGER_PROGRAMMING
to the solver.  Call the solver.
result_status = solver.Solve()
You don't need theCBC_MIXED_INTEGER_PROGRAMMING
argument, as it's already bundled with the solver.
The following is a simple example of a mixed integer programming problem:
 Maximize x + 10y subject to the following constraints:

x + 7 y ≤ 17.5 x ≤ 3.5 x ≥ 0 y ≥ 0 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.
Define the variables
The following code defines the variables in the problem.
# x and y are integer nonnegative variables. x = solver.IntVar(0.0, solver.infinity(), 'x') y = solver.IntVar(0.0, solver.infinity(), 'y')
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:
# x + 7 * y <= 17.5 constraint1 = solver.Constraint(solver.infinity(), 17.5) constraint1.SetCoefficient(x, 1) constraint1.SetCoefficient(y, 7) # x <= 3.5 constraint2 = solver.Constraint(solver.infinity(), 3.5) constraint2.SetCoefficient(x, 1) constraint2.SetCoefficient(y, 0)
Define the objective
The following code defines the objective function for the problem.
# Maximize x + 10 * y. 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.
Declare the solver
The following code declares the solver for the problem.
from ortools.linear_solver import pywraplp def main(): # Instantiate a mixedinteger solver, naming it SolveIntegerProblem. solver = pywraplp.Solver('SolveIntegerProblem', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
The program uses the Python wrapper pywraplp
to create an instance of
the CBC_MIXED_INTEGER_PROGRAMMING
solver.
Invoke the solver and display the results
The following code invokes the solver and displays the results.
result_status = solver.Solve() # The problem has an optimal solution. assert result_status == pywraplp.Solver.OPTIMAL # The solution looks legit (when using solvers other than # GLOP_LINEAR_PROGRAMMING, verifying the solution is highly recommended!). assert solver.VerifySolution(1e7, True) print('Number of variables =', solver.NumVariables()) print('Number of constraints =', solver.NumConstraints()) # The objective value of the solution. print('Optimal objective value = %d' % solver.Objective().Value()) print() # The value of each variable in the solution. variable_list = [x, y] for variable in variable_list: print('%s = %d' % (variable.name(), variable.solution_value()))
Here is the output of the program.
Optimal objective value = 23 Number of variables = 2 Number of constraints = 2 x = 3 y = 2The 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.
from __future__ import print_function from ortools.linear_solver import pywraplp def main(): # Instantiate a mixedinteger solver, naming it SolveIntegerProblem. solver = pywraplp.Solver('SolveIntegerProblem', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING) # x and y are integer nonnegative variables. x = solver.IntVar(0.0, solver.infinity(), 'x') y = solver.IntVar(0.0, solver.infinity(), 'y') # x + 7 * y <= 17.5 constraint1 = solver.Constraint(solver.infinity(), 17.5) constraint1.SetCoefficient(x, 1) constraint1.SetCoefficient(y, 7) # x <= 3.5 constraint2 = solver.Constraint(solver.infinity(), 3.5) constraint2.SetCoefficient(x, 1) constraint2.SetCoefficient(y, 0) # Maximize x + 10 * y. objective = solver.Objective() objective.SetCoefficient(x, 1) objective.SetCoefficient(y, 10) objective.SetMaximization() """Solve the problem and print the solution.""" result_status = solver.Solve() # The problem has an optimal solution. assert result_status == pywraplp.Solver.OPTIMAL # The solution looks legit (when using solvers other than # GLOP_LINEAR_PROGRAMMING, verifying the solution is highly recommended!). assert solver.VerifySolution(1e7, True) print('Number of variables =', solver.NumVariables()) print('Number of constraints =', solver.NumConstraints()) # The objective value of the solution. print('Optimal objective value = %d' % solver.Objective().Value()) print() # The value of each variable in the solution. variable_list = [x, y] for variable in variable_list: print('%s = %d' % (variable.name(), variable.solution_value())) if __name__ == '__main__': main()
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
solver = pywraplp.Solver('SolveIntegerProblem', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
withsolver = pywraplp.Solver('SolveSimpleSystem', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
 Replace
x = solver.IntVar(0.0, solver.infinity(), 'x') y = solver.IntVar(0.0, solver.infinity(), 'y')
withx = solver.NumVar(solver.infinity(), solver.infinity(), 'x') y = solver.NumVar(solver.infinity(), solver.infinity(), 'y')
After making these changes and running the program again, you get the following output:
Number of variables = 2 Number of constraints = 2 Optimal 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.