Eine Frage, die ich kürzlich bei sci.op-research gestellt habe, bot mir eine willkommene Abwechslung von einer langweiligen Arbeit, über die ich lieber nicht nachdenke und von der Sie lieber nichts hören würden. Wir wissen, dass die gierige Heuristik das Problem des kontinuierlichen Rucksacks löst
maximizec'xs.t.a'x≤bx≤ux∈ℜ + n (1)
zur Optimalität. (Der Beweis, Dualitätstheorie verwendend, ist ziemlich einfach.) Nehmen wir an, dass wir hinzufügen, was ich eine Zählungseinschränkung nennen werde, nachgebend
maximizec'xs.t.a'x≤be'x = b~x≤ux∈ℜ + n (2)
wo e = (1, ..., 1). Kann es durch etwas anderes als die Simplex-Methode, wie eine Variante der Greedy-Heuristik, gelöst werden?
Die Antwort ist ja, obwohl ich mir überhaupt nicht sicher bin, ob das, was ich mir ausgedacht habe, einfacher zu programmieren oder effizienter ist als die Simplex-Methode. Persönlich würde ich eine Verbindung zu einer Bibliothek mit einem linearen Programmierungslöser herstellen und Simplex verwenden, aber es war amüsant, eine Alternative zu finden, auch wenn die Alternative keine Verbesserung gegenüber Simplex darstellt.
Die Methode, die ich vorstellen werde, beruht auf Dualität, insbesondere einem wohlbekannten Ergebnis, dass beide, wenn eine durchführbare Lösung für ein lineares Programm und eine machbare Lösung für ihr duales die komplementäre Schlaffheit erfüllen, in ihren jeweiligen Problemen optimal sind. Ich werde die Doppelvariablen für den Rucksack bezeichnen und die Beschränkungen λ bzw. μ zählen. Beachten Sie, dass λ≥0, aber μ im Vorzeichen uneingeschränkt ist. Im Wesentlichen würde dieselbe Methode, die unten angegeben ist, mit einer Ungleichheitszahlbeschränkung (e'x ≤ b) arbeiten und wäre tatsächlich etwas leichter, da wir a priori das Vorzeichen von & mgr; (nichtnegativ) kennen würden. Das Poster der ursprünglichen Frage hat eine Einschränkung der Gleichheitsanzahl angegeben, also werde ich das verwenden. Es gibt auch Doppelvariablen (ρ≥0) für die oberen Schranken. Das doppelte Problem ist
minimumbλ + b~μ + u'ρs.t.λa + μe + ρ≥cλ, ρ≥0. (3)
Da es sich um einen Blogeintrag und keine Dissertation handelt, gehe ich davon aus, dass (2) machbar ist, dass alle Parameter streng positiv sind und dass die optimale Lösung einzigartig und nicht degeneriert ist. Eindeutigkeit und Entartung werden den Algorithmus nicht ungültig machen, aber sie würden die Darstellung komplizieren. In einer optimalen, grundlegenden, machbaren Lösung für (2) gibt es entweder eine oder zwei Basisvariablen - eine, wenn die Knapsackbeschränkung nicht bindend ist, zwei, wenn sie bindend ist - mit jeder anderen variablen Nichtbasis entweder an ihrer unteren oder oberen Grenze. Angenommen, (λ, μ, ρ) ist eine optimale Lösung für das duale von (2). Die reduzierten Kosten für jede Variable xi sind ri = ci-λai-μ. Wenn die Knapsack-Einschränkung nicht bindend ist, dann ist λ = 0 und die optimale Lösung ist
xi = uiri & gt; 0b-Σrj & gt; 0ujri = 00ri & lt; 0. (4)
Wenn die Knapsack-Einschränkung bindend ist, gibt es zwei Elemente (j, k), deren Variablen grundlegend sind, mit rj = rk = 0. (Indem ich Entartung angenommen habe, habe ich die Möglichkeit, dass die Slack-Variable in der Knapsack-Constraint mit dem Wert 0 grundlegend ist, weggenommen). einstellen
xi = uiri & gt; 00ri & lt; 0 (5)
und sei b '= b-Σi∉ {j, k} aixi und b~' = b~-Σi∉ {j, k} xi. Die zwei grundlegenden Variablen sind gegeben durch
xj = b'-akb~'aj-akxk = b'-ajb''ak-aj. (6)
Der Algorithmus wird in zwei Schritten ablaufen, zuerst nach einer Lösung mit der Rucksack-Bindung suchen (eine grundlegende x-Variable) und dann nach einer Lösung mit der Rucksackbindung suchen (zwei grundlegende x-Variablen). Beachten Sie, dass das erste Mal, wenn wir machbare Primal- und Duallösungen finden, die komplementärer Erschlaffung folgen, beide optimal sein müssen, also sind wir fertig. Man beachte auch, dass wir jedes μ und jedes λ≥0 vervollständigen können, um eine praktikable Lösung für (3) zu erhalten, indem wir ρi = ci-λai-μ + setzen. Wir werden uns also immer mit einer machbaren dualen Lösung befassen, und der Algorithmus wird Primal-Lösungen konstruieren, die die komplementäre Schlaffheit erfüllen. Das Abbruchkriterium reduziert sich daher auf die konstruierte ursprüngliche Lösung, die durchführbar ist.
Für die erste Phase sortieren wir die Variablen so, dass c1≥ ⋯ ≥cn. Da λ = 0 ist und es eine einzige Basisvariable (xh) gibt, deren reduzierte Kosten Null sein müssen, ist offensichtlich μ = ch. Das bedeutet, dass die reduzierten Kosten ri = ci-λai-μ = ci-ch von xi nicht negativ für ih sind. Wenn die durch (3) gegebene Lösung machbar ist - das heißt, wenn Σih. Somit können wir eine Bisektionssuche verwenden, um diese Phase abzuschließen. Wenn wir einen großen Wert von n annehmen, kann die anfängliche Sortierung in O (nlogn) -Zeit erfolgen und der Rest der Phase erfordert O (logn) -Iterationen, von denen jede O (n) -Zeit verwendet.
Leider sehe ich keinen Weg, die Bisektionssuche auf die zweite Phase anzuwenden, in der wir nach Lösungen suchen, bei denen die Rucksackzwangsbindung bindet und λ & gt; 0. Wir werden wieder den Wert von μ suchen, aber diesmal monoton. Zuerst wenden Sie die gierige Heuristik auf Problem (1) an und behalten die Knapsack-Einschränkung bei, ignorieren jedoch die Zählereinschränkung. Wenn die Lösungen zufälligerweise die Zählerbedingung erfüllen, sind wir fertig. In den meisten Fällen wird die Zählbeschränkung jedoch verletzt. Wenn der Zählwert b übersteigt, können wir folgern, dass der optimale Wert von & mgr; in (4) positiv ist; Wenn der Zählwert kleiner als b ~ ist, ist der optimale Wert von μ negativ. Wir starten die zweite Phase mit μ = 0 und bewegen uns in Richtung des optimalen Wertes.
Da die gierige Heuristik Elemente so sortiert, dass c1 / a1 ≥ ∞ ≥cn / an, und da wir mit μ = 0 beginnen, hat unsere aktuelle Sortierreihenfolge (c1-μ) / a1 ≥ ⋯ ≥ (cn-μ )/ein . Wir werden diese Reihenfolge beibehalten (bei Bedarf nachsortieren), wenn wir nach dem optimalen Wert von μ suchen. Um Verwirrung zu vermeiden (ich hoffe), lassen Sie mich annehmen, dass der optimale Wert von μ positiv ist, so dass wir μ im Laufe der Zeit erhöhen werden. Wir suchen nach Werten von (λ, μ), wobei zwei der x Variablen basisch sind, was bedeutet, dass zwei reduzierte Kosten 0 haben. Angenommen, das tritt für xi und xj auf; dann
ri = 0 = rj · ci-λai-μ = 0 = cj-λaj-μ (7) ⟹ci-μai = λ = cj-μaj.
Es ist leicht zu zeigen (dem Leser als Übung überlassen), dass wenn (c1-μ) / a1 ≥ ⋯ ≥ (cn-μ) / an für den aktuellen Wert von μ, dann der nächsthöhere (niedrigere) Wert von μ was eine Bindung in (7) erzeugt, muss ein fortlaufendes Paar von Items beinhalten (j = i + 1). Darüber hinaus, wieder abdriftend (in diesem Fall bedeutet mehr als zwei Elemente mit reduzierten Kosten 0), wenn wir μ etwas über den Wert, bei dem Elemente i und i + 1 die Kosten 0 reduziert haben, anstoßen, ist die einzige Änderung in der Sortierreihenfolge Die Items I und I + 1 tauschen die Plätze. Keine weitere Bewegung in dieser Richtung wird i und i + 1 veranlassen, wieder zu binden, aber natürlich können beide von ihnen mit ihrem neuen Nachbarn die Straße hinunter gebunden werden.
Die zweite Phase beginnt, beginnend mit μ = 0, wie folgt. Berechne für jedes Paar (i, i + 1) den Wert μi von μ, wobei (ci-μ) / ai = (ci + 1-μ) / ai + 1; Ersetzen Sie diesen Wert durch ∞, wenn er kleiner als der aktuelle Wert von μ ist (dies zeigt an, dass die Verbindung in die falsche Richtung erfolgt). Aktualisiere μ zu miniμi, berechne λ aus (7) und berechne x aus (5) und (6). Wenn x ursprünglich durchführbar ist (was sich auf 0 ≤ xi ≤ui und 0 ≤ xi + 1 ≤ui + 1 reduziert), dann halte an: x ist optimal. Andernfalls tausche ich i und i + 1 in der Sortierreihenfolge aus, setze μi = ∞ (die reindexierten Items i und i + 1 werden nicht wieder gebunden) und berechne μi-1 und μi + 1 neu (kein anderer μj wird durch den Swap beeinflusst).
Wenn die erste Phase kein Optimum gefunden hat (und wenn die gierige Heuristik zu Beginn der zweiten Phase nicht glücklich wurde), muss die zweite Phase mit einem Optimum enden, bevor die Werte von μ nicht mehr ausreichen ( alle μj = ∞). Die Entartung kann entweder mit einem kleinen zusätzlichen Aufwand beim Codieren (zum Beispiel das Prüfen mehrerer Kombinationen von i und j in der zweiten Phase, wenn Dreiwege- oder höhere Bindungen auftreten) oder durch Ausführen kleiner Störungen zum Brechen der Entartung behandelt werden.