Rozwiązanie programowania liniowego w jednym przejściu z uporządkowanymi zmiennymi

Mam rodzinę problemów z programowaniem liniowym: maksymalizuj $c' x$ z zastrzeżeniem $A x\le b$, $x\ge0$. Elementy$A$, $b$, i $c$ są liczbami całkowitymi nieujemnymi, $c$ściśle pozytywne. ($x$ powinien być również integralny, ale będę się tym martwić później).

W mojej aplikacji często zdarza się, że współczynniki $A$ i $c$ są takie, że uproszczony algorytm jednoprzebiegowy zapewnia optymalne rozwiązanie dla każdego wyboru $b$: algorytm jednoprzebiegowy określa elementy $x_1,\dots,x_n$ po kolei, wybierając każdy $x_j$ być największą możliwą wartością zgodną z już ustalonymi wartościami $x_1,\dots,x_{j-1}$. W języku simpleks sekwencja wprowadzania zmiennych jest po prostu$x_1$ do $x_n$i kończy się po $n$kroki. To oszczędza dużo czasu w porównaniu do full-on simplex.

Ten algorytm działa, gdy kolumny $A$ i elementy $c$zostały posortowane od „taniego” do „drogiego”. „Tania” zmienna to kolumna$A$ z ogólnie małymi wartościami, dla których odpowiedni element $c$ jest duży: dla tego elementu $x$ otrzymujesz dużą wydajność przy niewielkim zapotrzebowaniu na ograniczenie $b$. Algorytm mówi więc „najpierw wykonaj proste czynności”.

Moje pytanie brzmi: jaką właściwość $A$ i $c$ zapewniłby nas, że ten uproszczony algorytm działa dla wszystkich $b$? Moje początkowe przypuszczenie było takie, że niezerowe elementy$A$ powinna rosnąć w każdym rzędzie, ale to nie jest poprawne.

Oto kilka przykładów $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}$. Dla wszystkich tych algorytm sekwencyjny zapewnia optymalne rozwiązanie dla wszystkich wartości$b$ (przez eksperymenty numeryczne). $A_3$ jest jedynym, dla którego działają również wszystkie permutacje kolumn. $A_1$ i $A_3$ są szczególnie zaskakujące, ponieważ $(1,1,3)$ wygląda drożej niż $(1,3,0)$ i $(1,1,1)$ droższe niż $(1,0,0)$.

Byłbym niezmiernie wdzięczny za wszelkie wskazówki do literatury, za wszelkie podobne problemy lub sugestie. Musiały istnieć inne przypadki, w których niektóre zmienne można określić jako „tańsze” niż inne i można je bezpiecznie wykonać jako pierwsze. Po całej pracy nad programowaniem liniowym na przestrzeni lat wydaje się, że coś podobnego musiało się wydarzyć, ale nie udało mi się go znaleźć.

Prawdopodobnie najbardziej znanym przypadkiem, w którym znany jest chciwy algorytm do rozwiązywania LP, jest szczególny przypadek problemu z transportem. Hoffman („O prostych programach liniowych”, w Convexity , tom 7 Proceedings of Symposia in Pure Mathematics , strony 317-327, 1963) udowodnił, że jeśli macierz kosztów dla problemu (maksymalizacji) spełnia właściwość Monge'a ($c_{ij} + c_{kl} \geq c_{il} + c_{kj}$ kiedy $1 \leq i < k \leq n$, $1 \leq j < l \leq n$), wówczas można znaleźć optymalne rozwiązanie w sposób zachłanny, taki jak ten, który opisujesz.

Hoffman ma także artykuł z ankiety („ O chciwych algorytmach, które się udają ”) z 1985 r., W którym omawia znane przypadki, w których chciwy algorytm zapewnia optymalne rozwiązanie LP. Oprócz cytowanej powyżej własnej pracy (o której mówi: „większość problemów programowania liniowego znanych [do 1963 r.] Jako podatnych na zachłanny algorytm stanowiły szczególne przypadki idei Monge'a”), wspomina o interpretacji programowania liniowego Edmondsa uogólnienie matroidów i omówienie przypadku kiedy$A$ jest między innymi nieujemny.

Wyobrażam sobie, że są nowsze wyniki, ale mam nadzieję, że to przynajmniej częściowo odpowiada na twoje pytanie i daje pewne pomysły na to, gdzie jeszcze szukać.

Dzięki sugestii prof. Spiveya w końcu udało mi się ustalić, co według mnie jest najnowocześniejsze: Ulrich Faigle, Alan J. Hoffman i Walter Kern, „Charakteryzacja nieujemnych macierzy chciwości pudełkowej”, SIAM J. Disc. Matematyka 9 (1996) s. 1-6. Macierz jest „zachłanna”, jeśli algorytm, który opisałem powyżej, zapewnia optymalne rozwiązanie dla wszystkich$b$. Macierz jest „pudełkowata”, jeśli algorytm zachłanny daje optymalne rozwiązanie z dodatkowym warunkiem$x\le d$ dla wszystkich $b$ i wszystkich $d\ge0$. Oczywiście chciwość w pudełku jest silniejszym warunkiem niż chciwość.

Zawsze zakładaj, że $c_1\ge\dots\ge c_n>0$. Dowodzą tego Faigle, Hoffman i Kern$A$ jest chciwy, jeśli i tylko jeśli nie ma $k\times(k+1)$ (dla każdego $k$) submatrix formularza $\begin{pmatrix} r_1 & s_1 & & & \\ r_2 & & s_2 & & \\ \vdots & & & \ddots \\ r_k & & & & s_k \end{pmatrix}$ z każdym $r_j>0$ i $\sum_{i:s_i>0} \frac{r_i}{s_i} > 1$. Podczas wyodrębniania podmacierzy dozwolone są dowolne permutacje wierszy, ale nie kolumn, oraz dowolne podzbiór wierszy i kolumn. Tak więc w szczególności z$k=1$, niezerowe elementy w każdym rzędzie $A$ musi nie zmniejszać się.

Niestety okazuje się, że w moim problemie matryce nie są chciwymi pudełkami, choć nadal uważam, że są chciwe. Na przykład w moim$A_1$powyżej warunek jest naruszony i ta matryca nie jest chciwa, chociaż jest chciwa. O ile mi wiadomo, nie ma żadnych wyników w identyfikacji chciwych matryc.

Najłatwiejszym przykładem czegoś takiego może być frakcyjny problem plecaka, w którym elementy mogą być frakcjonowane. ten problem (i jego podwójny LP) można rozwiązać, sortując przedmioty pod kątem zysku na wagę, wybierając najdłuższą sekwencję w tej kolejności, która jest możliwa, i dzieląc na części ostatni element.