J'ai besoin de résoudre un système linéaire sous-déterminé d'équations et de contraintes, puis trouvez la solution particulière qui minimise une fonction de coût. Cela doit être fait dans un code géré purement portable qui fonctionnera à .NET et mono. Quelles bibliothèques librement disponibles sont là que je peux utiliser pour implémenter cela?
Tous les algorithmes d'optimisation fournis par des bibliothèques libres, je n'ai trouvé que des contraintes d'intervalle de support sur des variables simples, par ex. Le plus proche que j'ai trouvé jusqu'à présent est Dotnumerics , qui inclut la décomposition de la valeur singulière pour la résolution linéaire sous-déterminée Systèmes, mais ses algorithmes d'optimisation ne prennent en charge que les contraintes à une seule variable (autant que possible de le dire).
Il existe plusieurs autres questions posant à propos de la programmation linéaire, mais mes principales exigences sont des contraintes multi-variables et la résolution de systèmes sous-déterminés. Je n'ai pas encore trouvé une bibliothèque libre prenant en charge les contraintes multi-variables. 0 x + 2y <4 . J'ai également constaté que souvent les solveurs d'équations linéaires ne supportent que les systèmes linéaires avec une solution.
4 Réponses :
ALLLIB est la bibliothèque Go-à-à-à-une habituelle pour des éléments tels que des solveurs linéaires. Je donnerais cela un bon regard avant désespéré.
Pour ceux qui cherchent, Google a publié leurs ou outils développeurs.google.com/Optimization , j'ai pu Pour connecter cela rapidement et il soutient ce que l'OP recherche.
La programmation linéaire est destinée à faire exactement ce que vous demandez. Les contraintes multi-variables sont absolument normales dans la programmation linéaire. Recherchez des solveurs gratuits tels que lpsolvez ( http://sourceforge.net/projects/lpsolve/ ), GLPK ( http://www.gnu.org/software/glpk/ ) ou CBC (< a href = "https://projects.coin-or.org/cbc" rel = "nofollow"> https://projects.coin-or.org/cbc ) par exemple.
J'accepte que les suggestions ci-dessus ne sont pas dans C # et non géré les assemblages de .NET. Si tel est un casse-disque pour vous, vous pouvez peut-être essayer de construire une version vous-même du code source de l'une de ces bibliothèques. Peut-être nécessiter un peu de travail cependant - je ne l'ai pas essayé.
On ignore également de votre question initiale à quel point un problème est grand ou complexe que vous essayez de résoudre. Si vous avez des variables qui doivent prendre des valeurs discrètes, vous auriez besoin d'une bibliothèque de solveur qui fera une branche et une liaison ou similaire, sinon si elle est purement linéaire et continue, vous pouvez simplement utiliser un algorithme simplex. C'est dans de nombreux manuels si vous ne trouvez pas une version pré-construite.
Si c'est un problème vraiment minuscule (dizaines de variables et de contraintes) ou simplement linéaire et continu, vous pourrez peut-être vous éloigner de votre propre implémentation (portable, de code géré purifié), mais si vous avez des milliers de contraintes et Variables, vous pourriez avoir du mal à obtenir la performance dont vous avez besoin. Si vous avez un problème important et complexe, vous risquez d'avoir une chance, car vous aurez peut-être besoin d'un solveur commercial pour obtenir les réponses dont vous avez besoin.
Wrapper GLPK pour .NET: Nuget.org/packages/Optimization.solver.glpkKeD/A >
Si vous développez pour .NET (c.-à-d. Not Windows Store, Windows Phone ou Silverlight), je vous recommanderais certainement de jeter un coup d'œil à lpsolve , qui convient aux grands problèmes LP et / ou MILP. Téléchargez le x86 ou < un href = "http://sourceforge.net/projects/lpsveuler/files/lpsve/5.5.5.0/lp_solve_5.5.2.0_dev_win64.zip/download" rel = "Noreferrer"> X64 Archives de développement contenant le lpsolve dll: s, puis téléchargez le . API net archive contenant un fichier C # avec p / invoquer des appels à toutes les fonctions pertinentes de l'API lpsolve .
Une autre alternative consiste à utiliser CLP solveur de la Projets COIN-OU , via le COINMP binaires précompilés. Il y a une dll enroulé C # DLL disponible ici .
Si vous DO nécessitent un code purement géré, Alglib est probablement votre meilleur pari (comme suggéré par Marc Gravell), mais sachez que la licence Open-Source de Alglib utilise GPL. Si vous souhaitez utiliser Alglib dans votre propre code sans la divulguer à la communauté Open-Source, vous devez acheter une licence commerciale Alglib.
Une recherche Internet rapide révèle également une implémentation pure C # de l'algorithme Simplex LP ici . Je ne peux pas identifier l'auteur et je ne sais pas si cette mise en œuvre est correcte ou de toute qualité. Le code semble très portable, même en termes de magasin Windows Store, de téléphone Windows, Silverlight et mono contextes.
J'aurais utilisé Lpsolve si le code natif était autorisé, mais comme spécifié dans ma question, la solution doit être purement gérée pour assurer la transférabilité. Alors merci, mais non merci.
@Dylan n'est pas sûr de savoir pourquoi vous pensez avoir mérité un bowvote, ce n'est pas comme si ma réponse est trompeuse. Certes, vous mentionnez en passant que vous avez besoin d'une solution gérée, mais ce n'est pas évident de votre question pourquoi il s'agit d'un cas de discussion. Plus souvent qu'autrement, les gens demandent des solutions gérées lorsqu'une solution p / invoquée conviendrait parfaitement (comme dans ce cas où lpsolve fonctionne parfaitement sous .NET et mono). La réponse de Marc est évidemment la plus pertinente dans votre cas, mais sachez que Alglib est autorisé par GPL; Si vous souhaitez l'utiliser commercialement, vous devez acheter une licence commerciale allglib .
Peut-être que le bowvote était un peu hâtif, mais la ligne directrice est de savoir si la réponse n'est pas utile. Je peux l'annuler si vous éditez la réponse d'une manière ou d'une autre.
Ma réponse contient une indication claire dans les situations que la solution est applicable et fournit des références pertinentes aux bibliothèques et au code source requis pour mettre en œuvre la solution. Si vous, malgré cela, ne pensez pas que la réponse est d'aucune utilité pour vous ou un autre, alors lecteur avec des problèmes similaires, alors gardez le bowvote.
Mais je ne peux pas annuler le bowtvote à moins que vous ne changiez rien - cela ne me laissera pas uppouver que si cela n'est édité.
Je ne veux pas dire modifier votre réponse pour changer de sens. C'est juste une formalité.
Juste, je vois ce que tu veux dire, désolé. Je vais faire des changements.
Désolé pour la confusion et le bowvote, qui est maintenant corrigé.
Ici, avoir un uppote. Je suis sûr que la réponse sera utile aux autres sans mes besoins.
@Anders: Malheureusement, le code de "Pastebin" ne mentionne pas s'il s'agit de domaine public, voire de son auteur.
@Petero. Vous avez raison. J'ai supprimé la déclaration "Domaine public" de ma réponse. Néanmoins, il n'existe aucune revendication de droits d'auteur explicite associée au code et aucun auteur s'est révélé en pratique, donc dans la pratique, le code est là pour que quiconque soit utilisé pour le but. Mais comme je l'ai mentionné, je n'ai pas vérifié sa validité moi-même, je n'ai compris que le lien comme un conseil pour les autres.
Personne n'a mentionné Fondation Solver . C'est une bonne option.
Un bon, avec quelques exemples expliqués. Licence Express (GRATUIT) permet d'exécuter des problèmes avec une variables de décision maximum de 1 000. Le lien donné est cassé, mais si vous êtes intéressé, vous pouvez le trouver ici
Pour des problèmes exponentiels, cela est très limitatif et je ne le considérerais pas même à distance libre. Quelque chose comme un TSP est limité à 45 points, par exemple.
Avez-vous essayé Alglib?
@Marcgravell Après une inspection de plus près, il ressemble à cela correspond à mes besoins. Merci beaucoup. Mettez cela dans une réponse et je vais accepter. Je ne sais pas comment je n'ai pas tapé auparavant.