Integer Optimization – Mixed Integer Program(MIP) with Python

A Mixed Integer Program(MIP) is a linear optimization problem that requires that some of the variables be integers.  These variables could either be integer variables or boolean variables.

Let’s take an example, then we solve it using Python.

• An MIP Example
• Step 1 – Create the Solver
• Step 2 – Declare the Variables
• Step 3 – Create your Constraints
• Step 4 – Define the Cost Function
• Step 5 – Invoke the Solve() and Print Results
• Using MIP Approach

An MIP Example

Maximize the function f(x, y) = x + 10 subject to the following constraints:

Solution

For clarity, we would solve this problem using the simple 5-step linear programming approach. Then we would modify the program to use an MIP approach.

Step 1 – Create your solver

You’ll need to import the ortools.linear_solver from pywrap and create a solver variable. the code below does that

# IMPORT THE SOLVER
from ortools.linear_solver import pywraplp
solver = pywraplp.Solver.CreateSolver('GLOP')

Step 2 – Declare the variables

We do this using the solver’s NumVar method and specify: the upper bound, the lower bound and the variable name.

# DECLARE THE VARIABLES
x = solver.NumVar(0, 3.5, 'x')
y = solver.NumVar(0, solver.infinity(), 'y')

Step 3 – Create the Constraints

Constraints are of the form 0 <= f(x,y) <= 17.5. We would create only this one constraints because the other constraints have been implicitly created with the variable declaration.

# CREATE THE CONSTRAINT 0 <= f(x,y) <= 17.5
ct = solver.Constraint(0, 17.5) # specifies upper and lower bound
ct.SetCoefficient(x, 1) # specify the x coefficient
ct.SetCoefficient(y, 7) # specify the y coefficient

Step 4 – Define the Cost function

We simply declare the objective variable and then set the coefficient of x and y in the function.

# DEFINE THE OBJECTIVE FUNCTION x + 10y
obj = solver.Objective()
obj.SetCoefficient(x, 1)
obj.SetCoefficient(y, 10)
obj.SetMaximization() # set the problem goal as maximization

Step 5 – Call the Solver and display the result

You must say solver.Solve(). The value of the objective function is in the Value() method of the objective variable. Similarly, the value of each variable if in the solution_value() method of each of the variables. The code below displays the results.

# CALL THE SOLVER AND SHOW THE RESULT
solver.Solve()
print('Objective value = ', obj.Value())
print('x = ', x.solution_value())
print('y = ', y.solution_value())

The result is given below:

Objective value =  25.0
x =  0.0
y =  2.5

Solving Using MIP Approach

To solve using MIP you need to make just a few changes.

• in the variable declaration, instead of using NumVar(), you use IntVar()
• in creating the solver, you need to use ‘SCIP’ instead of ‘GLOP”

If you make this changes, then you will have the output:

Objective value =  23.0
x =  3.0
y =  2.0

Find the complete program below: