So I was playing around with the simplex method and basically I was interested in solving the problem "find the second most optimal vertex" for maximizing a given objective function, to be concrete:
$$ \max c^T x $$
$$ Ax \le b$$
Where we assume the result is not infeasible/not-empty and also not unbounded.
So I have a somewhat inefficient way of doing this. I can
Run an algorithm of my choice (such as the simplex method) to identify the optimal extreme point for maximizing $c^Tx$
Now that I have this point $p$, I find which inequalities in $Ax \le b$ are tight for the point
Now that I know which inequalities are tight for the point (I'll have $n$ or more such inequalities) I can try every combination of $(n-1)$ inequalities from the tight set with one other inequality from the larger set and check
- if the resulting point is feasible,
- if it is feasible then calculate its objective and store these in a list $L$
With that list $L$ we find the point with largest objective value that isn't the first extreme point $p$.
So this awful strategy takes $O(\text{LP run time}) + nmO(\text{LP run time})$ to run.
Where $n$ is the dimension of the problem i.e. number of columns in $A$ (or said geometrically the dimension of the ambient space of our polytope) and $m$ is the number of inequalities i.e. number of rows in $A$ (or said geometrically the number facets of our polytope).
I get the feeling that this procedure is kind of stupid and there should be a way to slightly modify the simplex method to basically find the extreme point and then do just one extra step to pivot to the 2nd from best extreme point. I am not sure what that procedure should be since the simplex method pivots on a per variable basis and doesn't let you directly say "take me to the vertex whose objective value is NEXT best".