Lineare Programmierlösung in einem Durchgang mit geordneten Variablen

Ich habe eine Familie linearer Programmierprobleme: Maximiere vorbehaltlich A x ≤ b , x ≥ 0 . Die Elemente von A , b und c sind nichtnegative ganze Zahlen, c streng positiv. ( x sollte auch ganzzahlig sein, aber darüber werde ich mich später Gedanken machen.)$c' x$$A x\le b$$x\ge0$$A$$b$$c$$c$$x$

In meiner Anwendung kommt es häufig vor, dass die Koeffizienten und c so sind, dass ein vereinfachter Ein-Durchlauf-Algorithmus die optimale Lösung für jede Wahl von b ergibt : Der Ein-Durchlauf-Algorithmus bestimmt die Elemente x 1 , … , x n nacheinander und wählt jedes x j soll der größtmögliche Wert sein, der mit den bereits bestimmten Werten x 1 , … , x j - 1 übereinstimmt . In der Simplex-Sprache beträgt die Reihenfolge der Eingabe von Variablen nur x 1 bis x $A$$c$$b$$x_1,\dots,x_n$$x_j$$x_1,\dots,x_{j-1}$$x_1$$x_n$und endet nach Schritten. Dies spart viel Zeit im Vergleich zu Full-On-Simplex.$n$

Dieser Algorithmus funktioniert, wenn die Spalten von und die Elemente von c von "billig" nach "teuer" sortiert wurden. Eine "billige" Variable ist eine Spalte von A mit im Allgemeinen kleinen Werten, für die das entsprechende Element von c groß ist: Für dieses Element von x erhalten Sie viel Ausgabe, ohne dass die Bedingung b sehr stark beansprucht wird . Der Algorithmus sagt also nur "Mach zuerst die einfachen Sachen."$A$$c$$A$$c$$x$$b$

Meine Frage ist: Welche Eigenschaft von und c würde uns versichern, dass dieser vereinfachte Algorithmus für alle b funktioniert ? Meine anfängliche Vermutung war, dass die Nicht-Null-Elemente von A in jeder Zeile zunehmen sollten, aber das ist nicht korrekt.$A$$c$$b$$A$

Hier einige Beispiele, alle mit : 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 0 1 ) , A $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}$ . Für alle diese gibt der sequentielle Algorithmus die optimale Lösung für alle Werte von b (durch numerisches Experimentieren). Eine 3 ist die einzige, für die auch alle Permutationen von Spalten funktionieren. A 1 und A 3 sind besonders verwirrend, da ( 1 , 1 , 3 ) teurer aussieht als ( 1 , 3 , 0 ) und ( 1 $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)$$(1,3,0)$ teurer als ( 1 , 0 , 0 ) .$(1,1,1)$$(1,0,0)$

Ich wäre sehr dankbar für Hinweise auf die Literatur, für solche Probleme oder Vorschläge. Es muss andere Fälle gegeben haben, in denen einige Variablen als "billiger" als andere eingestuft werden können und sicher zuerst durchgeführt werden können. Bei all der Arbeit, die im Laufe der Jahre an der linearen Programmierung geleistet wurde, scheint etwas Ähnliches aufgetaucht zu sein, aber ich konnte es nicht finden.

$c_{ij} + c_{kl} \geq c_{il} + c_{kj}$$1 \leq i < k \leq n$$1 \leq j < l \leq n$

$A$

Ich stelle mir vor, dass es neuere Ergebnisse gibt, aber hoffentlich beantwortet dies Ihre Frage zumindest teilweise und gibt Ihnen einige Ideen, wo Sie sonst suchen sollten.

$b$$x\le d$$b$$d\ge0$

$c_1\ge\dots\ge c_n>0$$A$$k\times(k+1)$$k$$\begin{pmatrix} r_1 & s_1 & & & \\ r_2 & & s_2 & & \\ \vdots & & & \ddots \\ r_k & & & & s_k \end{pmatrix}$$r_j>0$$\sum_{i:s_i>0} \frac{r_i}{s_i} > 1$$k=1$$A$

$A_1$

Das einfachste Beispiel für so etwas könnte das fraktionierte Rucksackproblem sein, bei dem Gegenstände fraktioniert werden dürfen. Dieses Problem (und sein LP-Dual) kann gelöst werden, indem die Artikel nach Gewinn pro Gewicht sortiert werden, die längste Sequenz in dieser Reihenfolge ausgewählt wird, die machbar ist, und der letzte Artikel fraktioniert wird.