Linear Programming with Python

Install the packages

python -m pip install -U "scipy==1.4.*" "pulp==2.1"

In [2]:
!pulptest
Solver <class 'pulp.apis.coin_api.PULP_CBC_CMD'> available
Solver <class 'pulp.apis.cplex_api.CPLEX_DLL'> unavailable
Solver <class 'pulp.apis.cplex_api.CPLEX_CMD'> unavailable
Solver <class 'pulp.apis.cplex_api.CPLEX_PY'> unavailable
Solver <class 'pulp.apis.coin_api.COIN_CMD'> unavailable
Solver <class 'pulp.apis.coin_api.COINMP_DLL'> unavailable
Solver <class 'pulp.apis.glpk_api.GLPK_CMD'> unavailable
Solver <class 'pulp.apis.xpress_api.XPRESS'> unavailable
Solver <class 'pulp.apis.gurobi_api.GUROBI'> unavailable
Solver <class 'pulp.apis.gurobi_api.GUROBI_CMD'> unavailable
Solver <class 'pulp.apis.glpk_api.PYGLPK'> unavailable
Solver <class 'pulp.apis.coin_api.YAPOSIB'> unavailable
Solver <class 'pulp.apis.choco_api.PULP_CHOCO_CMD'> available
Solver <class 'pulp.apis.mipcl_api.MIPCL_CMD'> unavailable
Solver <class 'pulp.apis.mosek_api.MOSEK'> unavailable
	 Testing zero subtraction
.	 Testing inconsistant lp solution
.	 Testing continuous LP solution
.	 Testing maximize continuous LP solution
.	 Testing unbounded continuous LP solution
.	 Testing Long Names
.	 Testing repeated Names
.	 Testing zero constraint
.	 Testing zero objective
.	 Testing LpVariable (not LpAffineExpression) objective
.	 Testing Long lines in LP
.	 Testing LpAffineExpression divide
.	 Testing MIP solution
.	 Testing MIP solution with floats in objective
.	 Testing MIP relaxation
.	 Testing feasibility problem (no objective)
.	 Testing an infeasible problem
.	 Testing an integer infeasible problem
.	 Testing column based modelling
..	 Testing dual variables and slacks reporting
...	 Testing fractional constraints
.	 Testing elastic constraints (no change)
.	 Testing elastic constraints (freebound)
.	 Testing elastic constraints (penalty unchanged)
.	 Testing elastic constraints (penalty unbounded)
.	 Testing zero subtraction
.	 Testing inconsistant lp solution
.	 Testing continuous LP solution
.	 Testing maximize continuous LP solution
.	 Testing unbounded continuous LP solution
.	 Testing Long Names
.	 Testing repeated Names
.	 Testing zero constraint
.	 Testing zero objective
.	 Testing LpVariable (not LpAffineExpression) objective
..	 Testing LpAffineExpression divide
.	 Testing MIP solution
.	 Testing MIP solution with floats in objective
.	 Testing MIP relaxation
.	 Testing feasibility problem (no objective)
.	 Testing an infeasible problem
.	 Testing an integer infeasible problem
.	 Testing column based modelling
.....	 Testing fractional constraints
.	 Testing elastic constraints (no change)
.	 Testing elastic constraints (freebound)
.	 Testing elastic constraints (penalty unchanged)
.	 Testing elastic constraints (penalty unbounded)
..................{'a': 53.0, 'b': 45.3, 'c': 459.2}
..........................
----------------------------------------------------------------------
Ran 99 tests in 24.032s

OK

To define and solve optimization problems with SciPy

In [3]:
from scipy.optimize import linprog
In [4]:
from IPython.display import Image
In [6]:
for url in ("https://bit.ly/3a6qEkq", "https://bit.ly/3krYDsb"):
    display(Image(url=url))
In [13]:
obj = (
    -1,
    -2,
)
lhs_ineq = (
    (2, 1,),
    (-4, 5,),
    (1, -2),
)
rhs_ineq = (
    20,
    10,
    2,
)
lhs_eq = ((-1, 5,),)
rhs_eq = (15,)

The next step is to define the bounds for each variable in the same order as the coefficients. In this case, they’re both between zero and positive infinity

bounds of x

bounds of y

They happen to be the same so create once and multiply by 2.

In [9]:
(bnd := ((0, float("inf"),),) * 2)
Out[9]:
((0, inf), (0, inf))

Optimize and Solve

In [16]:
(opt := linprog(
    c=obj,
    A_ub=lhs_ineq,
    b_ub=rhs_ineq,
    A_eq=lhs_eq,
    b_eq=rhs_eq,
    bounds=bnd,
    method="revised simplex",
))
Out[16]:
     con: array([0.])
     fun: -16.818181818181817
 message: 'Optimization terminated successfully.'
     nit: 3
   slack: array([ 0.        , 18.18181818,  3.36363636])
  status: 0
 success: True
       x: array([7.72727273, 4.54545455])
In [18]:
opt.fun
Out[18]:
-16.818181818181817
In [19]:
opt.x
Out[19]:
array([7.72727273, 4.54545455])

Side bar: YouTube video on how to so