Linear programming solution in one pass with ordered variables I have a family of linear programming problems:  maximise $c&#39; 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 &amp; 1 &amp; 1 \\ 1 &amp; 2 &amp; 3 \\ 3 &amp; 2 &amp; 0\end{pmatrix}$,
$A_2=\begin{pmatrix} 0 &amp; 0 &amp; 1 \\ 3 &amp; 0 &amp; 2 \\ 0 &amp; 3 &amp; 2 \end{pmatrix}$,
$A_3=\begin{pmatrix} 1 &amp; 1 &amp; 1 \\ 1 &amp; 0 &amp; 0 \\ 1 &amp; 0 &amp; 1 \end{pmatrix}$,
$A_4=\begin{pmatrix} 1 &amp; 0 &amp; 1 \\ 0 &amp; 1 &amp; 0 \\ 0 &amp; 1 &amp; 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.
Probably the most famous instance in which a greedy algorithm is known to solve an LP is for the special case of the transportation problem.  Hoffman ("On simple linear programs", in Convexity, vol. 7 of Proceedings of Symposia in Pure Mathematics, pages 317-327, 1963) proved that if the cost matrix for a (maximization) transportation problem satisfies the Monge property ($c_{ij} + c_{kl} \geq c_{il} + c_{kj}$ when $1 \leq i &lt; k \leq n$, $1 \leq j &lt; l \leq n$) then an optimal solution can be found in a greedy manner like the one you describe.  

Hoffman also has a survey paper ("On greedy algorithms that succeed") from 1985 in which he discusses known cases in which a greedy algorithm gives an optimal solution to an LP.  Besides his own work cited above (about which he says, "most of the linear programming problems known [by 1963] to be susceptible to a greedy algorithm were special cases of the Monge idea"), he mentions Edmonds' linear programming interpretation of a generalization of matroids and a discussion of the case when $A$ is nonnegative, among other things.

I imagine there are more recent results, but hopefully this at least partially answers your question and gives you some ideas of where else to look.