Exercise 2.21

Question

Suppose that Fourier-Motzkin elimination is used in the manner described at the end of Section 2.8 to find the optimal cost in a linear programming problem. Show how this approach can be augmented to obtain an optimal solution as well.

Elu Thingol · Accepted Answer

Consider the problem of minimizing $\mathbf{c}^{\prime} \mathbf{x}$ subject to $\mathbf{x}$ belonging to a polyhedron $P$, i.e., finding the minimum of
$$f:P \mapsto \mathfrak{R}, \quad f(\mathbf{x}) = \mathbf{c}^{\prime} \mathbf{x}.$$
We define a new variable $x_{0}$ and introduce the constraint $x_{0}=\mathbf{c}^{\prime} \mathbf{x}$. This results in a new polyhedron given by
$$\left\{\begin{bmatrix} x_0 \ \mathbf{x} \end{bmatrix} \in \mathfrak{R}^{n+1} \ \left| \ \mathbf{x} \in P,\, \mathbf{c}'\mathbf{x} = x_0 ight.ight\}.$$

At this point we apply the Fourier-Motzkin elimination algorithm $n$ times to eliminate the variables $x_{1}, \ldots, x_{n}$; we are left with the set
$$
Q=\left\{x_{0} \mid 	ext { there exists } \mathbf{x} \in P 	ext { such that } x_{0}=\mathbf{c}^{\prime} \mathbf{x}ight\},
$$
and the optimal cost $c^*$ is equal to the smallest element of $Q$. To get back from the optimal cost to the corresponding optimal solution, we project back into the $n$ dimensions we dismissed earlier
$$f^{-1}\left(c^*ight) = P \cap \{\mathbf{x}\in\mathfrak{R}^n \mid \mathbf{c}^{\prime} \mathbf{x} = c^*\}.$$

Exercise 2.21

Answers

Comments

Exercise 2.21

Answers

Comments

Add answer