I am quite new to the simplex algorithm, but I have been following the explanation of this excellent video. Unfortunately, I believe that there are some cases not discussed in the video that I'd like to understand. Let me set up the problem: Assume that I have variables $x_1$ and $x_2$ (the actual case I care about is higher-dimensional, but for the ability to visualize, let's keep it 2D), as well as a number of inequalities:
$$ \begin{align} - x_1 \leq 0 \tag{1} \\ - x_2 \leq 0 \tag{2} \\ 0.5x_1 + x_2 \leq 5 \tag{3} \\ x_1 + 0.5x_2 \leq 5 \tag{4} \\ \end{align} $$
The resulting feasible region should look like below:
Let us reformulate that into the equalities via the introduction of slack variables $s_1,\dots,s_4$:
$$ \begin{align} s_1 &= x_1 \tag{5} \\ s_2 &= x_2 \tag{6} \\ s_3 &= 5 - 0.5x_1 - x_2 \tag{7} \\ s_4 &= 5 - x_1 - 0.5x_2 \tag{8} \\ \end{align} $$
Now assume I start from vertex 1 ($0,0$). Plugging this into the equations above yields
$$ \begin{align} s_1 &= 0 \\ s_2 &= 0 \\ s_3 &= 5 \\ s_4 &= 5 \\ \end{align} $$
which means that the inequalities 1 and 2 are tight, whereas 3 and 4 are loose. This makes sense, as vertex 1 lies on inequalities 1 and 2. To find the next vertex, the video now recommends choosing a direction along which to move, say, $x_2$. We find intersections with the loose inequalities for $y=5$ $(s_1 = 0, s_2 = 2.5)$ and $y=10$ $(s_1 = -5, s_2 = 0)$. As slack variables cannot be negative, we must choose $y=5$, and our new vertex is vertex 2 at $(0,5)$. That makes a lot of sense to me. The new slack variables at vertex 2 are:
$$ \begin{align} s_1 &= 0 \\ s_2 &= 5 \\ s_3 &= 0 \\ s_4 &= 2.5 \\ \end{align} $$
so inequalities 1 and 3 are tight, and 2 and 4 are loose. Now I get beyond the video: Assume we want to move in the next direction, say, along $x_2$ to find vertex 3. If I used the same approach of just increasing $x_2$ and keeping $x_1$ fixed, I would actually step off the polytope, so clearly that's not an option. I need to alter $x_1$ and $x_2$ jointly. In 2D, I can imagine that this is possible, as I can find the parallel vector to inequality (3) with some simple algebra.
But this leaves me with a few important questions:
Questions:
- Am I correct in assuming that I seek the next vertex by moving along one of the "tight" inequalities?
- If so, how would I solve that in higher-dimensional half-spaces? (e.g., if an inequality involves $x_1,\dots,x_3$) In such settings, the may no longer be a "unique" vector to move along the inequality. How do we find the correct "direction" then?
We like to use the term "binding" if the constraint is active for a feasible solution within a model such that its corresponding slack value is equal to zero. What the Simplex Method is doing is exchanging basic and non-basic variables in-and-out of the basis to and traversing/exchanging and releasing a constraint to bind to another. It finds this improving direction by calculating the reduced cost of introducing a basic variable into the basis such that a new binding constraint is achieved after releasing one. (Pages $2-3$)
In terms of "correct" direction, is a topic of pivoting rules in which the shortest explanation is: you don't really know which route is the best route, but we know of methods that prevent cycling and methods that reduce CPU runtime; all we know is that there exists an improving direction(s) per pivot, and how we handle the direction(s) determines how fast the problem will solve. Additionally, there might be multiple solutions on a feasible point, thereby making a solution non-unique (point #$4$), or degeneracy.