An MIP Problem with Python with Constraints Define with Arrays

In the previous tutorial, we learnt how to solve a Mixed Integer Program(MIP) problem in Python. In that example there were very few constraints and so we manually specified them.

We would now look at situation where there are many constraints such that they have to be represented as an array. Let’s take an example:

Example 1 – Maximize the function 7x₁ + 8x₂ + 2x₃ + 9x₄ + 6x₅ with respect to the following constraints:

Also x₁, x₂, x₃, x₄, x₅ are integers

Solution:

We would follow the same 5 step procedure we followed previously

First let’s represent the given problem using the following:

• a 2-d array of coefficients – coefs
• array of the maximums(right-hand-side) – maxs
• array of unknowns (x1, x2,…, x5) – unknowns
• array of cost function coefficients – cost_fn

All these are clearly shown below:

coefs = [[5, 7, 9, 2, 1],
        [18, 4, -9, 10, 12],
        [4, 7, 3, 8, 5],
        [5, 13, 15, 3, -7]]

maxs = [250,  285, 211, 315] 

unknowns = ['x1','x2','x3','x4','x5']

cost_fn = [7, 8, 2, 9, 6]

Step 1 – Create the Solver

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

Step 2 – Declare the variables

To do this, we loop through the unknown and populate the variables array as shown below:

# DECLARE THE VARIABLES
variables = [[]] * len(unknowns)
for i in range(0, len(unknowns)):
    variables[i] = solver.IntVar(0, solver.infinity(), unknowns[i])

Step 3 – Create the contraints.

We do this by looping  through the constraints with an outer loop. Then, for each iteration, create a new constraint. Then we use an inner loop to iterate through the coefficients and assign the coefficients of each variable.

# CREATE THE CONSTRAINT 0 <= f(x,y) <= 17.5
constraints = [0] * len(coefs)

for i in range(0, len(coefs)):
    constraints[i] = solver.Constraint(0, maxs[i])
    for j in range(0, len(coefs[i])):
        constraints[i].SetCoefficient(variables[j], coefs[i][j])

Step 4 – Setup the Objective function

To do this, we loop through the cost_fn array and assign coefficients to the corresponding variable

# DEFINE THE OBJECTIVE FUNCTION 7x1 + 8x2 + 2x3 + 9x4 + 6x5
obj = solver.Objective()
for i in range(0, len(cost_fn)):
    obj.SetCoefficient(variables[i], cost_fn[i])

obj.SetMaximization() # set the problem goal as maximization

Step 5 – Call the Solver() and print the result

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

# PRINT THE RESULTS
for i in range(0, len(unknowns)):
    print('%s = %f' %(unknowns[i], variables[i].solution_value()))

The output of the program is given below:

Objective value =  260.0000000000009
x1 = 8.000000
x2 = 21.000000
x3 = 0.000000
x4 = 2.000000
x5 = 3.000000

The complete program is given below: