Beste Open-Source-Mixed Integer-Optimierung Solver [geschlossen]

Question

Ich bin mit CPLEX für große Optimierungsmodelle zu lösen (mehr als 100k Variablen) jetzt würde ich gerne sehen, wenn ich eine Open-Source-Alternative zu finden, kann ich lösen gemischt-ganzzahlige Probleme (MILP) und CPLEX funktioniert gut, aber es ist sehr teuer, wenn wir ich brauche so wirklich, um eine Alternative zu finden oder dem Schreiben beginnen unsere eigene ad-hoc-Optimierung Bibliothek (die schmerzhaft sein wird)

skalieren möchten

Jeder Vorschlag / Einsicht wäre sehr willkommen

Answer 1

Ich persönlich fand GLPK besser (das heißt schneller) als lp_solve. Es unterstützt verschiedene Dateiformate und ein weiterer Vorteil ist die Bibliothek-Schnittstelle, die mit Ihrer Anwendung reibungslose Integration ermöglicht.

Answer 2

Eine weitere Bestätigung für COIN-OR . Wir fanden, dass die lineare optimiser Komponente (Clp) war sehr stark, und die gemischte ganzzahlige Komponente (Cbc) konnte sehr gut mit einigen Analysen abgestimmt werden. Wir verglichen mit LP-Solve und GLPK.

Für wirklich schwierigen Probleme, eine kommerzielle Solver ist der Weg zu gehen.

Answer 3

Versuchen Sie, die SCIP-Löser. Ich habe es für MILP Probleme mit mehr als 300K Variablen mit einer guten Leistung verwendet. Seine MILP Leistung ist viel besser als GLPK. Gurobi hat auch eine ausgezeichnete Leistung für MILP Probleme (und in der Regel besser als SCIP (Mai 2011)), aber es könnte teuer werden, wenn Sie keine akademischen Benutzer sind. Gurobi wird Multicores verwendet die Solver zu beschleunigen.

Answer 4

Haben Sie versucht, lp_solve ? Es gab auch einige andere Vorschläge in den folgenden Fragen, für Java:

• mathematische Optimierung Bibliothek für Java - kostenlos oder Open-Source-Empfehlungen?
• Linear Programming Tool / Bibliotheken für Java

Answer 5

Wenn ich Sie wäre, würde ich versuchen, eine Multi-Solver-Schnittstelle zu verwenden, wie Osi (C ++) oder Pulp (Python), so dass Sie Ihren Code einmal schreiben kann, und testen Sie es mit vielen Löser.

Wenn die Integer-Programme, die Sie riesig lösen gehen, würde ich Python über C ++ empfehlen, da Sie Code saubere aussehen und 99% der Zeit wird in dem Solver ausgegeben werden.

• https://projects.coin-or.org/Osi
• http://code.google.com/p/pulp-or/

Wenn, im Gegenteil, die Probleme sind klein, dann ist die Zeit für das Kopieren der Probleme, die aus Python-Speicher an die Solver (hin und zurück) nicht mehr vernachlässigt werden: in diesem Fall, dass Sie einige deutlichen Leistungsverbesserungen experimentieren können mit eine kompilierte Sprache.

Aber wenn die Probleme überwiegend enorm sind, dann kompilierten Sprachen werden wieder gewinnen, da der Speicherbedarf in etwa um 2 (keine Kopie des Problems in Python) aufgeteilt wird.

Answer 6

Ich empfehle die Überprüfung der COIN-Projekt aus. Münz- oder

Viele gute Löser hier, einschließlich ipOPT für nichtlineare Probleme und ein paar sowie gemischt-ganzzahligen Löser.

Answer 7

Scip ist nicht schlecht!

Answer 8

Das ist zwar vielleicht nicht das, was Sie hören wollen, aber es gibt Lichtjahre zwischen den kommerziellen Solver CPLEX und Gurobi auf der einen Seite und Open-Source-Solver auf der anderen Seite.

Dennoch können Sie mit etwas Glück und Ihr Modell funktioniert gut mit GLPK, Münze oder dergleichen, aber im Allgemeinen Open-Source-Lösungen sind weit hinter den kommerziellen Solvern. Wenn es anders wäre, würde niemand zahlen 12.000 $ für eine Gurobi Lizenz und noch mehr für eine CPLEX Lizenz.

In den letzten Jahren habe ich viele, viele Modelle zu sehen, die für die Open-Source-Löser nur schwer waren. Glauben Sie mir ...

Es ist nicht so sehr eine Frage der Größe, sondern von numerischen Schwierigkeiten.

Answer 9

100k Variablen ist ein großes Problem. Viele der Open-Source-Bibliotheken funktionieren nicht gut mit, dass viele Variablen. Von dem, was ich habe lp_solve nur seit rund 30k Variablen gelesen hat getestet. das kommerzielle System kann Ihre einzige Wahl sein.

Answer 10

Ich habe verwendet DICOPT den NEOS-Server ( http: / /www.neos-server.org/neos/solvers/minco:DICOPT/GAMS.html ) zu lösen, große (ca. Variablen 1K- und 1k constraints) gemischt-ganzzahligen nicht-lineare Programme und fand es ausgezeichnet.

Für mein Problem DICOPT tat viel besser als der andere MINLP Solver notiert an dem neos Server BARON / KNITRO / LINDO / SBB etc.

Es gibt bestimmte Einschränkungen Arbeitsplätze NEOS einreichen, und es ist etwas umständlich, aber der freie Zugang zu einem leistungsfähigen kommerziellen Solver mehr als macht sich für sie.

Answer 11

Ich werde die folgenden auf die bereits sehr guten Antworten hinzuzufügen.

Während, wie andere haben darauf hingewiesen, kommerzielle Solvern viel schneller und besser in der Lage als die freien Alternativen ist es wichtig zu prüfen, wie viel von einem Optimalitätslücke können Sie annehmen. Für große Probleme mit vielen Integer-Variablen können Sie viel schneller lösen-mal, wenn man 1% annehmen kann oder sogar größer optimality Spalt (Standardwerte sind in der Regel um 0,01% oder weniger sein).

Natürlich, wenn Sie ein Problem zu lösen, wobei 1% führt zu Millionen von Dollar dies nicht akzeptabel ist - daher der Markt für erstklassige Löser. (Einige Vergleiche von Gurobi zum kostenlosen Löser hier )

würde ich mit anderen darüber einig, dass eine Plattform, die Solver-unabhängig Problemdateien (zB * .mps, * .LP Dateien) lohnt sich, wie Sie erzeugt dann können andere Löser ausprobieren. Ich verwende PULP und bin zu finden und das freie COIN_CBC Löser, ausgezeichnet. Obwohl mit vielen Integer-Variablen für Probleme beschränkt.

Answer 12

Ich bin überrascht, dass niemand erwähnt hat MIPCL ( http: //www.mipcl- cpp.appspot.com/index.html ). Dieser Solver behauptet Open Source unter der LGPL-Lizenz (Quelle zu sein: http: //www.mipcl -cpp.appspot.com/licence.html ), so ist es auch geeignet zur Verwendung in nicht-Open-Source-Anwendungen verwendet zu werden. Aber was wirklich Open Source sein fehlt, ist der Quellcode des Solver selbst.

Hans Mittelmann vor kurzem (10. September 2017) hat Programmierung Benchmark Mixed Integer Linear: http: / /plato.asu.edu/ftp/milpc.html (man könnte auch im Blick auf die Übersichtsseite http://plato.asu.edu/bench.html oder die Folien seines Vortrags: http://plato.asu.edu/talks/informs2017.pdf ).

In der Mixed Integer Linear Programming Benchmark mit 12 Threads und eine Frist von 2 Stunden MIPCL verwalten 79 Fälle zu lösen. Nur die kommerziellen Solver CPLEX, Gurobi und XPRESS verwalten mehr unter den gegebenen Randbedingungen zu lösen (86 oder 87 Instanzen, respectively).

Auch in Bezug auf dem gewählten Leistungsmaß (wieder unter Verwendung von 12 Fäden) MIPCL ist schneller als der gebenchmarkt SCIP Derivate (FSCIPC, FSCIPS) und der Open-Source-Solver-CBC. nur wieder die kommerziellen Solver CPLEX, Gurobi und XPRESS outcompete MIPCL signifikant in Bezug auf Leistung.

Answer 13

Nicht Open Source, aber wenn Sie eine Microsoft Academic Alliance-Lizenz haben, die Microsoft Solver Foundation (MSF) Enterprise Edition ist im Preis inbegriffen. Gurobi für akademische Zwecke auch frei ist, habe ich es in meiner Arbeit Forschung.