Was ist die schnellste Software (Open Source), um ein Problem mit der Programmierung von gemischten Ganzzahlen zu lösen?

Ich habe ein gemischtes Integer-Programmierproblem. Und ich verwende derzeit GLPK als meinen Löser. Aber ich fand, dass GLPK für das lineare Programmierproblem gut ist, aber für die gemischte Ganzzahl-Programmierung benötigt es viel mehr Zeit und entspricht daher nicht unseren Anforderungen. Ich suche so andere Software. Gibt es noch andere gute Open-Source-Tools, die das Problem der gemischten Ganzzahl-Programmierung mit hoher Geschwindigkeit lösen können? Vielen Dank!

Wenn Sie etwas Open Source möchten, möchten Sie wahrscheinlich den CBC-Code von COIN ausprobieren (es gibt auch ein paar andere MILP-Löser, wie ein Branch-and-Price-Framework oder SYMPHONY).

Gurobi und CPLEX werden erheblich schneller sein, und ab dem INFORMS-Meeting 2011 oder 2012 war Gurobi schneller als CPLEX (obwohl die Leistungsmetriken natürlich problemabhängig sind). Bei den in meiner Arbeit gelösten MILPs war Gurobi ungefähr 15-100-mal schneller als CBC und CPLEX war fast so schnell wie Gurobi, jedoch etwas langsamer (wie 12-80-mal schneller).

Obwohl die Leistung im ungünstigsten Fall tatsächlich exponentiell ist, hängt die Ausführungszeit stark von der Problemstruktur ab. Es ist unwahrscheinlich, dass Sie eine MILP mit Millionen von Variablen lösen können, wenn Sie nicht eine spezielle Struktur ausnutzen (möglicherweise, wenn es sich um ein stochastisches Programm handelt, das in viele kleinere Probleme zerlegt werden kann), aber es ist durchaus möglich, nicht-triviale MILPs mit Tausenden von Variablen zu lösen Variablen in weniger als einer Minute. (Natürlich kann es auch eine Stunde dauern, bis diese Probleme gelöst sind.)

Laut Brian Borchers verfügen CPLEX und Gurobi über kostenlose Lizenzen für einige Forscher. Eines dieser beiden Softwarepakete eignet sich am besten als Allzweck-MILP-Löser.

Mixed Integer Linear Programming Probleme sind viel schwieriger zu lösen als lineare Programmierprobleme. In Bezug auf die Komplexität der Berechnung können LPs in polynomialer Zeit gelöst werden, während das Lösen von MILP ein NP-hartes Problem ist. Die bekannten Algorithmen zum Lösen von MILPs weisen eine exponentielle Komplexität im ungünstigsten Fall auf.

Es gibt andere Softwarepakete für die gemischte lineare Ganzzahlprogrammierung, die Sie sich ansehen können, einschließlich SCIP (für den akademischen Gebrauch kostenlos), CPLEX (für den kommerziellen Gebrauch, jedoch mit einer akademischen Lizenzierungsoption) und GUROBI (auch für den kommerziellen Gebrauch mit einer akademischen Lizenzierungsoption). Ein oder mehrere Einige dieser Pakete sind möglicherweise bei Ihren Problemen wesentlich schneller als GLPK. Erwarten Sie jedoch nicht, dass sie bei der Lösung von MILP-Problemen annähernd so schnell sind wie bei der Lösung von LPs ähnlicher Größe.

Wenn Sie eine Reihe verschiedener Löser ausprobieren möchten, probieren Sie das JuMP-Modellierungsframework von Julia aus . Sie können Ihr Modell als JuMP-Modell schreiben und dann die Solver mit einer Codezeile austauschen. Bei MILP-Problemen können Sie beispielsweise zwischen den Lösern Bonmin, Cbc, Couenne, CPLEX, GLPK, Gurobi und MOSEK wählen. Aus diesem Grund können Sie, wenn Sie es in JuMP schreiben, einfach alle von Geoff erwähnten Löser ausprobieren und sehen, was funktioniert, ohne einen Haufen Code schreiben zu müssen. Ihre persönlichen Tests sind die beste Wissensquelle für die schnellsten Algorithmen für Ihre Probleme.

Nach den Vorschlägen anderer habe ich (das kommerzielle) GAMS verwendet für viele Projekte verwendet. Es ist sehr einfach; Alles, was Sie tun müssen, ist die mathematische Formulierung Ihres Problems. Es nimmt die Variablen, Nebenbedingungen, Zielfunktionen und alle Eingabedaten auf. Dann bietet es eine Reihe von Lösern (Optimierern) für jeden Fall. Abhängig von Ihrem Fall fügen Sie komplexere Löser hinzu.

Sicherlich EASY ist einen Blick wert. Open-Source-Framework.

Der Begriff "schnell" ist sehr vage! Sie müssen genauer sein; Schnell in Bezug auf die Anzahl der Iterationen? Anzahl der Bewertungen? verstrichene Zeit? Kombination von diesen?

Wenn Sie jedoch keine Software suchen und nur das Problem lösen möchten, kann ich die Verwendung des globalen Optimierers NSGA-II vorschlagen, eines Open-Source-Optimierers mit sehr hohem Ansehen und hoher Leistung.

Wenn Sie mehr Informationen zur Verfügung stellten, könnte ich genau führen.