Meilleur résolveur d'optimisation D'entier mixte en source ouverte [fermé]
j'utilise CPLEX pour résoudre d'énormes modèles d'optimisation (plus de 100k variables) maintenant, je voudrais voir si je peux trouver une alternative open source, je résous les problèmes d'entiers mixtes (MILP) et fonctionne CPLEX grand mais il est très coûteux si nous voulons mettre à l'échelle, donc je dois vraiment trouver une alternative ou commencer à écrire notre propre bibliothèque d'optimisation ad-hoc (qui sera douloureux)
Toute suggestion/insight serait très apprécié
13 réponses
personnellement, j'ai trouvé GLPK mieux (c'est à dire plus rapide) que LP_SOLVE. Il prend en charge différents formats de fichiers, et un autre avantage est son interface de bibliothèque, ce qui permet une intégration en douceur avec votre application.
une Autre mention pour PIÈCE de monnaie OU de . Nous avons constaté que la composante d'optimisation linéaire (Clp) était très forte, et que la composante d'optimisation mixte (Cbc) pouvait être assez bien ajustée avec une certaine analyse. Nous avons comparé avec LP-Solve et GLPK.
pour les problèmes vraiment difficiles, un résolveur commercial est la voie à suivre.
essayez le résolveur SCIP. Je l'ai utilisé pour les problèmes MILP avec plus de 300K variables avec de bonnes performances. Sa performance MILP est bien meilleure que celle de GLPK. Guobi a également une excellente performance pour les problèmes MILP (et généralement mieux que le SCIP (mai 2011)), mais il pourrait être coûteux si vous n'êtes pas un utilisateur universitaire. Gurobi utilisera multicores pour accélérer le solveur.
avez-vous essayé lp_solve ? Il y avait aussi d'autres suggestions dans les questions suivantes, pour Java:
je recommande de vérifier le projet de pièce de monnaie. COIN OU
beaucoup de bons résolveurs ici, y compris l'ipOPT pour les problèmes non linéaires et un couple mixed integer solveurs.
si j'étais vous, j'essaierais d'utiliser une interface à plusieurs résolveurs comme Osi (C++) ou PuLP (python) pour que vous puissiez écrire votre code une fois, et le tester avec de nombreux résolveurs.
si les programmes entiers que vous allez résoudre sont énormes, je recommande python sur C++, parce que votre code sera plus propre et 99% du temps sera passé dans le solveur.
si, au contraire, les problèmes sont petits, alors le temps de copier les problèmes de la mémoire de python vers le solveur (aller-retour) ne doit plus être négligé: dans ce cas, vous pouvez expérimenter quelques améliorations de performance notables en utilisant un langage compilé.
mais si les problèmes sont énormes, alors les langues compilées vont gagner encore une fois, parce que l'empreinte mémoire sera grossièrement divisée par 2 (Aucune copie du problème en python).
bien que ce ne soit peut-être pas ce que vous voulez entendre, mais il ya des années-lumière entre les résolveurs commerciaux CPLEX et Gurobi d'une part et les résolveurs à source ouverte d'autre part.
Néanmoins vous pouvez être chanceux et votre modèle fonctionne bien avec GLPK, Coin ou similaire, mais en général les solutions open source sont loin derrière les solveurs commerciaux. S'il était différent, personne ne paierait 12.000$ pour une licence de Gurobi et encore plus pour une licence CPLEX.
au cours des dernières années, j'ai vu beaucoup, beaucoup de modèles qui étaient juste trop difficiles pour les solveurs open source. Croyez-moi...
ce n'est pas tant une question de taille, mais de difficulté numérique.
100k variables est un grand problème. Beaucoup de bibliothèques open-source ne fonctionnent pas bien avec autant de variables. De ce que j'ai lu lp_solve n'a été testé pour environ 30k variables. L'utilisation du système commercial peut être votre seul choix.
j'ai utilisé DICOPT en utilisant le serveur NEOS ( http://www.neos-server.org/neos/solvers/minco:DICOPT/GAMS.html ) pour résoudre les grands (environ 1K variables et 1K contraintes) programmes non-linéaires de type mixte entier et trouvé excellent.
Pour mon problème DICOPT a fait beaucoup mieux que les autres MINLP solveurs répertoriés sur le neos serveur BARON/KNITRO/LINDO/CFF etc.
il y a certaines contraintes à la soumission d'emplois aux NEOS et il est un peu encombrant, mais le libre accès à un puissant solveur commercial compense plus que cela.
je vais ajouter ce qui suit aux réponses déjà excellentes.
alors que, comme d'autres l'ont souligné, les solveurs commerciaux sont beaucoup plus rapides et plus capables que les alternatives libres, il est important de considérer combien d'un écart d'optimalité vous pouvez accepter. Pour les grands problèmes avec de nombreuses variables entières, vous pouvez obtenir des temps de résolution beaucoup plus rapides si vous pouvez accepter 1% ou encore plus grand écart d'optimalité (par défaut ont tendance à être autour de 0,01% ou moins).
de bien sûr, si vous résolvez un problème où 1% se traduit en millions de dollars, ce n'est pas acceptable - d'où le marché pour les meilleurs résolveurs. (Quelques comparaisons de Gurobi gratuit solveurs ici )
je suis d'accord avec d'autres que l'utilisation d'une plate-forme qui génère des fichiers de problèmes indépendants du solveur (tels que *.les députés, *.lp files) est utile car vous pouvez ensuite essayer d'autres résolveurs. J'utilise PuLP et je le trouve, et le libre Solveur COIN_CBC, excellent. Bien que limité pour les problèmes avec de nombreuses variables entières.
pas open source, mais si vous avez une licence Microsoft Academic Alliance, La Microsoft Solver Foundation (MSF) enterprise edition est inclus. Gurobi est également libre à des fins académiques, Je l'ai utilisé dans ma recherche de thèse.
je suis surpris que personne n'ait mentionné MIPCL ( http://www.mipcl-cpp.appspot.com/index.html ). Il est open source sous licence LGPL (source: http://www.mipcl-cpp.appspot.com/licence.html ), donc également utilisable dans des applications non open-source.
Hans Mittelmann très récemment (10 Sep 2017) a fait la programmation linéaire mixte Benchmark: http://plato.asu.edu/ftp/milpc.html (vous pourriez également être intéressé à regarder la page d'aperçu http://plato.asu.edu/bench.html ou les diapositives de son discours: http://plato.asu.edu/talks/informs2017.pdf ).
dans le Benchmark mixte de programmation linéaire entier avec 12 threads et une limite de temps de 2 heures MIPCL réussi à résoudre 79 instances. Seuls les résolveurs commerciaux CPLEX, Gurobi et XPRESS ont réussi à résoudre plus sous les contraintes données (86 ou 87 des cas, respectivement).
également en termes de la métrique de performance choisie (encore une fois en utilisant 12 threads) MIPCL est plus rapide que les dérivés de référence SCIP (FSCIPC, FSCIPS) - rappelons que SCIP n'est pas un solveur open source - et le solveur open source CBC. Encore une fois, seuls les résolveurs commerciaux CPLEX, Gurobi et XPRESS surpassent MIPCL de manière significative en termes de performance.