Wie wählt man einen Integer-Linear-Programming-Solver?

Question

Ich bin Neuling für ganzzahlige lineare Programmierung. Ich plane, einen ganzzahligen linearen Programmierungslöser zu verwenden, um mein kombinatorisches Optimierungsproblem zu lösen. Ich bin vertraut mit C++/objektorientierte Programmierung auf einer IDE. Jetzt verwende ich NetBeans mit Cygwin, um meine Anwendungen die meiste Zeit zu schreiben.

Darf ich fragen, ob es einen einfachen ILP Solver für mich gibt? Oder hängt es von dem Problem, das ich lösen möchte? Ich versuche, einige Ressourcen Mapping-Optimierung zu tun. Bitte lassen Sie mich wissen, wenn weitere Informationen benötigt werden.

Vielen Dank, Cassie.

Answer 1

Linear Programming von Wikipedia umfasst ein paar verschiedene Algorithmen, mit denen Sie etwas graben können, um zu sehen, welche für Sie am besten funktioniert. Hilft das oder wollten Sie etwas Spezifischeres?

Answer 2

Für große Probleme, können Sie sich , die eine Optimierung Interpreter mit vielen backend solvers zur Verfügung steht. Es läuft als a separate process; C++ würde verwendet werden, um die Eingabedaten auszugeben.

Dann könnten Sie verschiedene State-of-the-Art-Löser versuchen.

Answer 3

Wenn was Sie möchten, ist lineare gemischte ganzzahlige Programmierung, dann würde ich auf Coin-OR (und speziell auf das Modul CBC) zeigen. Es ist freie Software (als Sprache) Sie können es entweder mit einer bestimmten Sprache verwenden, oder verwenden Sie C++.

Verwenden Sie C++, wenn Ihre Daten viel Vorverarbeitung erfordern oder wenn Sie Ihre Hände in den Solver legen möchten (Auswahl von Pivot-Punkten, Spaltengenerierung, Hinzufügen von Schnitten usw.).

Verwenden Sie die integrierte Sprache, wenn Sie den Solver als Blackbox verwenden möchten (Sie interessieren sich nur für das Ergebnis und das Problem ist einfach oder klassisch genug, um es zu lösen, ohne es zu optimieren).

Aber in den Tags erwähnen Sie genetische Algorithmen und Graphenalgorithmen. Vielleicht sollten Sie anfangen, indem Sie Ihr Problem besser definieren ... Für Graphen, die ich gerne Boost :: Graph

Answer 4

Ich habe lp_solve (http://lpsolve.sourceforge.net/5.5/) auf ein paar Gelegenheiten mit Erfolg verwendet. Es ist ausgereift, funktionsreich und ist mit vielen guten Ratschlägen sehr gut dokumentiert, wenn Ihre linearen Programmierfähigkeiten rostig sind. Die ganzzahlige lineare Programmierung ist nicht nur ein Zusatz, sondern wird mit diesem Paket stark betont.

Gerade bemerkt, dass Sie sagen, Sie sind ein "Neuling" bei diesem. Nun, dann empfehle ich dieses Paket dringend, da die Dokumentation voll von Beispielen und sanften Tutorials ist. Andere Pakete, die ich ausprobiert habe, neigen dazu, viel von dem Benutzer zu übernehmen.

Answer 5

Blick in GLPK. Kommt mit ein paar Beispielen und arbeitet mit einer Teilmenge von AMPL, obwohl IMHO am besten funktioniert, wenn Sie bei C/C++ für die Modelleinrichtung bleiben. Auch mit ziemlich großen Modellen.