Linear integer programming with Google ortools in Python

In a several other posts on Google’s ortools module in Python I have already solved the linear optimization problem stated below. The problem is a continuous problem as all optimization variables are from a continuous solution space.

I could think of a similar problem but with integer optimization variables. That would make the problem an integer optimization problem (with a discrete solution space). I have restated the problem and added a mathematical statement indicating that all optimization variabes are integers:

The workflow for solving this problem with ortools in Python is very similar to the one introduced in previous posts.

I start by importing pywraplp from ortools.linear_solver:

from ortools.linear_solver import pywraplp

Next, I create a solver instance and store its reference to a reference handler. This time I do not use the GLOP but instead the CBC solver:

solver = pywraplp.Solver.CreateSolver('linear_programming_examples', 'CBC')

I now have to declare relevant optimization variables. In this example the optimization variables are x, y and z and when declaring them I define the lower and upper bounds as per matehamtical problem statement. Also, I declare optimization variables to be integers by using the IntVar() constructor instead of the NumVar() constructor:

# declare variable x, with lower bound 0 and no upper bound - it is an integer (IntVar)
x = solver.IntVar(0, solver.infinity(), "x")
# declare variable y, with lower bound 0 and no upper bound - it is an integer (IntVar)
y = solver.IntVar(0, solver.infinity(), "y")
# declare variable z, with lower bound 0 and no upper bound - it is an integer (IntVar)
z = solver.IntVar(0, solver.infinity(), "z")

The workflow is now the same as in the most recent post containing the continuous problem. I model the problem by adding the objective function and the constraints to the solver:

# declare as maximization problen and define objective function
solver.Maximize(x+2*y+3*z)
# add constraints
solver.Add(2*x+y+z <= 20)
solver.Add(x+y+z <= 15)
solver.Add(x-y-z >= 0)
<ortools.linear_solver.pywraplp.Constraint; proxy of <Swig Object of type 'operations_research::MPConstraint *' at 0x000001D4F116CFC0> >

After having completed the model I can now solve the problem:

solver.Solve()
0

The optimal solution for x is outputed below:

print("x_opt: ", x.solution_value())
x_opt:  7.0

The optimal solution for y is outputed below:

print("y_opt: ", y.solution_value())
y_opt:  0.0

The optimal solution for z is outputed below:

print("z_opt: ", z.solution_value())
z_opt:  6.0

The optimal objective function value is outputed below:

print("optimal value: " + str(x.solution_value()+2*y.solution_value()+3*z.solution_value()))
optimal value: 25.0

As you can see the optimal values are integers. You can also see that the optimal objective function value has decreased, since the additional constraint of variables being from discrete solution space limits the range of possibilities for maximizing the objective. In the continuous case the optimal outcome was 26.66. Now, the optimal outcome is 25.0.

Leave a Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Meta