Diskussion:Ganzzahlige lineare Optimierung

Schnittebene

Mir ist nicht klar geworden, wie ich eine gültige Schnittebene finden kann, denn eine Bedingung ist ja, dass diese zusätzliche Ungleichung alle zulässigen Lösungen des IPs abdeckt. Die kann ich aber nicht alle kennen, sonst wäre mir ja auch automatisch die Lösung des IPs bekannt. Wie kann ich also feststellen, dass eine Schnittebene im Sinne des Verfahrens überhaupt gültig ist?89.0.50.166 10:10, 13. Apr. 2011 (CEST)

Ich weiss, die Frage ist lange her, aber zur Vollständigkeit:

Man erhält gültige Schnittebenen indem man den folgenden Prozess iteriert:

1. Nehme eine nicht-negative Linearkombination der Ungleichungen in $Ax<=b$, sagen wir $c^{T}x\leq t$, so dass $c$ ganzzahlig ist. Die entstehende Ungleichung ist nach Konstruktion sowohl für alle ganzzahligen, als auch für alle nicht-ganzzahligen Lösungen gültig.
2. Runde die rechte Seite ab, wir erhalten $c^{T}x\leq \lfloor t\rfloor$ Da die rechte Seite für ganzzahlige $x$ auch ganzzahlig ist, ist die neue Ungleichung immer noch für alle ganzzahligen Lösungen gültig.
3. Füge die neue Ungleichung dem System hinzu.

Man kann zeigen, dass man alle gültigen Ungleichungen so herleiten kann, und man kann ein Verfahren angeben, dass durch das systematische Anwenden dieses Prozesses ein LP erzeugt, dessen Optimallösung auch eine Optimallösung für das IP ist.

--84.165.54.84 04:57, 24. Mär. 2014 (CET)

unbeschränktes Polyeder vs. unbeschränktes IP

Im Rahmen meiner gestrigen Änderungen an diesem Artikel, die reverted wurde, hier eine Diskussion dazu:

• In der Fachliteratur gibt es diverse Eigenschaften, die ein (ganzzahliges oder reelles) lineares Optimierungsproblem haben kann:

• Infeasible / unlösbar / nicht zulässig: Es gibt keine Lösung, die alle Bedingungen erfüllt
• Unbounded / unbeschränkt: es gibt für jede gegegebene Schranke $k$ eine Lösung $x$ mit $c^{T}x\geq k$ (im Falle eines Maximierungsproblems)

• Insbesondere bezieht sich unbeschränkt also in sämtlicher mir bekannter Literatur nicht auf die Anzahl der Lösungen, sondern auf die zugehörigen Zielfunktionswerte.
  Es kann z.B. sein, dass es unendlich viele Lösungen gibt (Anzahl der Lösungen unbeschränkt), die aber alle optimal sind (Zielfunktion beschränkt).
  

Ein solches LP / IP ist gemäß der üblichen Definition nicht unbounded, obwohl der zugrunde liegende Polyeder kein Polytop, also unbounded ist.
 In den allermeisten Fällen sind wir in der Situation, dass es beliebig viele nicht-optimale Lösungen gibt (d.h. dass Polyeder unbeschränkt ist), jedoch nur endlich viele Optimallösungen. 

• Für LPs gilt das "Fundamental Theorem of Linear Programming": Aus unbeschränkt und lösbar folgt die existenz einer Optimallösung (Auch hier wieder: unbeschränkt bezieht sich auf die Zielfunktion, nicht auf den Polyeder)
• Es ist einer der wichtigste Unterschiede zwischen reelller und ganzzahliger linearer Optimierung, dass dieser Satz für IPs mit nicht-rationalem Polyeder nicht gilt. Die komplette Theorie zum Lösen von IPs fußt darauf, dass sich jedes IP mit rationalem Polyeder als LP schreiben lässt.

Ich bitte daher darum, meine Änderung diesbezüglich entweder zu akzeptieren oder den Artikel grundsätzlich zu überarbeiten, denn

• der derzeitige Artikel weist des Leser nicht auf diesen fundamentalen Unterschied zwischen IPs und LPs hin
• die Verwendung von "unbeschränktes IP" im Artikel wenn eigentlich "IP mit unbeschränktem zugrundeliegendem Polyeder" gemeint ist, widerspricht der Definition in gängiger Fachliteratur und verwirrt den Leser, wenn sich dieser sich intensiver mit dem Thema befassen möchte

--84.165.54.84 05:16, 24. Mär. 2014 (CET)

Abgrenzung zur kombinatorischen Optimierung

Ich vermisse in dem Artikel eine deutlichere Abgenzung zur kombinatorschen Optimierung, die ja doch eine nicht ganz unerhebliche Überschneidung mit der im Artikel behandelten Problemklasse behandelt.

Hier die generelle Beschränkung auf lineare Gleichungen, dort die generelle Beschränkung auf kleine Definitionsmengen. Das ist doch eine Unterscheidung, die sicherlich nicht jedem Leser so ohne weiteres direkt geläufig ist.

Bei der Suche nach Lösungsansätzen für Probleme, die beiden Pronlemklassen zuzuordnen sind (was zweifellos bei praxisrelevanten Problemen recht häufig vorkommt), stellt sich sicherlich z.B. auch die Frage, ob einer geometrischen Interpretation noch Restfragmente von Zweckmässigkeit anhaften könnten.

--77.3.95.219 20:37, 14. Mai 2015 (CEST)

Interferenz

Interferenz ist im Zusammenhang nicht nur ein unangebrachter Anglizismus, sondern vor allem auch ein false friend. --80.171.178.251 22:04, 20. Dez. 2016 (CET)

Danke für den Hinweis, aber das ist leider nicht gerade mein Spezialgebiet -;). Der Artikel ist jedoch frei bearbeitbar, sodaß Du Dir fragwürdig erscheinende Stellen jederzeit abändern kannst. Etwas weniger radikal kannst Du natürlich auch vorher hier auf der Diskussionsseite einen konkreten Alternativvorschlag zur Diskussion stellen, das würde sicherlich mehr Nichtfachleute ins Boot holen als jetzt. Liebe Grüße, Franz 23:00, 20. Dez. 2016 (CET)

ILP als Teil der konvexen Optimierung? ILP mit kontinuierlichen Variablen?

ILP wird in der Literatur und der Optimierungs-Community nicht als Teil der konvexen Optimierung gesehen. Ein konvexes Optimierungsproblem ist ein kontinuierliches konvexes Optimierungsproblem. Der Hinweis, dass man jedes ILP als konvexes Problem über der konvexen Hülle der zulässigen Punkte (welches ein Polytop ist) aufschreiben kann ist zwar theoretisch richtig, aber praktisch nicht umsetzbar, da die Berechnung der konvexen Hülle ein NP-schweres Problem ist. Unter einem konvexen Optimierungsproblem versteht man "im Volksmund" hingegen ein Problem, in welchem jedes lokale Optimum gleichzeitig ein globales Optimum ist und welches mit Innere-Punkte-Verfahren global optimal gelöst werden kann. Die aktuelle Formulierung ist also mindestens irreführend, insbes. nicht geläufig und wird etwa auch in der englischen Version nicht so erwähnt. Ich lasse das hier ein paar Tage ruhen und mache dann einen Gegenvorschlag zur Formulierung.

ILPs mit kontinuierlichen Variablen werden übrigens als MILPs (mixed-integer linear program) bezeichnet und unter Gemischt-ganzzahlige Optimierung behandelt. --BumbleMath (Diskussion) 18:32, 1. Jan. 2024 (CET)

Vorschlag ist da. --BumbleMath (Diskussion) 18:56, 4. Jan. 2024 (CET)