# Solving a MIP Problem

This section provides an example of solving a mixed-integer programming (MIP) problem.

## Basic steps for solving a MIP problem

To solve a MIP problem, your program should include the following steps.

### Import the linear solver wrapper

Import the OR-Tools linear solver wrapper, an interface for MIP solvers and the Glop linear solver, as shown below.

### 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.Loader;

### C#

```using System;

### Declare the MIP solver

Declare the MIP solver you want to use. The code below declares the SCIP (Solving Constraint Integer Programs) solver.

### Python

```# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver('SCIP')```

### C++

```// Create the mip solver with the SCIP backend.
MPSolver solver("simple_mip_program",
MPSolver::SCIP_MIXED_INTEGER_PROGRAMMING);```

### Java

```// Create the linear solver with the SCIP backend.
MPSolver solver = MPSolver.createSolver("SCIP");
if (solver == null) {
System.out.println("Could not create solver SCIP");
return;
}```

### C#

```// Create the linear solver with the SCIP backend.
Solver solver = Solver.CreateSolver("SCIP");```

Note: If you install OR-Tools from source, there are other third-party solvers available. See the "Install from Source" section of the installation guide for your platform.

### Call the MIP solver

The following code calls the solver.

### Python

`status = solver.Solve()`

### 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();`

### C#

`Solver.ResultStatus resultStatus = solver.Solve();`

## MIP Example

The following sections present an example of a MIP and show how to solve it. Here's the 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 constraints 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 is very similar to the linear optimization problem described in Linear Optimization with Glop, but in this case we require the solutions to be integers.

### Import the linear solver wrapper

To begin, you must import (or include) the linear solver wrapper.

### 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.Loader;

### C#

```using System;

### Declare the MIP solver

The following code declares the MIP solver for the problem. This example uses the third-party solver SCIP.

Note: If you build OR-Tools from source and wish to install and use a different solver, see the installation guide guide for your platform.

### Python

```# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver('SCIP')```

### C++

```// Create the mip solver with the SCIP backend.
MPSolver solver("simple_mip_program",
MPSolver::SCIP_MIXED_INTEGER_PROGRAMMING);```

### Java

```// Create the linear solver with the SCIP backend.
MPSolver solver = MPSolver.createSolver("SCIP");
if (solver == null) {
System.out.println("Could not create solver SCIP");
return;
}```

### C#

```// Create the linear solver with the SCIP backend.
Solver solver = Solver.CreateSolver("SCIP");```

### 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 `MakeIntVar` method (or a variant, depending on the coding language) to create variables x and y that take on non-negative integer values.

### Define the constraints

The following code defines the constraints for the problem.

### Python

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

# 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.

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();```

### Java

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

### C#

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

### Call the solver

The following code calls the solver.

### Python

`status = solver.Solve()`

### 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();`

### C#

`Solver.ResultStatus resultStatus = solver.Solve();`

### Display the solution

The following code displays the solution.

### Python

```if status == pywraplp.Solver.OPTIMAL:
print('Solution:')
print('Objective value =', solver.Objective().Value())
print('x =', x.solution_value())
print('y =', y.solution_value())
else:
print('The problem does not have an optimal solution.')```

### C++

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

### Java

```    if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
System.out.println("Solution:");
System.out.println("Objective value = " + objective.value());
System.out.println("x = " + x.solutionValue());
System.out.println("y = " + y.solutionValue());```

### C#

```// 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());```

Here is the solution to the problem.

```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.

### Complete programs

Here are the complete programs.

### Python

```from __future__ import print_function
from ortools.linear_solver import pywraplp

def main():
# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver('SCIP')

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.

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

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

status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL:
print('Solution:')
print('Objective value =', solver.Objective().Value())
print('x =', x.solution_value())
print('y =', y.solution_value())
else:
print('The problem does not have an optimal solution.')

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 SimpleMipProgram() {
// Create the mip solver with the SCIP backend.
MPSolver solver("simple_mip_program",
MPSolver::SCIP_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) << "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::SimpleMipProgram();
return EXIT_SUCCESS;
}```

### Java

```package com.google.ortools.linearsolver.samples;

/** Minimal Mixed Integer Programming example to showcase calling the solver. */
public class SimpleMipProgram {
public static void main(String[] args) throws Exception {
// Create the linear solver with the SCIP backend.
MPSolver solver = MPSolver.createSolver("SCIP");
if (solver == null) {
System.out.println("Could not create solver SCIP");
return;
}

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();

if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
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("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");
} else {
System.err.println("The problem does not have an optimal solution!");
}
}
}```

### C#

```using System;

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

// 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.

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("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 SCIP backend.
solver = pywraplp.Solver.CreateSolver('SCIP')```

### C++

```// Create the mip solver with the SCIP backend.
MPSolver solver("simple_mip_program",
MPSolver::SCIP_MIXED_INTEGER_PROGRAMMING);```

### Java

```// Create the linear solver with the SCIP backend.
MPSolver solver = MPSolver.createSolver("SCIP");
if (solver == null) {
System.out.println("Could not create solver SCIP");
return;
}```

### C#

```// Create the linear solver with the SCIP backend.
Solver solver = Solver.CreateSolver("SCIP");```
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.

[{ "type": "thumb-down", "id": "missingTheInformationINeed", "label":"Missing the information I need" },{ "type": "thumb-down", "id": "tooComplicatedTooManySteps", "label":"Too complicated / too many steps" },{ "type": "thumb-down", "id": "outOfDate", "label":"Out of date" },{ "type": "thumb-down", "id": "samplesCodeIssue", "label":"Samples/Code issue" },{ "type": "thumb-down", "id": "otherDown", "label":"Other" }]
[{ "type": "thumb-up", "id": "easyToUnderstand", "label":"Easy to understand" },{ "type": "thumb-up", "id": "solvedMyProblem", "label":"Solved my problem" },{ "type": "thumb-up", "id": "otherUp", "label":"Other" }]