I have a family of linear programming problems: maximise $c' x$ subject to $A x\le b$, $x\ge0$. The elements of $A$, $b$, and $c$ are nonnegative integers, $c$ strictly positive. ($x$ should also be integral but I will worry about that later.)
It often happens in my application that the coefficients $A$ and $c$ are such that a simplified one-pass algorithm gives the optimal solution for every choice of $b$: the one-pass algorithm determines the elements $x_1,\dots,x_n$ in sequence, choosing each $x_j$ to be the largest possible value consistent with the already-determined values $x_1,\dots,x_{j-1}$. In simplex language, the sequence of entering variables is just $x_1$ to $x_n$, and it terminates after $n$ steps. This saves a lot of time compared to full-on simplex.
This algorithm works when the columns of $A$ and the elements of $c$ have been sorted from "cheap" to "expensive". A "cheap" variable is a column of $A$ with generally small values, for which the corresponding element of $c$ is large: for that element of $x$ you get a lot of output with not very much demand on the constraint $b$. So the algorithm just says "do the easy stuff first."
My question is: what property of $A$ and $c$ would assure us that this simplified algorithm works for all $b$? My initial conjecture was that the nonzero elements of $A$ should be increasing in each row, but that is not correct.
Here are some examples, all with $c=(1,1,1)$: $A_1=\begin{pmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 3 & 2 & 0\end{pmatrix}$, $A_2=\begin{pmatrix} 0 & 0 & 1 \\ 3 & 0 & 2 \\ 0 & 3 & 2 \end{pmatrix}$, $A_3=\begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \end{pmatrix}$, $A_4=\begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}$. For all of these, the sequential algorithm gives the optimal solution for all values of $b$ (by numerical experimentation). $A_3$ is the only one for which all permutations of columns also work. $A_1$ and $A_3$ are especially baffling, since $(1,1,3)$ looks more expensive than $(1,3,0)$ and $(1,1,1)$ more expensive than $(1,0,0)$.
I would be tremendously grateful for any pointers to the literature, for any problems like this, or any suggestions at all. There must have been other cases where some variables can be determined to be "cheaper" than others and can safely be done first. With all the work that has been done on linear programming over the years, it seems that something similar must have come up, but I haven't been able to find it.