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 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.
  1. Declare the linear solver wrapper.
    void RunMIPExample(
      MPSolver::OptimizationProblemType optimization_problem_type) {
      MPSolver solver("MIPExample", optimization_problem_type);
  2. 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 the OptimizationProblemType method.

Using Glop in Python

To use Glop in Python:

  1. Declare the solver using the Python wrapper pywraplp.
    from ortools.linear_solver import pywraplp
    
    def main():
      # Instantiate a mixed-integer solver, naming it SolveIntegerProblem.
      solver = pywraplp.Solver('SolveIntegerProblem',
                               pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
    Note that this also passes the argument CBC_MIXED_INTEGER_PROGRAMMING to the solver.
  2. Call the solver.
      result_status = solver.Solve()
    You don't need the CBC_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 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.

Define the variables

The following code defines the variables in the problem.

  # x and y are integer non-negative 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 mixed-integer solver, naming it SolveIntegerProblem.
  solver = pywraplp.Solver('SolveIntegerProblem',
                           pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

The program uses the Python wrapper pywraplpto 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(1e-7, 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 = 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.

from __future__ import print_function
from ortools.linear_solver import pywraplp

def main():
  # Instantiate a mixed-integer solver, naming it SolveIntegerProblem.
  solver = pywraplp.Solver('SolveIntegerProblem',
                           pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

  # x and y are integer non-negative 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(1e-7, 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)
    with
    solver = 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')
    with
    x = 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.

Enviar comentarios sobre…