Solução de programação linear em uma passagem com variáveis ​​ordenadas

Eu tenho uma família de problemas de programação linear: maximize $c' x$ sujeito a $A x\le b$ , $x\ge0$ . Os elementos de , , e são números inteiros não negativos, estritamente positivo. ( também deve ser integral, mas vou me preocupar com isso mais tarde.)b c c $A$$b$$c$$c$$x$

Geralmente, em minha aplicação, os coeficientes e são tais que um algoritmo simplificado de uma passagem fornece a solução ideal para todas as opções de : o algoritmo de uma passagem determina os elementos em seqüência, escolhendo cada é o maior valor possível consistente com os valores já determinados . Na linguagem simplex, a sequência de entrada de variáveis ​​é apenas a e termina após etapas. Isso economiza muito tempo em comparação com o simplex completo.c b x 1 , … , x n x j x 1 , … , x j - 1 x 1 x n$A$$c$$b$$x_1,\dots,x_n$$x_j$$x_1,\dots,x_{j-1}$$x_1$$x_n$$n$

Esse algoritmo funciona quando as colunas de e os elementos de foram classificados de "barato" para "caro". Uma variável "barata" é uma coluna de com valores geralmente pequenos, para os quais o elemento correspondente de é grande: para esse elemento de você obtém muita saída com pouca demanda na restrição . Portanto, o algoritmo diz apenas "faça as coisas fáceis primeiro".c A c x $A$$c$$A$$c$$x$$b$

Minha pergunta é: que propriedade de e nos garantiria que esse algoritmo simplificado funciona para todos os ? Minha conjectura inicial era que os elementos diferentes de zero de deveriam aumentar em cada linha, mas isso não está correto.c b $A$$c$$b$$A$

Aqui estão alguns exemplos, todos com : , , , . Para tudo isso, o algoritmo seqüencial fornece a solução ideal para todos os valores de (por experimentação numérica). é o único para o qual todas as permutações de colunas também funcionam.A 1 = ( 1 1 1 1 2 3 3 2 0 ) A 2 = ( 0 0 1 3 0 2 0 3 2 ) A 3 = ( 1 1 1 1 0 0 1 1 1 ) A 4 = ( 1 0 1 0 1 $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 mais caro que e mais caro que .$(1,3,0)$$(1,1,1)$$(1,0,0)$

Eu ficaria tremendamente grato por qualquer indicação na literatura, por quaisquer problemas como esse ou quaisquer sugestões. Deve ter havido outros casos em que algumas variáveis ​​podem ser determinadas como "mais baratas" do que outras e podem ser feitas primeiro com segurança. Com todo o trabalho realizado na programação linear ao longo dos anos, parece que algo semelhante deve ter surgido, mas não consegui encontrá-lo.

Provavelmente, o exemplo mais famoso em que um algoritmo ganancioso é conhecido por resolver um LP é o caso especial do problema de transporte. Hoffman ("Em programas lineares simples", em Convexity , vol. 7 de Proceedings of Symposia in Pure Mathematics , páginas 317-327, 1963) provou que se a matriz de custos para um problema de transporte (maximização) satisfaz a propriedade Monge ( quando 1 ≤ i < k ≤ n , 1 ≤ $c_{ij} + c_{kl} \geq c_{il} + c_{kj}$$1 \leq i < k \leq n$ ), então uma solução ideal pode ser encontrada de maneira gananciosa como a que você descreve. $1 \leq j < l \leq n$

Hoffman também tem um artigo de pesquisa (" Sobre algoritmos gananciosos que obtêm sucesso ") de 1985, no qual discute casos conhecidos nos quais um algoritmo ganancioso fornece uma solução ideal para um LP. Além de seu próprio trabalho citado acima (sobre o qual ele diz, "a maioria dos problemas de programação linear conhecidos [em 1963] por serem suscetíveis a um algoritmo ganancioso eram casos especiais da idéia de Monge"), ele menciona a interpretação de programação linear de Edmonds sobre um generalização de matróides e uma discussão do caso em que não é negativo, entre outras coisas.$A$

Imagino que haja resultados mais recentes, mas espero que isso responda pelo menos parcialmente à sua pergunta e lhe dê algumas idéias de onde mais procurar.

Graças à sugestão do professor Spivey, finalmente localizei o que considero o estado da arte: Ulrich Faigle, Alan J. Hoffman e Walter Kern, "Uma Caracterização de Matrizes Não-Negativas Box-Greedy", SIAM J. Disc. Matemática. 9 (1996) pp 1-6. Uma matriz é "gananciosa" se o algoritmo que descrevi acima fornecer a solução ideal para todos os . Uma matriz é "gananciosa em caixa" se o algoritmo ganancioso fornecer a solução ideal com a condição adicional x ≤ d para todos os b e todos d ≥ 0 . Claramente, a caixa gananciosa é uma condição mais forte que a gananciosa.$b$$x\le d$$b$$d\ge0$

Sempre assuma que . Faigle, Hoffman e Kern provam que A é caixa gananciosa se, e somente se, não tiver submatriz k × ( k + 1 ) (para qualquer k ) da forma ( r 1 s $c_1\ge\dots\ge c_n>0$$A$$k\times(k+1)$$k$com cadarj>0e∑i:si>0r$\begin{pmatrix} r_1 & s_1 & & & \\ r_2 & & s_2 & & \\ \vdots & & & \ddots \\ r_k & & & & s_k \end{pmatrix}$$r_j>0$. Na extração das submatrizes, permutações arbitrárias de linhas são permitidas, mas não colunas, e subconjuntos arbitrários de linhas e colunas são permitidos. Assim, em particular, comk=1, os elementos diferentes de zero em cada linha deA nãodevem diminuir.$\sum_{i:s_i>0} \frac{r_i}{s_i} > 1$$k=1$$A$

Infelizmente, no meu problema, as matrizes não são gananciosas, embora eu ainda acredite que são gananciosas. Por exemplo, na minha acima da condição é violada e esta matriz não é caixa-gananciosos embora seja ganancioso. Até onde eu sei, não há resultados na identificação de matrizes gananciosas.$A_1$

O exemplo mais fácil para algo como isso pode ser o problema da mochila fracionada, em que itens podem ser fracionados. esse problema (e seu lp dual) pode ser resolvido classificando os itens para lucro por peso, escolhendo a sequência mais longa nessa ordem, que seja possível e fracionando o último item.