Algorithmus zur Minimierung der Ganzzahlprogrammierung

Question

Ich verstehe, dass es ein sehr komplexes Problem ist, die Minimierung in der Ganzzahl -Programmierung zu durchführen. Aber was macht dieses Problem so schwierig?

Wenn ich versuchen würde, einen Algorithmus zu schreiben, um ihn zu lösen, was müsste ich dann berücksichtigen? Ich bin nur mit der Zweig-und-gebundenen Technik vertraut, um sie zu lösen, und frage mich, welche Art von Straßensperren ich ausgesetzt bin, wenn ich versucht, diese Technikprogramme anzuwenden.

Answer 1

Wie der andere sagte diese Probleme sehr schwierig und es gibt weder eine einfache Lösung noch einfachen Algorithmus, die für alle Probleme der Probleme gelten.

Die "klassische" Art der Lösung dieses Problems besteht darin, einen Zweig-und-Gebäude durchzuführen und den Simplex-Algorithmus auf jeden Knoten anzuwenden, wie Sie in Ihrer Frage sagen. Ich würde dies jedoch nicht selbst empfehlen, dies selbst zu implementieren, wenn Sie kein Experte sind.

Bei vielen numerischen Methoden ist es sehr schwierig, es richtig zu machen (gute Parameterwerte, gute Optimierungen), und es wurden viele durchgeführt (siehe cplex, coin_or usw.).

Es ist nicht so, dass Sie es nicht können: Der Zweig-und-gebundene Teil ist ziemlich stroigtforward, aber ohne all die Tricks wird Ihr Programm sein Ja wirklich langsam.

Außerdem benötigen Sie eine Simplex-Implementierung, und dies ist nicht etwas, was Sie selbst tun möchten: Sie müssen ohnehin eine LIB von Drittanbietern verwenden.

Höchstwahrscheinlich wether

• Wenn Ihr Datensatz nicht so groß ist (probieren Sie es aus!) Und Sie sind nicht daran interessiert, ihn sehr schnell zu lösen: Verwenden Sie etwas wie Münz- oder LP_Solve mit der Standardmethode, sondern funktioniert.
• Wenn Ihr Datensatz wirklich groß ist (und/oder Sie jedes Mal schnell eine Lösung finden müssen), müssen Sie mit einem Experten in diesem Bereich zusammenarbeiten.

Mein Hauptpunkt ist, dass nur erfahrene Menschen es tun werden kennt Welcher Algorithmus in Ihrem Problem besser abschneidet, die Form des Modells ist am einfachsten zu lösen, welche Methode Sie sich anwenden sollen und welche Art von Optimierungen Sie versuchen können.

Wenn Sie an diesen Problemen interessiert sind, würde ich dieses Buch für eine Einführung in die Mathematik hinter all dem empfehlen (mit vielen Beispielen). Es ist unglaublich expansiv, also möchten Sie vielleicht in eine Bibliothek gehen, anstatt sie zu kaufen: Nemhauser und Wolsey.

Answer 2

Ich frage mich, mit welchen Straßensperren ich versuchen werde, diese Technik programmatisch anzuwenden.

Keine insbesondere keine (unter der Annahme einer ziemlich einfachen Implementierung ohne viele Tricks). Die Algorithmen sind nicht kompliziert - sie sind Komplex, Das ist ein grundlegender Unterschied.

Techniken wie Zweig und gebunden oder verzweigen und schneiden versuchen, den Suchbaum zu beschneiden und so die Laufzeit zu beschleunigen. Aber der gesamte Problembaum ist dennoch exponentiell groß, daher das Problem.

Answer 3

Ganzzahlprogrammierung ist Np-harte. Deshalb ist es so schwierig.

Da ist ein Lernprogramm damit Sie interessiert sein könnten.

Answer 4

Das erste, was Sie tun, bevor Sie ein Problem mit mathematischer Optimierung lösen, ist, dass Sie es kategorisieren. Mit Ausnahme von Sonderfällen werden die meisten Integer-Programmierprobleme NP-HART sein. Anstatt einen "Algorithmus" zu verwenden, werden Sie eine "Heuristik" verwenden. Die endgültige Lösung, die Sie finden, wird kein garantiertes Optimum sein, aber es wird eine ziemlich gute Lösung für Probleme im wirklichen Leben.

Ihre Hauptstraßensperre sind Ihre Programmierkenntnisse. Die heuristische Programmierung erfordert ein gutes Maß an Programmierverständnis. Anstatt Ihre eigene Heuristik zu programmieren, können Sie besser bekanntes Paket verwenden (z. B. Münzen oder frei). Auf diese Weise können Sie sich auf Ihr Problem anstelle der Heuristik konzentrieren.