Diese Seite wurde von der Cloud Translation API übersetzt.

Erweiterte Lösungen für die Landingpage

Trotz der Reife der LP-Technologie erfordern einige Anwendungsfälle komplexere Techniken. Es gibt beispielsweise eine Reihe verschiedener LP-Algorithmen und Implementierungen, die jeweils Stärken und Schwächen haben. Darüber hinaus kann numerische Instabilität dazu führen, dass Solver bestimmte Modelle verlangsamen oder nicht lösen können.

In diesem Leitfaden werden die Konzepte und Beispiele vorgestellt, mit denen Sie die Leistung und Zuverlässigkeit von LP-Lösungslösungen optimal nutzen können.

Konzepte

In diesem Abschnitt werden die wichtigsten Konzepte für den fortgeschrittenen Einsatz von LP Solver beschrieben. Wir gehen davon aus, dass die Leser mit dem Konzept der Dualität in LP vertraut sind.

Familien von LP-Algorithmen

Die folgenden Klassen von Algorithmen für LP können über ODER-Tools aufgerufen werden.

Der Simplex-Algorithmus war der erste praktische LP-Algorithmus und immer noch der beliebteste. Der Algorithmus bewegt sich entlang der Eckpunkte (Eckpunkte) des zulässigen Bereichs und verbessert dabei iterativ den Wert der Zielfunktion, bis eine optimale Lösung erreicht wird. Es gibt zwei Arten von Simplex-Algorithmen:
1. Das Primal Simplex führt Schritte entlang der Eckpunkte der urpräparierbaren Region aus. Diese Variante ist besonders effektiv bei der Lösung einer Abfolge von LP-Problemen mit unterschiedlichen Zielfunktionen, d. h., wo die ursprüngliche mögliche Region festgelegt ist.
2. Dual Simplex führt Schritte entlang der Eckpunkte der zulässigen dualen Region aus. Diese Variante ist besonders effektiv bei der Lösung einer Abfolge von LP-Problemen, bei denen die duale durchführbare Region festgelegt ist, z. B. wenn sich nur die Grenzen für Variablen ändern. Aus diesem Grund wird Dual Simplex in MIP-Resolvern häufig verwendet.
Hindernisse oder Innenpunkt-Methoden waren die zweite praktische Familie von Algorithmen für LP. Barrieremethoden kombinieren theoretische Garantien einer effizienten Konvergenz (Polynomzeit) mit zuverlässiger Leistung in der Praxis. Sie ergänzen den Simplex-Algorithmus bei schlechter Leistung. Einige Solver bieten beispielsweise an, sowohl Simplex als auch Barrier parallel auszuführen, sodass die Lösung von dem Algorithmus zurückgegeben wird, der zuerst abgeschlossen ist.
Methoden der ersten Ordnung sind eine Familie von Algorithmen, die zur Steuerung der Iterationen ausschließlich Gradienteninformationen (d. h. Ableitungen erster Ordnung) verwenden. Das Gradientenverfahren ist ein bekanntes Beispiel. Diese Methoden sind für die nicht lineare Optimierung und maschinelles Lernen beliebt. Bei LP können Methoden der ersten Ordnung auf größere Probleme als die von Simplex und Barriere skaliert werden und haben möglicherweise auch viel geringere Speicheranforderungen. Andererseits sind sie empfindlicher für numerische Probleme und es fällt ihnen schwer, hochpräzise Lösungen zu erhalten.

In der folgenden Tabelle sind die in OR-Tools verfügbaren LP-Belöser aufgeführt und es wird angegeben, welche der drei Algorithmenfamilien für jeden Maßrechner implementiert sind.

Rechner	Unidirektionale	Straßenbegrenzungs-/Schutzplanke	Erste Bestellung
CLP	X	X
CPLEX^L	X	X
Glop^G	X
GLPK (GLPK)	X	X
Gurobi	X	X
DLP^G			X
Drücken Sie ^L	X	X

G gibt an, dass der Matherechner von Google entwickelt wurde. L gibt an, dass für den Solver eine vom jeweiligen Drittanbieter-Entwickler ausgestellte Lizenz erforderlich ist.

Unter Empfehlungen finden Sie Vorschläge dazu, welche Solver und Algorithmen zu verwenden sind.

Was bedeutet Lösung?

Damit Sie LP-Rechner optimal nutzen können, ist es wichtig zu verstehen, was impliziert wird, wenn ein Solver behauptet, eine Lösung für ein LP-Problem gefunden zu haben. In diesem Abschnitt werden die Grundlagen behandelt, die zur Beantwortung dieser Frage erforderlich sind, insbesondere im Hinblick auf numerische Ungenauigkeiten und Nichteindeutigkeit von Lösungen.

Toleranzen

LP-Belöser verwenden fast immer Gleitkommaarithmetik, wodurch ihre Lösungen von numerischer Ungenauigkeiten abhängig sind. Um dies zu berücksichtigen und die Leistung zu verbessern, indem der Aufwand für Lösungen vermieden wird, die bereits gut genug sind, akzeptieren Löser Lösungen – und behaupten, ein Problem gelöst zu haben, wenn diese Lösungen Bedingungen bis zu bestimmten Toleranzen erfüllen.

Betrachten Sie das Problem der linearen Programmierung.

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

und das entsprechende doppelte Problem

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

Dieses Aufgabenpaar hat eine einzigartige optimale Primärlösung von $ x_1 = 1, x_2 = 0 $ und eine doppelte Lösung $ y = -2 $. Welche Lösungen könnten von einem Matherechner als optimal anerkannt werden? Um dies zu beantworten, definieren wir die folgenden Mengen:

Die Dualitätslücke ist die Differenz zwischen dem ursprünglichen Zielwert und dem Dual-Zielwert, in diesem Fall $ |(-2x_1 - x_2) - y| $.
Die primären Undurchführlichkeiten sind die Verstöße gegen die ursprünglichen Einschränkungen, in diesem Fall $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2, 0\}) $.
Die dualen Undurchführlichkeiten sind die Verstöße gegen die doppelten Einschränkungen, in diesem Fall $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \}) $.

Ein Solver erklärt eine Lösung als optimal, wenn die Dualitätslücke, die ursprünglichen Undurchführbarkeiten und die doppelten Undurchführbarkeiten kleiner sind als eine bestimmte Toleranz.¹

Insbesondere variiert die Anwendung der Toleranzen sowohl aus natürlichen als auch aus idiosyncratischen Gründen bei den Rechnern und Algorithmen. Beispielsweise wird die Dualitätslücke im Simplex-Algorithmus nur durch numerische Ungenauigkeiten gesteuert, während die primäre und die duale Undurchführbarkeit auch bei exakter Arithmetik vorhanden sind. Bei einigen Methoden werden die gebundenen Einschränkungen $ x_1 \ge 0, x_2 \ge 0, $ und $ y \le 0 $ direkt erzwungen. Bei anderen Methoden sind Verstöße gegen gebundene Einschränkungen anders als Verstöße gegen lineare Einschränkungen wie $x_1 + x_2 \le 1$. Für einige Löser sind Dualtoleranzen mit der absoluten Primzahl und die optimale Primzahl in $ – $ / $ y \le 0 $.

Ein Beispiel für die Wirkung von Toleranzen ist eine absolute Toleranz von $\epsilon = \frac{1}{2} $, die auf das obige Prim-Dual-Paar angewendet wird. Die Lösung $ x_1 = 1,5, x_2 = 0, y = -3 $ weist keine Dualitätslücke und Undurchführlichkeiten auf, die kleiner oder gleich $ \epsilon $ sind.Daher könnte ein Matherechner diese Lösung als „optimal“ bezeichnen. Sein Zielwert (-3) unterscheidet sich jedoch um 1 vom wirklich optimalen Zielwert -2. Typische Standardwerte von $ \epsilon $ liegen zwischen $10^{-6}$ und $10^{-8}$, was solche extremen Beispiele selten, aber nicht unmöglich macht.

Arten von Lösungen

Bei LP-Problemen gibt es mehr als eine optimale Lösung, umso mehr bei der Berücksichtigung von Toleranzen. Wir erläutern kurz die Eigenschaften der Lösungen, die von den drei oben vorgestellten Familien von LP-Algorithmen zurückgegeben werden.

Simplex-Algorithmen geben immer Eckpunkte oder Eckpunkte der zulässigen Region zurück. Diese Lösungen werden in einigen Situationen bevorzugt, da sie spärlich sind.

Barriere- und Erstrangmethoden geben in der Regel keine Scheitelpunkte zurück. (Die Theorie bietet zusätzliche Charakterisierungen, die in diesem Leitfaden nicht behandelt werden.)

Aus historischen Gründen und da Vertex-Lösungen ansprechende Attribute haben, wenden Resolver standardmäßig ein Crossover-Verfahren an, um von einer Lösung, die von einem Barrier-Algorithmus gefunden wurde, zu einem optimalen Scheitelpunkt zu wechseln. Für Lösungen, die mit Methoden der ersten Reihenfolge gefunden werden, wird ein Crossover derzeit nicht angeboten.

Empfehlungen

Wir geben die folgenden Empfehlungen für den fortgeschrittenen Einsatz von LP-Lösern.

Skalierung von Problemdaten

Solver können aufgrund numerischer Probleme langsame Konvergenz oder Fehler bei Modellen haben. Für solche Probleme kann es viele Gründe geben. Hier ein Beispiel.

Es ist üblich, dass sehr kleine oder große numerische Konstanten in LP-Modellen auftreten. Wenn $x_1$ und $x_2$ den Anteil der Kunden darstellen, die „Anbieter 1“ oder „Anbieter 2“ zugewiesen sind, und wenn wir den Nutzen aus der Betreuung dieser Kunden maximieren möchten, könnten wir die folgende Zielfunktion schreiben:

$$ \min -c_1x_1 - c_2x_2 $$

Dabei gilt:

$ c_1 $ ist der Vorteil, wenn Kunden dem Anbieter 1 zugewiesen werden
$ c_2 $ ist der Vorteil, wenn Kunden dem Anbieter 2 zugewiesen werden

Duale Tests, die die folgenden Einschränkungen erfüllen, werden mit einer absoluten Toleranz $ \epsilon $ als machbar angesehen:

$ y \le -c_1 + \epsilon $,
$ y \le -c_2 + \epsilon $.

Wenn die Nutzeneinheiten von $ c_1 $ und $ c_2 $ kleine Bruchwerte sind, die im gleichen Maßstab wie $ \epsilon $ liegen, werden die Bedingungen für die duale Machbarkeit ziemlich schwach, sodass ein sehr suboptimaler Ursprung als optimal erklärt werden kann.

Wenn andererseits die Nutzeneinheiten „Mikrodollar“ (1.000.000 Mikrodollar = 1 Dollar) sind, verlangen die resultierenden sehr großen absoluten Werte eine sehr hohe Genauigkeit in der Lösung, was angesichts der Grenzen von Gleitkommazahlen unangemessen hoch ist. Solver können möglicherweise nicht konvergieren, wenn das Problem auf diese Weise formuliert wird. Fortgeschrittene Modellentwickler sollten bei der Formulierung eines gut gestellten Problems berücksichtigen, ob die Problemdaten so skaliert werden, dass sie den Toleranzen ihres Matherechners entsprechen.

Neben der Vermeidung numerischer Fehler können auch Toleranzen für eine bessere Leistung abgestimmt werden. Simplex- und Barriere-Methoden reagieren nicht allzu sensibel auf Toleranzen, können aber gelegentlich von größeren Toleranzen profitieren, wenn der Fortschritt am Ende des Lösungsvorgangs verzögert wird. Andererseits sind Methoden der ersten Ordnung in der Regel viel empfindlicher. Nutzer erster Ordnungsmethoden können von schnelleren Lösungen profitieren, da sie die Toleranzen je nach Kontext lockern.

Informationen zu den Toleranzen von Glop finden Sie unter primal_feasibility_tolerance, dual_feasibility_tolerance und solution_feasibility_tolerance in GlopParameters. Beachten Sie, dass primal_feasibility_tolerance und dual_feasibility_tolerance innerhalb des Algorithmus verwendet werden, während solution_feasibility_tolerance nach dem Lösen ausgewählt wird, um numerische Probleme zu kennzeichnen. Informationen zu PDLP finden Sie unter eps_optimal_absolute und eps_optimal_relative.

Weitere Informationen zu diesen Arten von Problemen findest du in den Richtlinien für numerische Probleme von Gurobi. Die Richtlinien sind für Nutzer von Gurobi verfasst, viele der Prinzipien gelten jedoch allgemein.

Wahl zwischen Matherechner und Algorithmen

Wir beginnen mit einem Beispiel, wie groß die Auswirkungen der Wahl von Lösern und Algorithmen sein können, und stellen Ihnen dann einen Leitfaden zur Auswahl von LP-Lösern vor.

Variabilität in der Praxis

Wir veranschaulichen die Leistungsvariabilität zwischen den LP-Algorithmen und -Resolvern, indem wir die Lösungszeiten für eine Auswahl von Instanzen vergleichen, die von Hans Mittelmann für das Benchmarking von LP-Belösern verwendet wurden. Die Instanzen werden explizit ausgewählt, um die extremen relativen Leistungen darzustellen, und sind nicht unbedingt repräsentativ für das typische Verhalten.

Die Prima- und Dual-Simplex-Methoden von Glop werden mit der Barrieremethode von Gurobi (mit und ohne Crossover, die eine Vertex-Lösung findet) und PDLP, einer Methode der ersten Ordnung, mit hoher und niedriger Genauigkeit verglichen. In der folgenden Tabelle sind die Zeiten in Sekunden angegeben, bei denen ein Limit von 20 Minuten (1.200 Sekunden) angegeben wird.

Instanz	Glop Primal Simplex	Glop Dual Simplex	Gurobi-Bar mit Crossover	Gurobi-Bar ohne Crossover	DLP Hohe Präzision	PDLP Geringe Genauigkeit
ex10	>1200	>1200	79.7	63.5	8.2	2.7
nug08-3rd	>1200	252.8	144,6	3.2	1.1	0,9
savsched1	>1200	>1200	156.0	22,6	46.4	32.4
wide15	>1200	20,8	>1200	>1200	916,4	56.3
Gebäudeenergie	178.4	267.5	12,8	12.3	>1200	157.2
S250R10	12.1	520.6	15.2	16.4	>1200	>1200

Solver-Version	OR-Tools 9.3	OR-Tools 9.3	Gurobi 9.0	Gurobi 9.0	OR-Tools 9.3	OR-Tools 9.3
`solver_specific_parameters`	(Standardwerte)	`use_dual_simplex: true`	`Method 2, Threads 1`	`Method 2, Crossover 0, Threads 1`	`termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 }`	`termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }`

Aus diesen Ergebnissen schließen wir Folgendes.

Die relative Leistung von Algorithmen und Matherechnern kann je nach Größenordnung auf einer einzelnen Instanz variieren.
Kein Algorithmus und Matherechner ist grundsätzlich besser als andere.
Crossover (standardmäßig aktiviert) erhöht die Lösungszeit, manchmal erheblich.
PDLP kann niedrige Genauigkeit manchmal 10-mal schneller als bei hoher Genauigkeit lösen.

Kurzer Leitfaden zur Auswahl von LP-Rechnern

Da kein LP-Algorithmus oder Solver der beste ist, empfehlen wir die folgenden Schritte, um herauszufinden, was für Ihren Anwendungsfall am besten geeignet ist. Beginnen Sie mit dem ersten Schritt und fahren Sie mit dem nächsten fort, wenn die Leistung nicht ausreicht.

Probier es mit Glop. Erläuterung: Glop ist die interne Implementierung der primären und Dual-Simplex-Methoden bei Google. Glop ist Open Source und für die Produktionsarbeitslasten von Google vertrauenswürdig.
- Wenn die Standardkonfiguration (primäres Simplex) nicht gut funktioniert, versuchen Sie, mit use_dual_simplex: true zur Dual-Simplex-Konfiguration zu wechseln.
Wenn eine Lizenz verfügbar ist, kannst du es mit einem kommerziellen Solver (CPLEX, Gurobi oder Xpress) versuchen. Experimentiere mit Simplex- und Barrieremethoden. Erläuterung:Diese Matherechner entsprechen dem Branchenstandard und sind stark optimiert. Barrieremethoden ergänzen die Simplex-Algorithmen von Glop.
- Wenn Sie eine Barriere verwenden, deaktivieren Sie „Crossover“, wenn Sie keine Vertex-Lösung benötigen.
Probiere PDLP aus. Konvergenztoleranzen auf Ihre Anwendung abstimmen. Erläuterung:PDLP wurde für die größten Probleme entwickelt, bei denen Simplex- und Barrieremethoden die Speicherlimits überschreiten oder zu langsam sind. PDLP funktioniert am besten, wenn eine ungefähre, aber schnelle Lösung einer genauen, aber langsamen Lösung vorgezogen wird.
Wenn Sie es bis hierher geschafft haben, sind Sie jetzt ein erfahrener LP-Nutzer! Weitere Informationen finden Sie in den Supportoptionen für OR-Tools.

Es ist oft komplexer als dieses. Solver prüfen diese Bedingungen normalerweise für eine transformierte/vereinfachte Version des Problems, die als gelöstes Problem bezeichnet wird. In einigen Fällen kann eine Lösung des bereits gelösten Problems weit von einer Lösung für das Eingabeproblem entfernt sein. Das kann zu ungewöhnlichen Status wie OptimalInfeas von CPLEX oder IMPRECISE von Glop führen.↩