Solving an integer linear programming problem with linprog



In [1]:

    
from scipy.optimize import linprog
import numpy as np

Objective function

$$z(max) = 7x_1 + 6x_2$$

Constraints:

$C_1 = 2x_1 + 3x_2 \leq 12$
$C_2 = 6x_1 + 5x_2 \leq 30$
$x_1,x_2 \geq 0$
$x_1, x_2 \space must \space be \space Integers$



In [2]:

    
z = np.array([ 7, 6])



In [3]:

    
C = np.array([
    [ 2, 3],          #C1
    [ 6, 5]           #C2
])



In [4]:

    
b = np.array([12, 30])



In [5]:

    
x1 = (0, None)
x2 = (0, None)



In [6]:

    
sol = linprog(-z, A_ub = C, b_ub = b, bounds = (x1, x2), method='simplex')



In [7]:

    
sol









    Out[7]:





     fun: -35.25
 message: 'Optimization terminated successfully.'
     nit: 2
   slack: array([0., 0.])
  status: 0
 success: True
       x: array([3.75, 1.5 ])

In this case this problem is not giving Integer Variables.

Getting integer variables, add options={'maxiter':True} in the parameters of linprog.



In [8]:

    
sol = linprog(-z, A_ub = C, b_ub = b, bounds = (x1, x2), method='simplex', options={'maxiter':True})



In [9]:

    
sol









    Out[9]:





     fun: -35.0
 message: 'Iteration limit reached.'
     nit: 1
   slack: array([2., 0.])
  status: 1
 success: False
       x: array([5., 0.])

To print the values that we need:



In [10]:

    
print(f"x1 = {sol.x[0]}, x2 = {sol.x[1]}, z = {sol.fun*-1}")









    



x1 = 5.0, x2 = 0.0, z = 35.0

LP problem is solved, to check the result just replace the values $x_1$ and $x_2$ into the objective function.

$z(max) = 7x_1 + 6x_2$

$z(max) = 7*5 + 6*0$

$z(max) = 35$