Scipy

The main method to solve linear programming problem in python is given by the following command

scipy.optimize.linprog(c, 
                       A_ub=None, 
                       b_ub=None, 
                       A_eq=None, 
                       b_eq=None, 
                       bounds=None, 
                       method='revised simplex', 
                       callback=None, 
                       options=None, 
                       x0=None)

Where the value of each argument is given by comparing the linear programming with the following linear programn

\[ \begin{alignat*}{2} & \text{minimize: } && c^T x \\ & \text{subject to: } && \begin{aligned}[t] A_{ub}x &\leq b_{ub} \\ A_{eq}x &= b_{eq} \\ l\leq x &\leq u \end{aligned} \end{alignat*} \]

Example¶

c = [-1, 4]
A = [[-3, 1], 
     [1, 2]]
b = [6, 4]
x0_bounds = (None, None)
x1_bounds = (-3, None)

res = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds], method='simplex')

       message: The problem is unbounded. (HiGHS Status 10: model_status is Unbounded; primal_status is At upper bound)
       success: False
        status: 3
           fun: None
             x: None
           nit: 3
         lower:  residual: None
                marginals: None
         upper:  residual: None
                marginals: None
         eqlin:  residual: None
                marginals: None
       ineqlin:  residual: None
                marginals: None

1. Example 1.a¶

Now let's try to solve the following problem from the assignment

\[\begin{alignat*}{2} & \text{minimize: } && x_1 - 2x_2 - 4x_3 + 2x_4 \\ & \text{subject to: } && \begin{aligned}[t] x_1 - 2x_3 &\leq 4 \\ x_2 - x_4 &\leq 8 \\ -2x_1 + x_2 + 8x_3 + x_4 &\leq 12 \\ x_1,x_2,x_3,x_4 &\geq 0 \end{aligned} \end{alignat*}\]

We have to use the following command to solve this problem

        message: Optimization terminated successfully. (HiGHS Status 7: Optimal)
        success: True
         status: 0
            fun: -18.0
              x: [ 0.000e+00  8.000e+00  5.000e-01  0.000e+00]
            nit: 4
          lower:  residual: [ 0.000e+00  8.000e+00  5.000e-01  0.000e+00]
                 marginals: [ 0.000e+00  0.000e+00  0.000e+00  1.000e+00]
          upper:  residual: [       inf        inf        inf        inf]
                 marginals: [ 0.000e+00  0.000e+00  0.000e+00  0.000e+00]
          eqlin:  residual: []
                 marginals: []
        ineqlin:  residual: [ 5.000e+00  0.000e+00  0.000e+00]
                 marginals: [-0.000e+00 -1.500e+00 -5.000e-01]
 mip_node_count: 0
 mip_dual_bound: 0.0
        mip_gap: 0.0

We can use a small function to extract the important information and print in a line as follows.

The value of optimal is \(-18\) at \((0,8,1/2,0)\)

2. Example 1.b¶

We can solve the second assignment

\[\begin{alignat*}{2} & \text{minimize: } && 2x-y+2z \\ & \text{subject to: } && \begin{aligned}[t] 2x + y &\leq 10 \\ x+2y-2z &\leq 20 \\ y+2z &\leq 5 \\ x,y,z &\geq 0 \end{aligned} \end{alignat*}\]

The value of optimal is \(-5\) at \((0,5,0)\)

3. Example 1.c¶

We can solve the second assignment

\[\begin{alignat*}{2} & \text{maximize: } && x_1 + 2x_2 + 2x_3, \\ & \text{subject to: } && \begin{aligned}[t] 5x_1 + 2x_2 + 3x_3 &\leq 15 \\ x_1 + 4x_2 + 2x_3 &\leq 12 \\ 2x_1 + x_3 &\leq 8 \\ x_1,x_2,x_3 &\geq 0 \end{aligned} \end{alignat*}\]

The value of optimal is \(21/2\) at \((0,3/4,9/2)\)

4. Example 2.a¶

We can solve the second assignment

\[\begin{alignat*}{2} & \text{maximize: } && 3x_1 - x_2 \\ & \text{subject to: } && \begin{aligned}[t] 2x_1 + x_2 &\geq 2 \\ x_1 + 3x_2 &\leq 2 \\ x_2 &\leq 4 \\ x_1,x_2 &\geq 0 \end{aligned} \end{alignat*}\]

The value of optimal is \(6\) at \((2,0)\)

5. Example 5.a¶

We can solve the second assignment

\[\begin{alignat*}{2} & \text{maximize: } && 2x+4y \\ & \text{subject to: } && \begin{aligned}[t] x + 2y &\leq 5 \\ x + y &\leq 4 \\ x, y &\geq 0 \end{aligned} \end{alignat*}\]

The value of optimal is \(10\) at \((0,5/2)\)

6. Example 4¶

Consider the following linear programming problem

\[\begin{alignat*}{2} & \text{maximize: } && 3x+2y \\ & \text{subject to: } && \begin{aligned}[t] 4x - y &\leq 4 \\ 4x +3y &\leq 6 \\ 4x + y &\leq 4 \\ x, y &\geq 0 \end{aligned} \end{alignat*}\]

The value of optimal is \(17/4\) at \((6755399441055743/9007199254740992,4503599627370497/4503599627370496)\)

7. Example 6.b¶

Show that the following problem has unbounded objective

\[\begin{alignat*}{2} & \text{maximize: } && 20x_1 + 5x_2 + x_3 \\ & \text{subject to: } && \begin{aligned}[t] 3x_1 + 5x_2 - 5x_3 &\leq 50 \\ x_1 + 3x_2 - 4x_3 &\leq 20 \\ x_1 &\leq 10 \\ x_1, x_2, x_3 &\geq 0 \end{aligned} \end{alignat*}\]

'The problem is unbounded. (HiGHS Status 10: model_status is Unbounded; primal_status is At upper bound)'

8. Example 3.b¶

Consider the following problem, in the phase I, the artificial variable didn't leave but assumes the value \(0\), hence we can remove it and continue with phase II

\[\begin{alignat*}{2} & \text{maximize: } && 2x_1 + 2x_2 + 4 x_3 \\ & \text{subject to: } && \begin{aligned}[t] 2x_1 + x_2 + x_3 &\leq 2 \\ 3x_1 + 4x_2 + 2x_3 &\geq 8 \\ x_1, x_2, x_3 &\geq 0 \end{aligned} \end{alignat*}\]

The value of optimal is \(4\) at \((0,2,0)\)

Last modified on: 2023-01-06 22:22:45