Linear programming with scipy

See https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html



In [ ]:

    
import scipy.optimize

Problem examples:

http://people.brunel.ac.uk/~mastjjb/jeb/or/morelp.html

Scipy's syntax

Example for a problem of 2 dimensions:

$$ \begin{align} \min_{x_1,x_2} & \quad \color{\red}{c_1} x_1 + \color{\red}{c_2} x_2 \\ \text{s.t.} & \quad \color{\orange}{A_{1,1}} x_1 + \color{\orange}{A_{1,2}} x_2 \leq \color{\green}{b_1} \\ & \quad \color{\orange}{A_{2,1}} x_1 + \color{\orange}{A_{2,2}} x_2 \leq \color{\green}{b_2} \\ & \quad \color{\purple}{B_{1,1}} \geq x_1 \geq \color{\purple}{B_{1,2}} \\ & \quad \color{\purple}{B_{2,1}} \geq x_2 \geq \color{\purple}{B_{2,2}} \\ \end{align} $$

$$ \color{\red}{ \boldsymbol{c} = \begin{pmatrix} c_1 \\ c_2 \end{pmatrix} } \quad \color{\orange}{ \boldsymbol{A} = \begin{pmatrix} A_{1,1} & A_{1,2} \\ A_{2,1} & A_{2,2} \end{pmatrix} } \quad \color{\green}{ \boldsymbol{b} = \begin{pmatrix} b_1 \\ b_2 \end{pmatrix} } \quad \color{\purple}{ \boldsymbol{B} = \begin{pmatrix} B_{1,1} & B_{1,2} \\ B_{2,1} & B_{2,2} \end{pmatrix} } $$

$$ \text{scipy.optimize.linprog}(\color{\red}{\boldsymbol{c}}, ~ \color{\orange}{\boldsymbol{A}}, ~ \color{\green}{\boldsymbol{b}}, ~ \color{\purple}{\boldsymbol{B}}) $$

Example 1

$$ \begin{align} \min_{x_0,x_1} & \quad -x_0 + 4 x_1 \\ \text{s.t.} & \quad -3 x_0 + x_1 \leq 6 \\ & \quad -x_0 - 2 x_1 \geq -4 \\ & \quad x_1 \geq -3 \end{align} $$



In [ ]:

    
# Coefficients of the linear objective function to be minimized
c = [-1, 4]

# 2-D array which, when matrix-multiplied by x, gives the values of the upper-bound inequality constraints at x.
A = [[-3, 1],
     [ 1, 2]]

# 1-D array of values representing the upper-bound of each inequality constraint (row) in A.
b = [6, 4]

# Sequence of (min, max) pairs for each element in x, defining the bounds on that parameter.
# Use None for one of min or max when there is no bound in that direction.
# By default bounds are (0, None) (non-negative).
# If a sequence containing a single tuple is provided, then min and max will be applied to all variables in the problem.
x0_bounds = (None, None)
x1_bounds = (-3, None)
bounds = (x0_bounds,x1_bounds)

scipy.optimize.linprog(c, A_ub=A, b_ub=b, bounds=bounds)

The carpenter problem



In [ ]:

    
# Coefficients of the linear objective function to be minimized
c = np.array([3, 5])

# 2-D array which, when matrix-multiplied by x, gives the values of the upper-bound inequality constraints at x.
A_ub = np.array([[3, 2],
                 [1, 2],
                 [5, 4]])

# 1-D array of values representing the upper-bound of each inequality constraint (row) in A_ub.
b_ub = np.array([700, 500, 1500])

# Sequence of (min, max) pairs for each element in x, defining the bounds on that parameter.
# Use None for one of min or max when there is no bound in that direction.
# By default bounds are (0, None) (non-negative).
# If a sequence containing a single tuple is provided, then min and max will be applied to all variables in the problem.
bounds = ((0, None), (0, None))

scipy.optimize.linprog(-c, A_ub=A_ub, b_ub=b_ub, bounds=bounds)

The optimal solution is obtain for $x_1=100$ and $x_2=200$ with a gain of 1300.