Linear programming solution in one pass with ordered variables

Question

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.

Answer 1

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 < k \leq n$, $1 \leq j < 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.

Answer 2

Thanks to Prof Spivey's suggestion, I finally located what I think is the state of the art: Ulrich Faigle, Alan J. Hoffman, and Walter Kern, "A Characterization of Nonnegative Box-Greedy Matrices", SIAM J. Disc. Math. 9 (1996) pp 1-6. A matrix is "greedy" if the algorithm I described above gives the optimal solution for all $b$. A matrix is "box-greedy" if the greedy algorithm gives the optimal solution with the additional condition $x\le d$ for all $b$ and all $d\ge0$. Clearly, box-greedy is a stronger condition than greedy.

Always assume that $c_1\ge\dots\ge c_n>0$. Faigle, Hoffman, and Kern prove that $A$ is box greedy if and only if it has no $k\times(k+1)$ (for any $k$) submatrix of the form $\begin{pmatrix} r_1 & s_1 & & & \\ r_2 & & s_2 & & \\ \vdots & & & \ddots \\ r_k & & & & s_k \end{pmatrix}$ with each $r_j>0$ and $\sum_{i:s_i>0} \frac{r_i}{s_i} > 1$. In extracting the submatrices, arbitrary permutations of rows are allowed but not columns, and arbitrary subsetting of rows and columns is allowed. Thus in particular, with $k=1$, the nonzero elements in each row of $A$ must be nondecreasing.

It turns out, unfortunately, that in my problem the matrices are no box-greedy though I still believe they are greedy. For example, in my $A_1$ above the condition is violated and this matrix is not box-greedy though it is greedy. As far as I know, there are no results on identifying greedy matrices.

Answer 3

The easiest example for something like this might be the fractional knapsack problem where items are permitted to be fractionalized. this problem (and its lp dual) can be solved by sorting the items for profit per weight, choosing the longest sequence in this order which is feasible and fractionalizing the last item.