Solving Linear Problems

Solving linear problems is easier with SciPy. It includes the function linprog (from linear programming) that allows us to solve any linear optimization problem. In this lesson, we’re going to learn how to use this special feature of SciPy.

First linear optimization problem

The best way to learn is with a practical example, so let’s solve the following linear optimization problem:

$$\min_{x, y} 4x + 3y + 1\\ s.t.: x + y < 10\\ x > 5\\$$

Note: The last term of the target function is a constant. This constant doesn’t affect the optimization problem. This means that removing it doesn’t modify the optimal value. The minimum of $4x + 3y$ is the same as the minimum of $4x + 3y + 1$.

The first step is to transform it into the form we learned earlier. Note that the second constraint has a $>$ sign instead of a $<$ sign. We need to change this to use linprog from SciPy since this function only accepts the less than or equal to ($≤$) constraints. This change is done by multiplying the constraint by $-1$.

$$\min_{x, y} 4x + 3y + 1\\ s.t.: x + y < 10\\ -x < -5\\$$

The second step is to define the problem using matrix notation. Here we have a problem. The one that we sum in the target function is just a scalar and it doesn’t multiply any variable. How do we write the target function as $\mathbf{c}\mathbf{x}^\top$ then? For that, we’ll add an artificial variable and constrain it to always be one.

$$\min_{x, y} 4x + 3y + 1b\\ s.t.: x + y < 10\\ -x < -5\\ b = 1$$

Now $b$ is an additional variable but it’s always one. To write the problem in matrix notation, we have $\mathbf{a} = (4, 3, 1)$, $\mathbf{x} = (x, y, b)$, $\mathbf{p} = (10, -5)$, and $\mathbf{q} = (1)$. We also have $Q =(\begin{smallmatrix} 0 & 0 & 1 \end{smallmatrix})$ and $P = \big(\begin{smallmatrix}1 & 1 & 0\\ -1 & 0 & 0\end{smallmatrix}\big)$. Remember we added a new variable and that’s why we have three columns in the matrices.