Face, dimension, inequality of a polyhedron

Question

I have a polyhedron:

$$\begin{align} P = \{x \in R^3 \;\mid\;& x_1 + 2x_2 \ge 4 \tag1 \\ &2x_1 − x_2 \ge 3 \tag2 \\ &x_2 \ge 1 \tag3 \\ &x_1 + x_3 \ge 4 \tag4 \\ &2x_1 + 2x_2 − x_3 \ge 7 \tag5 \\ &x_1, x_2, x_3 \ge 0 \tag6 \}\end{align}$$

1. Determine the face F induced by $I = \{(3),(4)\}$.
2. Determine an inequality $c x \leq \gamma$, such that $c x \leq \gamma$ is valid for $P$ and $F = \{x \in P \mid c x = b\}$.
3. Determine the dimension of $F$.
4. Prove that inequality (5) is valid but does not define a supporting hyperplane

I have never seen this type of problem so I have no idea how would I need to find the face of this or what does even the polyhedron mean written like this which are edges?

If anyone can help it would be amazing

Answer 1

What you have here is the typical way a polyhedron (or, more generally, a polytope) is described in linear optimization: as intersection of half-spaces.

Each inequation is a half-space. Some will define facets (they are "facet-defining") but some may not, if the intersection of all other half-spaces is already contained in the interior of this half-space.

1. I assume here the question is about the face induced by (3) and (4) considered as equations, i.e. with a "$=$" instead of a "$\lt$". And also that in (3) we have $x_2$, not $x^2$. Then the face is the intersection of two planes, so a line. The part of it included into $P$ may be an edge, or empty, if one of the inequations is not facet-defining. To know that, you have to report $x_2=1$ and $x_1+x_3=4$ in the other inequations, and check if there are solutions. (I have no pen and paper right now, but it seems to be the case).

2. We can assume $c$ is a vector, $\gamma$ a real number, but $b$? In usual linear programming notation (see Wikipedia page linked above), $b$ is the vector of right-hand constants in all inequations; so a $8$-dimension vector (there are $8$ inequations); but that would make $cx=b$ a nonsense. So $b$ is probably a real number. But still the question is clumsy, because there is no quantifier for $b$, and moreover, asking for "$cx\le \gamma$ such that it is valid $\forall x \in P$" would have been sufficient. Anyway, for a given $c$, $\gamma$ has to be the $\max$ of all $b$ such that $F$ is not empty. It can be $\infty$, if the polyhedron is not finite (it may be "open" on one side - I have not checked).

3. F is the intersection of a plane and a polyhedron, so a polygon (which may be infinite if the polyhedron is infinite), or empty. So when not empty, it has dimension $2$.

4. I assume "a supporting hyperplane" means a facet-supporting hyperplane, i.e. the inequation is facet-defining. So the goal is to find a linear combination of inequations $(1)$ to $(4)$, and the $3$ inequations in $(6)$, with positive or null coefficients, that implies inequation $(5)$. However it is not possible: point $(2,1,2)$ verifies all inequations except $(5)$. So there is an error, in the text or in the way I understand it.

Note that, in a typical optimization problem, variables and inequations are counted in thousands, and cases with millions of variables and inequations are not rare. So knowing which inequations are redundant is really a hard problem.