Meilleur solutionneur open source d'optimisation mixte entier [fermé]

Question

J'utilise CPLEX pour résoudre d'énormes modèles d'optimisation (plus de 100 000 variables). J'aimerais maintenant voir si je peux trouver une alternative open source. Je résous les problèmes de nombres entiers mixtes (MILP). CPLEX fonctionne très bien, mais il est très efficace. cher si nous voulons évoluer, j'ai donc vraiment besoin de trouver une alternative ou de commencer à écrire notre propre bibliothèque d'optimisation ad-hoc (ce qui sera pénible)

Toute suggestion / idée serait très appréciée

Answer 1

J'ai personnellement trouvé GLPK meilleur (c'est-à-dire plus rapide) que LP_SOLVE. Il prend en charge divers formats de fichiers. Un autre avantage est son interface de bibliothèque, qui permet une intégration en douceur avec votre application.

Answer 2

Nouvelle approbation de la COIN-OR . Nous avons constaté que le composant d'optimiseur linéaire (Clp) était très puissant et que le composant entier mixte (Cbc) pouvait être très bien réglé avec certaines analyses. Nous avons comparé avec LP-Solve et GLPK.

Pour les problèmes vraiment difficiles, un solutionneur commercial est la solution.

Answer 3

Essayez le solveur SCIP. Je l'ai utilisé pour les problèmes MILP avec plus de 300 000 variables et de bonnes performances. Ses performances MILP sont bien meilleures que celles de GLPK. Gurobi offre également d'excellentes performances pour les problèmes de MILP (et généralement meilleures que SCIP (mai 2011)), mais cela pourrait être coûteux si vous n'êtes pas un utilisateur universitaire. Gurobi utilisera le multicœur pour accélérer la résolution du problème.

Answer 4

Avez-vous essayé lp_solve ? Il y avait aussi d'autres suggestions dans les questions suivantes, pour Java:

• bibliothèque d'optimisation mathématique pour Java & # 8212; - recommandations gratuites ou à code source ouvert?
• Outil de programmation linéaire / Bibliothèques pour Java

Answer 5

Si j'étais vous, j'essaierais d'utiliser une interface multi-résolveur telle que Osi (C ++) ou PuLP (python) afin que vous puissiez écrire votre code une fois et le tester avec de nombreux solveurs.

Si les programmes entiers que vous allez résoudre sont énormes, je recommanderais python au C ++, car votre code aura l'air plus propre et 99% du temps sera passé dans le solveur.

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

Si, au contraire, les problèmes sont petits, le temps nécessaire pour les copier depuis la mémoire de Python vers le solveur (dans les deux sens) n’est plus à négliger: dans ce cas, vous pouvez expérimenter des améliorations de performances notables avec un langage compilé.

Mais si les problèmes sont énormément énormes, les langages compilés gagneront à nouveau, car l’empreinte mémoire sera grossièrement divisée par 2 (aucune copie du problème en python).

Answer 6

Je recommande de consulter le projet COIN. PIÈCE OU

Beaucoup de bons solveurs ici, y compris ipOPT pour des problèmes non linéaires et un couple les solveurs entiers mélangés aussi bien.

Answer 7

Scip n'est pas mauvais!

Answer 8

Bien que ce ne soit peut-être pas ce que vous souhaitiez entendre, il existe des années-lumière entre les solveurs commerciaux CPLEX et Gurobi, d'une part, et les solveurs open source, de l'autre.

Néanmoins, vous pouvez avoir de la chance et votre modèle fonctionne bien avec GLPK, Coin ou similaire, mais en général, les solutions open source sont bien loin des solveurs commerciaux. Si c'était différent, personne ne paierait 12 000 $ pour une licence Gurobi et encore plus pour une licence CPLEX.

Ces dernières années, j'ai vu beaucoup, beaucoup de modèles qui étaient trop difficiles pour les solveurs open source. Croyez moi ...

Ce n’est pas vraiment une question de taille, mais de difficulté numérique.

Answer 9

100k variables est un gros problème. Beaucoup de bibliothèques open source ne fonctionnent pas bien avec autant de variables. D'après ce que j'ai lu, lp_solve n'a été testé que pour environ 30 000 variables. Utiliser le système commercial peut être votre seul choix.

Answer 10

J'ai utilisé DICOPT en utilisant le serveur NEOS ( http: / /www.neos-server.org/neos/solvers/minco:DICOPT/GAMS.html ) pour résoudre de grands programmes non linéaires entiers mixtes (approximativement 1k variables et 1k contraintes) et l'a trouvé excellent.

Pour mon problème, DICOPT a fait beaucoup mieux que les autres solveurs MINLP listés sur le serveur neos BARON / KNITRO / LINDO / SBB, etc.

La soumission de travaux à NEOS est soumise à certaines contraintes. C’est un peu fastidieux, mais le libre accès à un puissant logiciel de résolution des problèmes commerciaux compense largement.

Answer 11

Je vais ajouter ce qui suit aux réponses déjà excellentes.

Bien que, comme d'autres l'ont souligné, les solutions commerciales soient beaucoup plus rapides et plus performantes que les alternatives libres, il est important de prendre en compte l'ampleur de l'écart que vous pouvez accepter en matière d'optimalité. Pour les gros problèmes comportant de nombreuses variables entières, vous pouvez obtenir des temps de résolution beaucoup plus rapides si vous pouvez accepter un écart d’optimalité supérieur ou égal à 1% (les valeurs par défaut ont tendance à se situer autour de 0,01% ou moins).

Bien sûr, si vous résolvez un problème où 1% correspond à des millions de dollars, ceci n’est pas acceptable - d’où le marché des solveurs de premier ordre. (Quelques comparaisons entre Gurobi et les solveurs libres ici )

Je conviens avec d'autres que l'utilisation d'une plate-forme générant des fichiers de problèmes indépendants du solveur (tels que les fichiers * .mps, * .lp) en vaut la peine, car vous pouvez ensuite essayer d'autres solveurs. J'utilise PuLP et je le trouve et le solveur gratuit COIN_CBC, excellent. Bien que limité pour les problèmes avec de nombreuses variables entières.

Answer 12

Je suis surpris que personne n'ait mentionné MIPCL ( http: //www.mipcl- cpp.appspot.com/index.html ). Ce solveur prétend être open source sous licence LGPL (source: http: //www.mipcl -cpp.appspot.com/licence.html ), il est donc également approprié pour être utilisé dans des applications non-open-source. Mais ce qui manque pour être vraiment open source, c'est le code source du solveur lui-même.

Hans Mittelmann très récemment (10 septembre 2017) a réalisé un benchmark en programmation linéaire mixte: http: / /plato.asu.edu/ftp/milpc.html (la page de présentation http://plato.asu.edu/bench.html ou les diapositives de son exposé: http://plato.asu.edu/talks/informs2017.pdf ).

Dans le référentiel de programmation linéaire en nombres entiers mixtes avec 12 unités d'exécution et une limite de temps de 2 heures, MIPCL est parvenu à résoudre 79 instances. Seuls les solveurs commerciaux CPLEX, Gurobi et XPRESS ont réussi à résoudre davantage sous les contraintes données (respectivement 86 ou 87 instances).

Également en termes de métrique de performance choisie (toujours avec 12 threads), MIPCL est plus rapide que les dérivés SCIP (FSCIPC, FSCIPS) comparés et le résolveur open source CBC. Encore une fois, seuls les solveurs commerciaux CPLEX, Gurobi et XPRESS surpassent MIPCL de manière significative en termes de performances.

Answer 13

Pas de source ouverte, mais si vous possédez une licence Microsoft Academic Alliance, la Microsoft Solver Foundation L'édition d'entreprise (MSF) est incluse. Gurobi est également gratuit à des fins académiques, je l'ai utilisé dans ma thèse.