Solving LP problems using Fourier-Motzkin elimination method

Fourier-Motzkin elimination can actually be used to solve a linear programming problem. We illustrate the process with an example.

Let \((LP)\) denote the linear programming problem \[ \begin{array}{rl} \min & x + y \\ \text{s.t.} & x + 2y \geq 2 \\ & 3x + 2y \geq 6. \end{array} \] Observe that \((LP)\) is equivalent to \[ \begin{array}{rl} \min & z \\ (LP')~~~~\text{s.t.} & z - x - y = 0 \\ & x + 2y \geq 2 \\ & 3x + 2y \geq 6. \end{array} \] Note that the objective function is replaced with \(z\) and \(z\) is set to the original objective function in the first constraint of \((LP')\) since \(z = x+ y\) if and only if \(z-x-y=0\). Then, solving \((LP')\) is equivalent to finding among all the solutions to the following system a solution that minimizes \(z\), if it exists. \[ \begin{array}{rl} z - x - y \geq 0 & ~~~(1) \\ -z + x + y \geq 0 & ~~~(2) \\ x + 2y \geq 2 &~~~(3)\\ 3x + 2y \geq 6 & ~~~(4) \end{array} \] Since we are interested in the minimum possible value for \(z\), we use Fourier-Motzking elimination to eliminate the variables \(x\) and \(y\).

To eliminate \(x\), we first multiply \((4)\) by \(\frac{1}{3}\) to obtain \[ \begin{array}{rl} z - x - y \geq 0 & ~~~(1) \\ -z + x + y \geq 0 & ~~~(2) \\ x + 2y \geq 2 &~~~(3)\\ x + \frac{2}{3}y \geq 2 & ~~~(5) \end{array} \] Then eliminate \(x\) to obtain \[ \begin{array}{rrl} (1) + (2): & 0 \geq 0 \\ (1) + (3): & z + y \geq 2 & ~~~(6) \\ (1) + (5): & z - \frac{1}{3} y \geq 2 & ~~~(7) \\ \end{array} \] Note that there is no need to keep the first inequality. To eliminate \(y\), we first multiply \((7)\) by \(3\) to obtain \[ \begin{array}{rl} z + y \geq 2 & ~~~(6) \\ 3z - y \geq 6 & ~~~(8) \\ \end{array} \] Then eliminate \(y\) to obtain \[ \begin{array}{rl} 4z \geq 8 & ~~~(9) \\ \end{array} \] Multiplying \((9)\) by \(\frac{1}{4}\) gives \(z \geq 2\). Hence, the minimum possible value for \(z\) among all the solutions to the system is \(2\). So the optimal value of \((LP')\) is \(2\). To obtain an optimal solution, set \(z = 2\). Then we have no choice but to set \(y = 0\) and \(x = 2\). One can check that \((x,y) = (2,0)\) is a feasible solution with objective function value \(2\).

We can obtain an independent proof that the optimal value is indeed \(2\) if we trace back the computations. Note that the inequality \(z \geq 2\) is given by \begin{eqnarray*} \frac{1}{4} (9) & \Leftarrow & \frac{1}{4} (6) + \frac{1}{4} (8) \\ & \Leftarrow & \frac{1}{4} (1)+\frac{1}{4}(3) + \frac{3}{4}(7) \\ & \Leftarrow & \frac{1}{4} (1)+\frac{1}{4}(3) + \frac{3}{4}(1)+\frac{3}{4}(5) \\ & \Leftarrow & (1)+ \frac{1}{4}(3) + \frac{1}{4} (4) \\ \end{eqnarray*} This shows that \(\frac{1}{4}(3) + \frac{1}{4} (4)\) gives the inequality \(x+y \geq 2\). Hence, no feasible solution to \((LP)\) can have objective function value less than \(2\). But we have found one feasible solution with objective function value \(2\). Hence, \(2\) is the optimal value.

Worked examples

1. Determine the optimal value of the following linear programming problem: \[ \begin{array}{rl} \min & x \\ \text{s.t.} & x + y \geq 2 \\ & x - 2y + z \geq 0 \\ & y - 2z \geq -1. \end{array} \]

   The problem is equivalent to determining the minimum value for \(x\) among all \(x,y,z\) satisfying \[ \begin{array}{r} x + y \geq 2 ~~~~~~(1)\\ x - 2y + z \geq 0~~~~~~(2) \\ y - 2z \geq -1.~~~~(3) \end{array} \]

   We use Fourier-Motzkin Elimination Method to eliminate \(z\). Multiplying \((3)\) by \(\frac{1}{2}\), we get \[ \begin{array}{r} x + y \geq 2 ~~~~~~(1)\\ x - 2y + z \geq 0~~~~~~(2) \\ \frac{1}{2}y - z \geq -\frac{1}{2}.~~~~(4) \end{array} \] Eliminating \(z\), we obtain \[ \begin{array}{r} x + y \geq 2 ~~~~~~(1)\\ x - \frac{3}{2}y \geq -\frac{1}{2}~~~~~~(5) \\ \end{array} \] where \((5)\) is given by \((2) + (4)\).

   Multiplying \((5)\) by \(\frac{2}{3}\), we get \[ \begin{array}{r} x + y \geq 2 ~~~~~~(1)\\ \frac{2}{3} x - y \geq -\frac{1}{3}~~~~~~(6) \\ \end{array} \] Eliminating \(y\), we get \[ \begin{array}{r} \frac{5}{3} x \geq \frac{5}{3} ~~~~~~(7)\\ \end{array} \] where \((7)\) is given by \((1) + (6)\). Multiplying \((7)\) by \(\frac{3}{5}\), we obtain \(x \geq 1\). Hence, the minimum possible value for \(x\) is \(1\).

   Note that setting \(x = 1\), the system \((1)\) and \((6)\) forces \(y = 1\). And \((2)\) and \((3)\) together force \(z = 1\). One can check that \((x,y,z) = (1,1,1)\) is a feasible solution.

   Remark. Note that the inequality \(x \geq 1\) is given by \begin{eqnarray*} \frac{3}{5} (7) & \Leftarrow & \frac{3}{5} (1) + \frac{3}{5} (6) \\ & \Leftarrow & \frac{3}{5} (1) + \frac{2}{5} (5) \\ & \Leftarrow & \frac{3}{5} (1) + \frac{2}{5} (2) + \frac{2}{5} (4) \\ & \Leftarrow & \frac{3}{5} (1) + \frac{2}{5} (2) + \frac{1}{5} (3) \end{eqnarray*}

2. Determine if the following linear programming problem has an optimal solution: \[ \begin{array}{rl} \min & x_1 + 2x_2 \\ \text{s.t.} & x_1 + 3x_2 \geq 4 \\ & -x_1 + x_2 \geq 0. \end{array} \]

   It suffices to determine if there exists a minimum value for \(z\) among all the solutions to the system \[ \begin{array}{rl} z- x_1 - 2x_2 \geq 0 & ~~~(1) \\ -z+ x_1 + 2x_2 \geq 0 & ~~~(2)\\ x_1 + 3x_2 \geq 4 & ~~~(3)\\ -x_1 + x_2 \geq 0 & ~~~(4) \end{array} \] Using Fourier-Motzkin elimination to eliminate \(x_1\), we obtain: \[ \begin{array}{rrl} (1) + (2): & 0 \geq 0 \\ (1) + (3): & z + x_2 \geq 4 & ~~~(5)\\ (2) + (4): & - z + 3x_2 \geq 0 & ~~~(6) \\ (3) + (4): & 4x_2 \geq 4 & ~~~(7) \end{array} \] Note that all the coefficients of \(x_2\) is nonnegative. Hence, eliminating \(x_2\) will result in a system with no constraints. Therefore, there is no lower bound on the value of \(z\). In particular, if \(z = t\) for \(t\leq 0\), then from \((5)\),\((6)\),\((7)\), we need \(x_2 \geq 4-t\), \(3x_2 \geq t\), and \(x_2 \geq 1\). Hence, we can set \(x_2 = 4-t\).

   Since we require that \(z - x_1 - 2x_2 = 0\), we get that \(t - x_1 - 2(4-t) = 0\). Thus, we have to set \(x_1 = -8+3t\).

   Hence, \(x_1 = -8+3t\) and \(x_2 = 4-t\) together give a feasible solution for all \(t \leq 0\) with objective function value that approaches \(-\infty\) as \(t \rightarrow -\infty\). Hence, the linear programming problem is unbounded.

3. Determine all values of \(a\) such that the problem \[ \begin{array}{rl} \min & x + y \\ \text{s.t.} & -3x + y \geq a \\ & 2x - y \geq 0 \\ & x + 2y \geq 2 \end{array} \] is infeasible.

   Adding the first two inequalities gives \(-x \geq a\). Adding \(2\) times the second inequality and the third inequality gives \(5x \geq 2\), implying that \(x \geq \frac{2}{5}\). Hence, if \(a \gt -\frac{2}{5}\), there is no solution.

   Note that if \(a \leq -\frac{2}{5}\), then \((x,y) = \left (\frac{2}{5}, \frac{4}{5}\right)\) satisfies all the inequalities. Hence, the problem is infeasible if and only if \(a \gt -\frac{2}{5}\).