Use SciPy Library in Python to Solve Linear Programming Problems

Posted on Views: Word count in article: 340 Reading time ≈ 1 mins.

scipy.optimize

SciPy provides functions for minimizing (or maximizing) objective functions, possibly subject to constraints. It includes solvers for nonlinear problems (with support for both local and global optimization algorithms), linear programming, constrained and nonlinear least-squares, root finding, and curve fitting.

This is the official manual of scipy.optimize: Optimization and root finding (scipy.optimize) — SciPy v1.13.0 Manual

scipy.optimize.linprog is used here to solve the linear programming problem. More information about scipy.optimize.linprog: scipy.optimize.linprog — SciPy v1.13.0 Manual

Note:

  • Before calling scipy.optimize.linprog, the maximization problem needs to be converted into a minimization problem.

  • The sign of the inequality constraint needs to be converted to less than or equal to.

Install the SciPy Library

Install the SciPy library in Python:

1
pip install scipy

Example

Max:2x1+6x2+10x3Max:2x_1+6x_2+10x_3

S.T. :

2x1+x2−2x3<=50x1−5x2<=20x2+2x3=102x_1+x_2-2x_3<=50\\ x_1-5x_2<=20\\ x_2+2x_3=10

Bounds:

x1<=500<=x20<=x3x_1<=50\\0<=x_2\\0<=x_3

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from scipy.optimize import linprog

# Coefficients of the objective function
c = [-2, -6, -10]

# Coefficients to the left of the inequality constraints
A_ub = [[2, 1, -2], [1, -5, 0]]

# Coefficients to the right of the inequality constraints
b_ub = [50, 20]

# Coefficients to the left of the equality constraints
A_eq = [[0, 1, 2]]

# Coefficients to the right of the equality constraints
b_eq = [10]

# Bounds on the decision variables
x1_bounds = (None, 50)
x2_bounds = (0, None)
x3_bounds = (0, None)

# Solve the linear programming problem
result = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=[x1_bounds, x2_bounds, x3_bounds],
                 method='highs')
print(result)

Results

The output of the program is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
       message: Optimization terminated successfully. (HiGHS Status 7: Optimal)
       success: True
        status: 0
           fun: -108.33333333333333
             x: [ 2.833e+01  1.667e+00  4.167e+00]
           nit: 2
         lower:  residual: [       inf  1.667e+00  4.167e+00]
                marginals: [ 0.000e+00  0.000e+00  0.000e+00]
         upper:  residual: [ 2.167e+01        inf        inf]
                marginals: [ 0.000e+00  0.000e+00  0.000e+00]
         eqlin:  residual: [ 0.000e+00]
                marginals: [-5.917e+00]
       ineqlin:  residual: [ 0.000e+00  0.000e+00]
                marginals: [-9.167e-01 -1.667e-01]
mip_node_count: 0
mip_dual_bound: 0.0
       mip_gap: 0.0