Lineare Programmierlösung in einem Durchgang mit geordneten Variablen

9

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.)cxAxbx0Abccx

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 nAcbx1,,xnxjx1,,xj1x1xnund 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."AcAcxb

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.AcbA

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 4c=(1,1,1)A1=(111123320)A2=(001302032)A3=(111100101) . 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 ,A4=(101010011)bA3A1A3(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.

Robert Almgren
quelle

Antworten:

4

cij+cklcil+ckj1i<kn1j<ln

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.

Mike Spivey
quelle
2
Ich möchte Prof. Spivey für seinen Vorschlag danken. Ich habe eine Weile gebraucht, um die Referenzen zu verfolgen, aber ich werde eine ausführlichere Beschreibung als Antwort geben.
Robert Almgren
3

bxdbd0

c1cn>0Ak×(k+1)k(r1s1r2s2rksk)rj>0i:si>0risi>1k=1A

A1

Robert Almgren
quelle
Ich bin froh, dass meine Antwort Ihnen dabei geholfen hat!
Mike Spivey
3

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.

anonym
quelle