Given the following open example polyhedron:
\begin{equation} \begin{aligned} x_1 & -x_2 & -s & \le 0 \\ x_1 & +x_2 & & \le 3 \\ x_1 & & & \ge 1 \\ & \;\;\;\; x_2 & & \ge 0 \\ & & s & \ge 0 \end{aligned} \tag{1} \end{equation}
I'd like to find the maximal value of a variable $s$ that occurs in an extreme point of the polyhedron, although $s$ itself is unbounded. In the example case, the solution would be $s=3$, according to the extreme point $[x_1=3,\; x_2=0,\; s=3]$. ($[3,0,3]$ see plot 1).
Is there a generic way to (ideally through a single LP) identify such maximum values s.t. them being located at extreme points?
I see that you could enumerate all extreme points or basic feasible solutions (BFS) and posteriorly select the one with the largest $s$ because this is what I did in the example. This would be the brute-force approach. Maybe it would also be possible follow the "top, but not unbounded edges" of the polyhedron in a Simplex-way. But an elegant way to formulate a single LP for this would make my life much easier. MILP would not be ideal, because as opposed to the example, the original problem has several thousand constraints.
Context:
Later on, I could crop the polyhedron with $s\le3$ (plot 2) and ultimately use it as a part of a larger MILP in a big-M manner to control the constraint (2).
\begin{equation} \begin{aligned} x_1 & -x_2 & -z\,M & \le 0 \\ x_1 & +x_2 & & \le 3 \\ x_1 & & & \ge 1 \\ & \;\;\;\; x_2 & & \ge 0 \\ & & z \in \{0,1\} \end{aligned} \tag{2} \end{equation}
The binary variable $z$ will then also depend on constraints outside this scope. The parent problem has hundreds of other binary variables and runtimes of several hours. With randomly large $M$, I encounter problems like trickle flow. I know, textbooks advise against big-M whenever possible. In my case it's not possible to do otherwise, as I'm bound to certain tools.
Update (2021/02/18):
The face perpendicular to the direction of unboundedness is of course $s\le 3$
The face that bounds the polyhedron in the top corner points and maintains the full combinatoric potential is $-2x_1 + x_2 +2s\le 0$ (or any scaled version of this constraint).
Is it easy to find such a facet in higher dimensions? Is it possible without determining all corner points?
This is a fun question! I'm not sure if there's a single linear program that answers your question, but interestingly it appears to be possible to use the simplex method on the original problem to answer your question.
Namely, you can set $\max s$ as your objective function, and then keep pivoting on the resulting simplex table for as long as you can until absolutely no more pivots are possible: this happens exactly when every column with strictly negative reduced costs has all values negative or zero. In this case, you've found the desired maximal value. This is because there are no more pivots that increase the value of the objective function which can reach another basic feasible solution.
Here's my solution on your problem. An initial table (with $X_1=x_1-1$ and slack variables $t_1$ and $t_2$) representing the linear program is:
\begin{equation} \begin{array}{r|rrrrr|r} T_0 & X_1 & x_2 & s & t_1 & t_2 & \\ \hline z & 0 & 0 & -1 & 0 & 0 & 0 \\ \hline ? & 1 & -1 & -1 & 1 & 0 & -1 \\ ? & 1 & 1 & 0 & 0 & 1 & 2 \end{array} \end{equation} Note that I don't have a feasible basis in this table. However, it's clear I can flip the sign of the first row, and then that gives me an initial feasible starting basis (alternatively, you could use the 2-phase method, although that's much slower): \begin{equation} \begin{array}{r|rrrrr|r} T_1 & X_1 & x_2 & s & t_1 & t_2 & \\ \hline z & -1 & 1 & 0 & -1 & 0 & 1 \\ \hline s & -1 & 1 & 1 & -1 & 0 & 1 \\ t_2 & 1 & 1 & 0 & 0 & 1 & 2 \end{array} \end{equation} Now, the only possible pivot is on column $X_1$ and row $t_2$: \begin{equation} \begin{array}{r|rrrrr|r} T_2 & X_1 & x_2 & s & t_1 & t_2 & \\ \hline z & 0 & 2 & 0 & -1 & 1 & 3 \\ \hline s & 0 & 2 & 1 & -1 & 1 & 3 \\ X_1 & 1 & 1 & 0 & 0 & 1 & 2 \end{array} \end{equation} We can see that the problem is unbounded since there is a column with negative reduced cost and no strictly positive entries above it (column $t_2$). Since there are no other columns with strictly negative reduced cost, no further pivots are possible that would increase the value of the objective function. We've found our solution: $s=3$, $X_1=2$ (so $x_1=X_1+1=3$), and $x_2=0$.