Solución de programación lineal en una pasada con variables ordenadas

Tengo una familia de problemas de programación lineal: maximizar sujeto a , . Los elementos de , , y son números enteros no negativos, estrictamente positivo. ( también debería ser integral, pero me preocuparé por eso más adelante).$c' x$$A x\le b$$x\ge0$$A$$b$$c$$c$$x$

A menudo sucede en mi aplicación que los coeficientes y son tales que un algoritmo simplificado de un paso da la solución óptima para cada elección de : el algoritmo de un paso determina los elementos en secuencia, eligiendo cada uno será el mayor valor posible consistente con los valores ya determinados$A$$c$$b$$x_1,\dots,x_n$$x_j$$x_1,\dots,x_{j-1}$. En lenguaje simplex, la secuencia de entrada de variables es solo$x_1$ a $x_n$, y termina después de $n$pasos. Esto ahorra mucho tiempo en comparación con el simplex completo.

Este algoritmo funciona cuando las columnas de $A$ y los elementos de $c$han sido ordenados de "barato" a "caro". Una variable "barata" es una columna de$A$ con valores generalmente pequeños, para los cuales el elemento correspondiente de $c$ es grande: para ese elemento de $x$ obtienes una gran cantidad de producción con poca demanda en la restricción $b$. Entonces el algoritmo solo dice "haz las cosas fáciles primero".

Mi pregunta es: ¿qué propiedad de $A$ y $c$nos aseguraría que este algoritmo simplificado funciona para todos los ? Mi conjetura inicial fue que los elementos distintos de cero de deberían estar aumentando en cada fila, pero eso no es correcto.$b$$A$

Aquí hay algunos ejemplos, todos con : , , , . Para todos estos, el algoritmo secuencial proporciona la solución óptima para todos los valores de (por experimentación numérica). es el único para el que también funcionan todas las permutaciones de columnas.$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}$$b$$A_3$$A_1$$A_3$$(1,1,3)$parece más caro que y más caro que .$(1,3,0)$$(1,1,1)$$(1,0,0)$

Estaría tremendamente agradecido por cualquier sugerencia a la literatura, por cualquier problema como este, o cualquier sugerencia en absoluto. Debe haber otros casos en los que se puede determinar que algunas variables son "más baratas" que otras y se pueden hacer de manera segura primero. Con todo el trabajo que se ha hecho en la programación lineal a lo largo de los años, parece que algo similar debe haber surgido, pero no he podido encontrarlo.

Probablemente el caso más famoso en el que se sabe que un algoritmo codicioso resuelve un LP es para el caso especial del problema de transporte. Hoffman ("En programas lineales simples", en Convexity , vol. 7 de Proceedings of Symposia in Pure Mathematics , páginas 317-327, 1963) demostró que si la matriz de costos para un problema de transporte (maximización) satisface la propiedad Monge ($c_{ij} + c_{kl} \geq c_{il} + c_{kj}$ cuando $1 \leq i < k \leq n$, $1 \leq j < l \leq n$), entonces se puede encontrar una solución óptima de una manera codiciosa como la que usted describe.

Hoffman también tiene un documento de encuesta (" Sobre algoritmos codiciosos que tienen éxito ") de 1985 en el que analiza casos conocidos en los que un algoritmo codicioso da una solución óptima a un LP. Además de su propio trabajo citado anteriormente (sobre el cual dice, "la mayoría de los problemas de programación lineal conocidos [en 1963] por ser susceptibles a un algoritmo codicioso fueron casos especiales de la idea de Monge"), menciona la interpretación de programación lineal de Edmonds generalización de matroides y una discusión del caso cuando$A$ no es negativo, entre otras cosas.

Me imagino que hay resultados más recientes, pero espero que esto al menos parcialmente responda a su pregunta y le dé algunas ideas de dónde buscar.

Gracias a la sugerencia del profesor Spivey, finalmente encontré lo que creo que es el estado del arte: Ulrich Faigle, Alan J. Hoffman y Walter Kern, "Una caracterización de matrices codiciosas de caja no negativas", SIAM J. Disc. Matemáticas. 9 (1996) pp 1-6. Una matriz es "codiciosa" si el algoritmo que describí anteriormente brinda la solución óptima para todos$b$. Una matriz es "codiciosa" si el algoritmo codicioso da la solución óptima con la condición adicional$x\le d$ para todos $b$ y todo $d\ge0$. Claramente, el codicioso de caja es una condición más fuerte que el codicioso.

Siempre asume que $c_1\ge\dots\ge c_n>0$. Faigle, Hoffman y Kern prueban que$A$ es codicioso si y solo si no tiene $k\times(k+1)$ (para cualquier $k$) submatriz del formulario $\begin{pmatrix} r_1 & s_1 & & & \\ r_2 & & s_2 & & \\ \vdots & & & \ddots \\ r_k & & & & s_k \end{pmatrix}$ con cada $r_j>0$ y $\sum_{i:s_i>0} \frac{r_i}{s_i} > 1$. Al extraer las submatrices, se permiten permutaciones arbitrarias de filas pero no columnas, y se permite la subconjunto arbitrario de filas y columnas. Así, en particular, con$k=1$, los elementos distintos de cero en cada fila de $A$ debe ser no decreciente.

Resulta, desafortunadamente, que en mi problema las matrices no son codiciosas, aunque todavía creo que son codiciosas. Por ejemplo, en mi$A_1$por encima de la condición se viola y esta matriz no es codiciosa de caja aunque es codiciosa. Hasta donde yo sé, no hay resultados en la identificación de matrices codiciosas.

El ejemplo más fácil para algo como esto podría ser el problema de la mochila fraccionaria donde los artículos pueden fraccionarse. Este problema (y su lp dual) se puede resolver clasificando los artículos por ganancia por peso, eligiendo la secuencia más larga en este orden que sea factible y fraccionando el último artículo.