HorusLP-Gurobi : architecture d'optimisation de haut niveau pour Gurobi

À mesure que les technologies d'optimisation deviennent plus sophistiquées, les solveurs commerciaux ont commencé à jouer un rôle de plus en plus important dans l'industrie. Par rapport aux solveurs open source, les solutions commerciales ont généralement plus de fonctionnalités pour résoudre des modèles d'optimisation complexes tels que la prérésolution avancée, le démarrage à chaud et la résolution distribuée.

L'un des solveurs commerciaux les plus populaires sur le marché est Gurobi, du nom des cofondateurs Zonghao Gu, Edward Rothberg et Robert Bixby, chacun un pionnier dans le domaine des solveurs commerciaux. Gurobi a alimenté de nombreux projets d'optimisation de haut niveau dans l'histoire récente, notamment le projet d'allocation de bande passante de la FCC et le projet de réaffectation des prisonniers de la prison d'État de Pennsylvanie.

Aujourd'hui, nous verrons comment HorusLP, un progiciel qui fournit une interface déclarative de haut niveau pour la modélisation d'optimisation, s'intègre à l'API de Gurobi pour offrir une expérience de modélisation intuitive aux utilisateurs tout en exploitant les fonctionnalités les plus avancées de Gurobi.

Optimisation : un rappel rapide

Pour ceux qui ne sont pas familiers avec l'optimisation ou la recherche opérationnelle, l'optimisation fait référence à un ensemble de techniques mathématiques qui trouvent les valeurs optimales des variables dans un système d'équations soumis à un système de contraintes. Si la phrase ci-dessus semble un peu sèche, peut-être qu'un exemple aidera à illustrer.

Supposons que vous ayez un sac à dos d'une capacité de charge de 15 livres. Vous avez devant vous quelques objets, chacun avec un poids et une valeur monétaire spécifiques :

1. Appareil photo : poids 2 lb, valeur 5 $
2. Figurine : poids 4 lb, valeur 7 $
3. Cidre : poids 7 lbs, valeur 2$
4. Corne : poids 10 lb, valeur 10 $.

Vous voulez choisir les articles à placer dans votre sac à dos de manière à ce que le poids total reste inférieur à 15 lb, mais que la valeur soit maximisée. (Si vous avez besoin de plus de contexte sur la raison pour laquelle nous collons des objets de grande valeur dans un sac à dos, nous vous encourageons à utiliser votre imagination pour un récit. Les bons récits candidats incluent le sauvetage d'objets d'un incendie et d'enchères immobilières… ou certaines activités néfastes que nous Je préfère ne pas mentionner.)

On peut formuler le problème sous la forme du problème d'optimisation suivant :

 Let // Each variable stands for whether we put the item into the knapsack Camera = {0, 1} Figurine = {0, 1} Cider = {0, 1} Horn = {0, 1} // Maximize dollar value Maximize 5 * camera + 7 * figurine + 2 * cider + 10 * horn // Weight must stay below 15 pounds 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Une fois que nous avons formulé ce problème, nous pouvons appliquer des techniques d'optimisation pour trouver les meilleurs articles à placer dans notre sac à dos. Vous pouvez trouver un exemple de la solution dans mes articles précédents sur la résolution de problèmes d'optimisation à l'aide de Python et la résolution de problèmes d'optimisation à l'aide de l'API principale HorusLP.

La technique mathématique sous-jacente est assez fascinante, mais sort du cadre de cet article. Si vous souhaitez en savoir plus, je vous recommande de regarder ici et ici, tous deux gracieuseté de Gurobi.

Gourobi

Alors que les premiers problèmes d'optimisation ont été résolus par des équipes de mathématiciens travaillant avec des calculatrices, la plupart des problèmes d'optimisation actuels sont résolus à l'aide de logiciels spécialisés appelés solveurs. Alors que la plupart des solveurs sont généralement capables de trouver des solutions à la majorité des problèmes de programmation linéaire et entier bien formulés, certains solveurs sont beaucoup plus capables que d'autres. Ils peuvent résoudre des classes de problèmes que d'autres ne peuvent pas résoudre, résoudre des problèmes plus rapidement en appliquant des mathématiques de pointe ou résoudre des problèmes importants et difficiles à l'aide d'ordinateurs distribués. Les fonctionnalités les plus avancées sont généralement fournies par des solveurs commerciaux développés et maintenus par des sociétés spécialisées dans la création des solveurs les plus rapides et les plus sophistiqués.

Gurobi est l'un des leaders sur le marché des solveurs commerciaux, utilisé par de larges segments de la communauté de l'optimisation, notamment les gouvernements, les institutions universitaires et les entreprises opérant dans des secteurs allant de la finance à la logistique. En termes de vitesse, gurobi surpasse constamment dans plusieurs benchmarks utilisés pour juger les solveurs commerciaux et open source.

Gurobi est également livré avec une puissante API Python qui vous permet de créer des modèles à partir de Python. Cette fonctionnalité permet aux modélisateurs d'accéder à toutes les bibliothèques de manipulation de données utiles de Python lors de la construction du modèle, ce qui facilite grandement leur processus. En guise de démonstration de l'API Python gurobi, voici comment modéliser le problème du sac à dos :

 import gurobipy as gr m = gr.Model() camera = m.addVar(name='camera', vtype=gr.GRB.BINARY) figurine = m.addVar(name='figurine', vtype=gr.GRB.BINARY) cider = m.addVar(name='cider', vtype=gr.GRB.BINARY) horn = m.addVar(name='horn', vtype=gr.GRB.BINARY) m.addConstr(2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 , 'size constraint') m.setObjective(5 * camera + 7 * figurine + 2 * cider + 10 * horn, gr.GRB.MAXIMIZE) m.optimize() print(camera.x) print(figurine.x) print(horn.x) print(cider.x)

L'exécution de l'exemple vous donnera le résultat suivant :

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% -0.0 1.0 1.0 -0.0

HorusLP

HorusLP est une bibliothèque de modélisation d'optimisation qui a été construite sur des expériences de développement d'algorithmes d'optimisation. Les bibliothèques de modélisation actuellement disponibles manquent des outils nécessaires pour travailler avec le type de problèmes complexes et à multiples facettes qui sont généralement rencontrés par les applications commerciales de la recherche opérationnelle.

Alors que la plupart des bibliothèques d'optimisation offrent une interface impérative de bas niveau, à mesure que les modèles d'optimisation deviennent plus complexes, de meilleurs outils sont nécessaires pour gérer la complexité. HorusLP est une bibliothèque qui fournit des outils de haut niveau pour gérer ces complexités. HorusLP fournit également de puissants outils de débogage et de création de rapports qui permettent un développement et une itération plus rapides.

À la base, HorusLP est une bibliothèque orientée objet qui fournit une architecture indispensable autour de modèles d'optimisation. En tirant parti de la syntaxe orientée objet Python, la bibliothèque HorusLP fournit une structure autour de laquelle les modèles d'optimisation peuvent être optimisés. Le résultat est une base de code découplée, modulaire et facile à lire.

Si vous souhaitez une introduction plus détaillée à la bibliothèque de base HorusLP avec des exemples de code, vous pouvez trouver un tutoriel ici.

Intégration HorusLP-Gurobi

Bien que l'API principale d'HorusLP fournisse une API de haut niveau pratique pour créer des modèles d'optimisation, elle est basée sur PuLP, qui, bien que capable d'utiliser Gurobi comme solveur, n'a pas accès à certaines des capacités plus avancées de Gurobi.

HorusLP-Gurobi est une version de l'API HorusLP construite à l'aide de l'API Python de Gurobi. Cela permet à l'utilisateur d'accéder directement aux fonctionnalités avancées de Gurobi, tout en gardant l'API HorusLP cohérente.

L'une des philosophies clés guidant le développement d'HorusLP-Gurobi était la cohérence avec l'API principale d'HorusLP. En gardant la structure minimaliste d'HorusLP cohérente, un utilisateur d'un solveur open source peut facilement passer à l'utilisation de Gurobi en installant l'API Gurobi et en changeant les instructions d'importation.

Pour les modèles simples, les modèles basés sur HorusLP prendront plus de lignes de code que la simple utilisation impérative de l'API Python. Cependant, à mesure que le processus de développement se poursuit et que les modèles deviennent plus complexes, les conceptions orientées objet et déclaratives de l'API HorusLP faciliteront le débogage et le développement. L'orientation objet rendra également le modèle plus lisible, car la définition du modèle crée centralise et délimite clairement les objectifs, les contraintes et les variables, etc.

Sans plus tarder, plongeons dans quelques exemples de code !

Exemples de codes

API HorusLP de base

Comme HorusLP-Gurobi maintient la cohérence de l'API, le code du didacticiel principal d'HorusLP peut être transféré avec une simple modification des importations. Pour utiliser HoruLP-Gurobi, cependant, vous devrez vous assurer que l'optimiseur Gurobi et l'interface Python de Gurobi sont installés. Vous pouvez obtenir Gurobi en les contactant ici.

Une fois que vous avez installé Gurobi, nous pouvons commencer à coder avec HorusLP-Gurobi ! Commençons par installer le package requis :

 Pip install horuslp horuslp-gurobi

Une fois l'installation terminée, nous pouvons commencer à utiliser HorusLP-Gurobi ! Rappelez-vous l'exemple du problème du sac à dos de tout à l'heure. Nous pouvons utiliser HorusLP-Gurobi pour modéliser le problème comme suit :

Tout d'abord, importez les bibliothèques appropriées.

 from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE

Définissez quelques variables.

 class KnapsackVariables(VariableManager): # we define variables by declaring the “vars” class variable vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn')

Maintenant, nous pouvons définir les contraintes en utilisant la classe de contraintes.

 class SizeConstraint(Constraint): # implement the 'define' function, the variables will get passed in by name def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Nous pouvons alors mettre en œuvre l'objectif de la même manière.

 class ValueObjective(ObjectiveComponent): # implement the define function and return the objective expression def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

Et enfin, nous pouvons définir le problème.

 class KnapsackProblem(Problem): # defining a problem using the Horus API is a matter of setting variables in the subclass variables = KnapsackVariables objective = ValueObjective # constraints is a list variable, since there can be multiple constraints,. constraints = [SizeConstraint] # make sure to set the sense! sense = MAXIMIZE

Et nous instancions le problème et appelons la fonction de résolution. C'est là que la magie opère.

 prob = KnapsackProblem() # instantiate prob.solve() # call the solve method prob.print_results() # optional: print the standard Horus debug report print(prob.result_variables) # optional: print the variable results as a list

Exécutez le code et vous devriez voir le résultat suivant :

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% KnapsackProblem: Optimal camera -0.0 figurine 1.0 cider -0.0 horn 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'camera': -0.0, 'figurine': 1.0, 'cider': -0.0, 'horn': 1.0}

La première partie est le solveur Gurobi, et la seconde partie est la sortie de HorusLP. Comme vous pouvez le voir, l'algorithme recommande de prendre la figurine et la corne, ce qui donne 14 livres d'articles d'une valeur de 17 $.

L'un des avantages d'utiliser HorusLP avec Gurobi est que vous obtenez beaucoup d'informations "gratuitement". Une grande partie des informations que l'on voudrait normalement consulter pendant le développement, telles que la valeur de chaque variable, la valeur de l'objectif final et les valeurs de contrainte, sont automatiquement calculées et sorties dans un format facile à lire.

Si vous avez lu l'article précédent sur le noyau HorusLP, vous remarquerez qu'il s'agit presque exactement de la même API. Pour garder l'API simple, les interfaces du noyau HorusLP et de HorsLP-Gurobi sont identiques, les différences entre les solveurs étant abstraites dans l'implémentation de la superclasse.

Ainsi, nous laisserons l'introduction d'HorusLP à cet exemple simple ; des exemples plus complexes démontrant les fonctionnalités avancées d'HorusLP peuvent être trouvés dans l'article précédent.

Fonctionnalités de Gurobi

Gurobi fournit de nombreuses fonctionnalités avancées pour résoudre des problèmes complexes. La plupart des fonctionnalités sont accessibles via l'objet Modèle. Pour permettre une compatibilité totale avec l'API Gurobi, l'objet model est facilement accessible depuis la classe du problème en tant que model .

Par exemple, si vous vouliez écrire le fichier MPS du modèle de sac à dos, dans Gurobi, vous pouvez écrire quelque chose comme m.write('knapsack.mps') . En utilisant HorusLP-Gurobi, vous pouvez simplement :

 # import the problem as usual from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE # define the constraint class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 # define the objectives as above class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn # define the variables used by the constraints and objectives class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') # define the problem as in the above example class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE # instantiate the problem. We don't need to call solve or print any reports. prob = KnapsackProblem() prob.model.write('knapsack.mps') # this is the only bit of new code!

Et vous devriez voir le fichier MPS dans votre répertoire de travail.

Vous pouvez utiliser cette interface pour accéder aux fonctionnalités avancées de Gurobi, telles que le calcul d'IIS, la création de rappels ou la fourniture d'indices variables.

Fonctionnalités avancées de Gurobi à votre service

Aujourd'hui, nous avons examiné une version de la bibliothèque HorusLP construite au-dessus de l'API Gurobi Python. En plus des fonctionnalités de rapport et de débogage du noyau HorusLP, vous avez désormais accès à toutes les fonctionnalités avancées de Gurobi accessibles de manière transparente grâce à l'intégration avec l'API Python de Gurobi.

Si vous êtes un utilisateur actuel de Gurobi ou quelqu'un qui souhaite utiliser l'optimisation Gurobi, j'espère que vous essayez HorusLP ! Vous pouvez trouver des exemples de code, faire des suggestions ou contribuer à HorusLP-Gurobi sur GitHub.