Architecturer des algorithmes d'optimisation avec HorusLP

La recherche opérationnelle et l'optimisation convexe sont un domaine des mathématiques appliquées qui a trouvé de nombreuses applications commerciales au fil des ans. Alors que la puissance de calcul devenait plus abordable et largement disponible, les chercheurs ont commencé à créer des algorithmes d'optimisation de plus en plus sophistiqués pour les aider à prendre de meilleures décisions. Aujourd'hui, les applications alimentées par la recherche opérationnelle alimentent tout, du routage dans la logistique mondiale au lissage de la production d'électricité dans l'industrie de l'énergie.

Au fur et à mesure que la technologie sous-jacente gagnait en complexité, un nouvel ensemble d'outils a été créé pour aider les chercheurs et les développeurs à travailler de manière plus productive. Ces outils, tels que AMPL, CVXPY et PuLP, permettent aux développeurs de définir, de créer et d'exécuter rapidement des algorithmes d'optimisation et de s'interfacer avec une grande variété de solveurs.

Cependant, alors que les technologies d'optimisation et les besoins des entreprises continuent de gagner en sophistication, la plupart de ces outils sont restés plus ou moins les mêmes et n'ont pas évolué assez rapidement pour répondre aux besoins de l'industrie. Par conséquent, le développement, la gestion, le débogage et le réglage de ces algorithmes nécessitent souvent une grande quantité de surcharge cognitive, en particulier dans un environnement commercial en évolution rapide.

Aujourd'hui, j'aimerais vous présenter HorusLP, une bibliothèque d'optimisation Python qui aide à l'architecture des workflows de développement d'algorithmes. Nous parlerons des problèmes que l'outil est conçu pour résoudre, puis donnerons un aperçu rapide de la bibliothèque Python, et nous construirons quelques exemples d'algorithmes d'optimisation.

Problèmes rencontrés par les développeurs d'algorithmes d'optimisation

L'un des problèmes permanents auxquels sont confrontés la plupart des développeurs est l'équilibre entre la construction d'un logiciel facile à maintenir, efficace et idiomatique et la livraison d'un produit dans les délais impartis au projet. Que vous travailliez sur une application basée sur un navigateur, une API Web ou un microservice d'authentification des utilisateurs, il existe souvent un compromis entre la « bonne » méthode et la « rapide » pour atteindre vos objectifs. Ce compromis inhérent devient plus important à mesure que la complexité du produit augmente.

Dans la plupart des disciplines, un développeur peut atténuer ce problème en choisissant un framework ou une bibliothèque qui aide à l'architecture. Dans le frontal Web, de nombreux développeurs choisissent React ou Angular ; dans le monde du développement d'API, les ingénieurs logiciels peuvent choisir entre Django, ASP.NET MVC ou Play, parmi tant d'autres. Cependant, en ce qui concerne l'humble développeur d'algorithmes d'optimisation, il existe très peu d'outils d'architecture pour aider à gérer la complexité architecturale. Le développeur doit gérer lui-même les variables, les contraintes et divers objectifs. De plus, les algorithmes de recherche opérationnelle sont généralement difficiles à introspecter, ce qui aggrave le problème.

L'objectif principal d'HorusLP est de fournir un cadre architectural pour le développement d'algorithmes d'optimisation. En fournissant une cohérence structurelle, le framework facilite l'organisation et permet aux développeurs de se concentrer sur ce qu'ils font le mieux : construire des algorithmes.

Défis typiques du flux de travail d'optimisation

Il existe plusieurs sources majeures de complexité lors du développement d'algorithmes OR :

Complexité des variables

• Des variables doivent souvent être ajoutées pour répondre à des exigences commerciales supplémentaires et il n'existe aucun moyen simple de les suivre pour les utiliser dans les définitions de modèles et les rapports ultérieurs.
• Les variables associées doivent être regroupées et suivies, et il n'existe pas de moyen évident de les gérer.

Complexité des contraintes

• Des contraintes doivent être ajoutées et supprimées pour prendre en charge divers scénarios et effectuer le débogage, mais il n'y a pas d'endroit évident pour ajouter ou supprimer des contraintes.
• Les contraintes sont souvent liées/dépendantes les unes des autres, et il n'existe aucun moyen naturel d'exprimer leurs relations.

Complexité des objectifs

• Les expressions objectives peuvent devenir difficiles à manier si elles ont plusieurs composants. Cela peut être exacerbé si les différents composants sont pondérés et que les pondérations doivent être ajustées en fonction des besoins de l'entreprise.

Complexité du débogage

• Il n'y a pas de moyen facile de voir les résultats du modèle pendant le développement. Un développeur doit imprimer explicitement de nouvelles variables et valeurs de contrainte pour voir les résultats. Cela conduit à un code dupliqué et à un développement plus lent.
• Lorsque l'ajout d'une contrainte rend le modèle infaisable, la raison pour laquelle la contrainte a rendu le modèle infaisable peut ne pas être évidente. Habituellement, les développeurs doivent supprimer diverses contraintes et rechercher l'incompatibilité par essais et erreurs.

HorusLP espère rendre ces défis plus gérables en fournissant une structure, des outils et des meilleures pratiques pour améliorer la productivité des développeurs et la maintenabilité des produits.

Tutoriel HorusLP : Algorithme d'optimisation et aperçu de l'API

Sans plus tarder, plongeons et voyons ce que la bibliothèque HorusLP peut faire pour vous !

Puisque HorusLP est basé sur Python et PuLP, nous voudrons les installer en utilisant pip. Exécutez ce qui suit dans votre ligne de commande :

 Pip install horuslp pulp

Une fois l'installation terminée, allons-y et ouvrons un fichier Python. Nous allons implémenter le problème du sac à dos de mon article précédent sur la recherche opérationnelle.

La bibliothèque HorusLP a une API déclarative très simple et très peu de passe-partout. Commençons par importer les classes et variables nécessaires :

 from horuslp.core.Variables import BinaryVariable # we will be using binary variables, so we will import the BinaryVariable class from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent # We will also need to import the constraint class, variable manager class, the main problem class, and the objective class to define the objective. from horuslp.core.constants import MAXIMIZE # since we're maximizing the resulting value, we want to import this constant

Une fois que nous avons importé toutes les variables, définissons les variables dont nous avons besoin pour ce problème. Pour ce faire, nous créons une sous-classe de gestionnaire de variables et la remplissons avec les variables binaires :

 class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), # the first argument is the name of the variable BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') ]

Maintenant que les variables sont définies, définissons les contraintes. Nous créons des contraintes en sous-classant la classe de contraintes principale et en implémentant sa fonction "définir".

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Dans la fonction de définition, vous pouvez demander les variables requises par leur nom. Le framework localisera la variable dans le gestionnaire de variables et la transmettra à la fonction de définition.

Une fois la contrainte implémentée, nous pouvons implémenter l'objectif. Puisqu'il s'agit d'un objectif simple, nous utiliserons ObjectiveComponent :

 class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

La fonction de définition a une configuration très similaire à la fonction de définition de la classe de contraintes. Au lieu de retourner une expression de contrainte, cependant, nous retournons une expression affine.

Maintenant que les variables, les contraintes et les objectifs sont définis, définissons le modèle :

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE

Pour construire le modèle, nous créons une classe qui est une sous-classe de la classe Problem et spécifions les variables, les objectifs, les contraintes et le sens. Avec le problème spécifié, nous pouvons résoudre le problème :

 prob = KnapsackProblem() prob.solve()

Après la résolution, nous pouvons imprimer les résultats à l'aide de la fonction print_results de la classe de problèmes. Nous pouvons également accéder à la valeur de variables spécifiques en regardant la classe result_variables .

 prob.print_results() print(prob.result_variables)

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

 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}

Vous devriez voir l'état du problème, la valeur finale des variables, la valeur de l'objectif et la valeur de l'expression de contrainte. Nous voyons également les valeurs résultantes des variables sous forme de dictionnaire.

Et voilà, notre premier problème HorusLP en 35 lignes environ !

Dans les exemples à venir, nous explorerons certaines fonctionnalités plus sophistiquées de la bibliothèque HorusLP.

Utilisation de VariableGroups

Parfois, les variables sont liées et appartiennent à un groupe logique. Dans le cas du problème du sac à dos, toutes les variables peuvent être placées dans un groupe d'objets. Nous pouvons refactoriser le code pour utiliser la variable groupe. Assurez-vous d'enregistrer le code de la section précédente, car nous y ferons référence dans les didacticiels suivants !

Modifiez les instructions d'importation comme suit :

 from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp.core.constants import MAXIMIZE

Maintenant, nous devons également modifier les déclarations de variables de sac à dos comme ceci :

 class KnapsackVariables(VariableManager): vars = [ BinaryVariableGroup('objects', [ 'camera', 'figurine', 'cider', 'horn' ]) ]

Le premier argument est le nom du groupe de variables, la seconde variable est une liste de noms pour les variables au sein de ce groupe.

Maintenant, nous devons changer les définitions des contraintes et des objectifs. Au lieu de demander les noms individuels, nous allons comme pour le groupe de variables, qui sera transmis sous forme de dictionnaire où les clés sont les noms et les valeurs sont les variables. Modifiez les définitions de contrainte et d'objectif comme suit :

 class SizeConstraint(Constraint): def define(self, objects): return 2 * objects['camera'] + 4 * objects['figurine'] + 7 * objects['cider'] + 10 * objects['horn'] <= 15 class ValueObjective(ObjectiveComponent): def define(self, objects): return 5 * objects['camera'] + 7 * objects['figurine'] + 2 * objects['cider'] + 10 * objects['horn']

Nous pouvons maintenant utiliser la même définition de problème et exécuter les commandes :

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results() print(prob.result_variables)

Vous devriez voir ceci dans votre sortie :

 KnapsackProblem: Optimal objects[camera] 0.0 objects[figurine] 1.0 objects[cider] 0.0 objects[horn] 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'objects': {'camera': 0.0, 'figuring': 1.0, 'cider': 0.0, 'horn': 1.0}}

Gérer plusieurs contraintes

Les modèles à une seule contrainte sont relativement rares. Lorsque vous travaillez avec plusieurs contraintes, il est bon d'avoir toutes les contraintes au même endroit afin qu'elles puissent être suivies et gérées facilement. HorusLP rend cela naturel.

Supposons, par exemple, que nous voulions voir comment les résultats changeraient si nous forcions le modèle à ajouter une caméra à notre sac à dos. Nous implémenterions une contrainte supplémentaire et l'ajouterions à notre définition de problème.

Revenez au modèle que nous avons implémenté dans le premier tutoriel. Ajoutez la contrainte suivante :

 class MustHaveItemConstraint(Constraint): def define(self, camera): return camera >= 1

Pour ajouter la contrainte au modèle, nous devons simplement l'ajouter à la définition du problème comme ceci :

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, MustHaveItemConstraint # just add this line :) ] sense = MAXIMIZE

Exécutez le problème et vous devriez voir le résultat suivant :

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

Vous devriez voir la nouvelle contrainte imprimée dans la sortie standard et les valeurs de variables optimales modifiées.

Gestion des contraintes dépendantes et des groupes de contraintes

Les contraintes sont souvent liées entre elles soit parce qu'elles sont dépendantes les unes des autres, soit parce qu'elles appartiennent logiquement au même groupe.

Par exemple, si vous souhaitez définir une contrainte pour limiter la somme de la valeur absolue d'un ensemble de variables, vous devez d'abord spécifier des contraintes pour exprimer les relations de valeur absolue entre les variables prévues, puis spécifier les limites de valeur absolue. Parfois, vous devez appliquer des contraintes similaires à un groupe de variables pour exprimer une relation spécifique entre les variables.

Pour exprimer ces regroupements, nous pouvons utiliser la fonction de contraintes dépendantes de nos définitions de contraintes. Pour voir comment la fonction de contrainte dépendante peut être utilisée, refactorisez la SizeConstraint du problème précédent comme ceci :

 class SizeConstraint(Constraint): dependent_constraints = [MustHaveItemConstraint] def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Et maintenant, pour tester que les contraintes dépendantes sont automatiquement implémentées, retirons MustHaveItemConstraint de la définition du problème :

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, ] sense = MAXIMIZE

Et exécutez à nouveau le code, et vous devriez voir ce qui suit dans stdout :

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

On dirait que MustHaveItemConstraint est implémenté ! Pour un exemple plus complexe d'utilisation de la contrainte dépendante, reportez-vous à l'exemple de dotation à la fin du didacticiel.

Gérer plusieurs objectifs pondérés

Souvent, lors du développement de nos algorithmes d'optimisation, nous rencontrons une expression objective composée de plusieurs parties. Dans le cadre de notre expérimentation, nous pouvons modifier la pondération de divers composants objectifs pour biaiser l'algorithme vers le résultat souhaité. Le CombinedObjective fournit un moyen clair et simple d'exprimer cela.

Supposons que l'on veuille biaiser l'algorithme pour choisir la figurine et le cidre. Refactorisons le code de la section précédente pour utiliser CombinedObjective .

Tout d'abord, importez la classe CombinedObjective comme ceci :

 from horuslp.core import CombinedObjective

Nous pouvons implémenter un composant d'objectif indépendant comme ceci :

 class ILoveCiderFigurineObjectiveComponent(ObjectiveComponent): def define(self, figurine, cider): return figurine + cider

Maintenant, nous pouvons combiner l'objectif de valeur et l'objectif de cidre/figurine en implémentant un CombinedObjective :

 class Combined(CombinedObjective): objectives = [ (ILoveCiderFigurineObjectiveComponent, 2), # first argument is the objective, second argument is the weight (ValueObjectiveComponent, 1) ]

Modifions maintenant la définition du problème comme ceci :

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = Combined constraints = [SizeConstraint] sense = MAXIMIZE

Exécutez le problème et vous devriez voir le résultat suivant :

 KnapsackProblem: Optimal camera 1.0 figurine 1.0 cider 1.0 horn 0.0 Combined: 18.00 ILoveCiderFigurineObjectiveComponent: 2.00 * 2 ValueObjectiveComponent: 14.00 * 1 SizeConstraint: 13.00 MustHaveItemConstraint: 1.00

La sortie décrira la valeur objective combinée, la valeur de chacun des composants objectifs, le poids et bien sûr la valeur de toutes les contraintes.

Recherche de contraintes incompatibles

Lors du développement d'algorithmes, nous rencontrons souvent des modèles irréalisables. Si le modèle est complexe, il peut être difficile de déterminer pourquoi le modèle est soudainement irréalisable. HorusLP dispose d'un outil pratique pour vous aider dans ces cas.

Supposons que nous ajoutions des contraintes et que nous nous retrouvions avec l'ensemble de contraintes suivant :

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 class SizeConstraint2(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 20 class MustHaveItemConstraint(Constraint): def define(self, cider): return cider >= 1 class IncompatibleConstraint1(Constraint): def define(self, camera): return camera >= 1 class IncompatibleConstraint2(Constraint): def define(self, camera): return camera <= 0

Nous avons quelques contraintes sur la taille totale des articles dans le sac à dos, une contrainte exigeant que le cidre soit dans le sac à dos et un ensemble de contraintes incompatibles qui exigent que l'appareil photo soit à la fois dans et non dans le sac à dos. (Bien sûr, dans un algorithme du monde réel, les contraintes ne sont généralement pas aussi évidentes et impliquent des relations et des contraintes de variables complexes.)

Supposons également que les contraintes soient regroupées de la manière suivante, ce qui rend peut-être la détection plus difficile :

 class CombinedConstraints1(Constraint): dependent_constraints = [SizeConstraint2, IncompatibleConstraint1] class CombinedConstraints2(Constraint): dependent_constraints = [SizeConstraint, IncompatibleConstraint2] # MustHaveItemConstraint will be included in the problem definition independently

Voici la définition du problème :

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [CombinedConstraints1, CombinedConstraints2, MustHaveItemConstraint] sense = MAXIMIZE

Exécutez le problème et vous devriez voir le résultat suivant :

 KnapsackProblem: Infeasible

Oh non! Qu'est-ce qu'on fait? Si nous utilisons la plupart des outils, nous devons nous lancer dans une session de débogage difficile où nous réduisons une par une les contraintes potentiellement conflictuelles. Heureusement, HorusLP dispose d'une fonction de recherche d'incompatibilité pour vous aider à affiner plus rapidement les contraintes incompatibles. La façon la plus simple d'utiliser la fonction de recherche d'incompatibilité est de modifier l'appel print_results ainsi :

 prob.print_results(find_infeasible=True)

Aussi simple que cela! Exécutez le code et vous devriez maintenant voir ce qui suit en sortie :

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('CombinedConstraints1', 'CombinedConstraints2')

Génial! Nous avons maintenant établi que MustHaveItemConstraint n'est pas la cause de l'infaisabilité et que le problème est dû à CombinedConstraints1 et CombinedConstraints2 .

Cela nous donne quelques informations, mais entre les contraintes combinées, il y a quatre contraintes dépendantes. Peut-on identifier lesquelles des quatre contraintes sont incompatibles ? Hé bien oui. Modifiez votre appel print_results ainsi :

 prob.print_results(find_infeasible=True, deep_infeasibility_search=True)

Cela permettra à la recherche d'infaisabilité d'étendre les contraintes dépendantes afin d'obtenir une image beaucoup plus granulaire de ce qui cause l'infaisabilité. Exécutez ceci et vous devriez voir la sortie suivante :

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('IncompatibleConstraint1', 'IncompatibleConstraint2')

Bien qu'il soit tentant d'exécuter une recherche d'infaisabilité approfondie à chaque fois, pour des problèmes réalistes avec un grand nombre de contraintes totales, la recherche d'infaisabilité approfondie peut devenir très gourmande en ressources et chronophage. Par conséquent, il est préférable d'exécuter la recherche d'infaisabilité de base pour réduire la possibilité et d'exécuter la recherche d'infaisabilité approfondie sur un sous-ensemble plus petit après avoir effectué une enquête manuelle.

Création d'algorithmes à partir de fichiers de données

Lors de la construction de modèles, nous avons rarement le luxe de coder en dur chaque contrainte et variable. Souvent, notre programme doit être suffisamment flexible pour modifier le modèle en fonction des données d'entrée. Supposons qu'au lieu d'une entrée codée en dur, nous voulions construire notre problème de sac à dos à partir du JSON suivant :

 { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 }

Nous pouvons le faire en nous appuyant sur la prise en charge par les kwargs de la fonction « définir » que nous implémentons pour les contraintes et les objectifs.

Modifions le code du problème simple du sac à dos (le problème que nous avons implémenté dans la section 1 du tutoriel). Tout d'abord, insérons la chaîne JSON dans le fichier. Bien sûr, nous le lirions normalement à partir d'une source externe, mais par souci de simplicité, gardons tout dans un seul fichier. Ajoutez ce qui suit à votre code :

 JSON = ''' { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 } '''

Assurons-nous également que notre programme serait capable de l'analyser. Ajoutez les éléments suivants à vos instructions d'importation :

 Import json

Maintenant, modifions notre code de configuration de variable ainsi :

 mip_cfg = json.loads(JSON) class KnapsackVariables(VariableManager): vars = [ BinaryVariable(i['name']) for i in mip_cfg['items'] ]

Cela définira une variable pour chacun des éléments du JSON et la nommera de manière appropriée.

Modifions les définitions de contrainte et d'objectif comme suit :

 class CapacityConstraint(Constraint): def define(self, **kwargs): item_dict = {i['name']: i['weight'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs) <= mip_cfg['capacity'] class ValueObjective(ObjectiveComponent): def define(self, **kwargs): item_dict = {i['name']: i['value'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs)

En demandant **kwargs au lieu de variables spécifiques, la fonction define obtient un dictionnaire contenant toutes les variables par nom. La fonction de définition de contrainte peut alors accéder aux variables du dictionnaire.

Remarque : Pour les groupes de variables, il s'agira d'un dictionnaire imbriqué où le premier niveau est le nom du groupe et le second niveau est le nom de la variable.

Le reste est assez simple :

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

Exécutez ce programme et vous devriez voir la sortie suivante :

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00

Définir des métriques personnalisées dans HorusLP

Parfois, à des fins de débogage et de création de rapports, nous construisons des métriques personnalisées qui ne sont pas exprimées directement dans l'objectif ou en tant que contrainte. HorusLP a une fonctionnalité pour simplifier la spécification de métriques personnalisées.

Supposons que nous voulions garder une trace du nombre de fruits que le modèle de notre section précédente mettait dans le sac à dos. Pour garder une trace de cela, nous pouvons définir une métrique personnalisée. Commençons par importer la classe de base Metrics :

 From horuslp.core import Metric

Définissons maintenant la métrique personnalisée :

 class NumFruits(Metric): name = "Number of Fruits" def define(self, apple, banana): return apple + banana

Comme vous pouvez le voir, l'interface définie ressemble beaucoup à celles de la classe de composants de contrainte et d'objectif. Si vous avez suivi le didacticiel jusqu'à présent, cela devrait vous être assez familier.

Nous devons maintenant ajouter la métrique à la définition du problème. L'interface ici encore est très similaire à la définition de contrainte :

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective metrics = [NumFruits] sense = MAXIMIZE

Exécutez ceci et vous devriez voir la sortie suivante :

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00 Number of Fruits: 1.00

Vous pouvez voir le nombre de fruits imprimés en bas.

Résoudre un problème plus complexe : deux sacs à dos

Prenons un exemple un peu plus complexe. Supposons qu'au lieu d'un seul sac à dos, nous ayons un sac et une valise. Nous avons aussi deux classes d'objets, durables et fragiles. La valise, étant plus protectrice, peut contenir à la fois des biens fragiles et durables. Le sac, quant à lui, ne peut contenir que des biens durables. Supposons également que les données des éléments soient données dans le JSON suivant :

 { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 }

Voyons comment cela change le modèle. Commençons par une page blanche car le modèle sera assez différent. Commencez par la configuration du problème :

 import json from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, Metric, ObjectiveComponent from horuslp.core.constants import MAXIMIZE JSON = ''' { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 } ''' mip_cfg = json.loads(JSON)

Configurons maintenant les variables. Nous allons configurer une variable binaire pour chaque combinaison article/contenant possible.

 class KnapsackVariables(VariableManager): vars = [ # suitcase can hold both fragile and durable goods BinaryVariableGroup('suitcase_f', [i['name'] for i in mip_cfg['fragile']]), BinaryVariableGroup('suitcase_d', [i['name'] for i in mip_cfg['durable']]), # bag can only hold durable goods. BinaryVariableGroup('bag_d', [i['name'] for i in mip_cfg['durable']]) ]

Maintenant, nous voulons implémenter des contraintes de poids pour la valise et le sac.

 class SuitcaseCapacityConstraint(Constraint): def define(self, suitcase_d, suitcase_f): fragile_weight = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_weight = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_weight + durable_weight <= mip_cfg['suitcase_capacity'] class BagCapacityConstraint(Constraint): def define(self, bag_d): durable_weight = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return durable_weight <= mip_cfg['bag_capacity']

Nous devons maintenant implémenter une contrainte légèrement plus complexe - la contrainte qui garantit qu'un article n'entre pas à la fois dans la valise et dans le sac - c'est-à-dire que si la variable "dans la valise" est 1, alors la variable "dans le sac" variable doit être nulle, et vice versa. Bien sûr, nous voulons nous assurer d'autoriser les instances où l'élément se retrouve également dans aucun des conteneurs.

Pour ajouter cette contrainte, nous devons itérer sur tous les éléments durables, trouver la variable "dans la valise" et la variable "dans le sac" et affirmer que la somme de ces variables est inférieure à 1.

On peut définir dynamiquement des contraintes dépendantes assez facilement dans HorusLP :

 class UniquenessConstraints(Constraint): def __init__(self): super(UniquenessConstraints, self).__init__() # call the dependent constraint builder function for every durable item, and push them into dependent constraints. dependent_constraints = [self.define_uniqueness_constraint(item) for item in mip_cfg['durable']] self.dependent_constraints = dependent_constraints def define_uniqueness_constraint(self, item): # classes are first-class objects in python, so we can define a class within this function and return it class UQConstraint(Constraint): # we name the constraint based on the item this is for, so that debugging is easier. name = "Uniqueness_%s" % item['name'] def define(self, suitcase_d, bag_d): # the define function can access the variables much in the same way as other functions return suitcase_d[item['name']] + bag_d[item['name']] <= 1 return UQConstraint

Maintenant que les contraintes sont définies, construisons l'objectif. L'objectif est simple la somme de toutes les valeurs que nous obtenons de tous les éléments qui sont dans des conteneurs. Ainsi:

 class TotalValueObjective(ObjectiveComponent): def define(self, suitcase_f, suitcase_d, bag_d): fragile_value = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_value_s = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) durable_value_d = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_value + durable_value_s + durable_value_d

Définissons également quelques métriques personnalisées afin que nous puissions voir en un coup d'œil combien de poids a été mis dans le sac et la valise, ainsi que la part du poids de la valise provenant de biens durables et de biens fragiles :

 class SuitcaseFragileWeightMetric(Metric): def define(self, suitcase_f): return sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) class SuitcaseDurableWeightMetric(Metric): def define(self, suitcase_d): return sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) class BagWeightMetric(Metric): def define(self, bag_d): return sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']])

Maintenant que toutes les pièces sont terminées, instancions le problème et exécutons le modèle :

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [SuitcaseCapacityConstraint, BagCapacityConstraint, UniquenessConstraints] objective = TotalValueObjective metrics = [SuitcaseDurableValueMetric, SuitcaseFragileValueMetric, BagValueMetric] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

Exécutez ceci et vous devriez voir la sortie suivante dans votre stdout :

 KnapsackProblem: Optimal suitcase_f[camera] 1.0 suitcase_f[glasses] 1.0 suitcase_f[apple] 1.0 suitcase_f[pear] 0.0 suitcase_f[banana] 1.0 suitcase_d[figurine] 0.0 suitcase_d[horn] 0.0 suitcase_d[leatherman] 0.0 bag_d[figurine] 1.0 bag_d[horn] 1.0 bag_d[leatherman] 1.0 TotalValueObjective: 32.00 SuitcaseCapacityConstraint: 15.00 BagCapacityConstraint: 17.00 Uniqueness_figurine: 1.00 Uniqueness_horn: 1.00 Uniqueness_leatherman: 1.00 SuitcaseDurableWeightMetric: 0.00 SuitcaseFragileWeightMetric: 15.00 BagWeightMetric: 17.00

Ainsi, l'appareil photo, les lunettes, la pomme et la banane vont dans la valise pour un total de 15 unités de poids, la figurine, la corne et le cuir vont tous dans le sac pour un total de 17 unités de poids. La valeur totale des marchandises s'élève à 32 unités de valeur. Fait intéressant, aucun des biens durables ne s'est retrouvé dans la valise, probablement parce que le sac avait une capacité suffisante pour contenir tous les biens durables.

Un scénario plus vaste et plus réaliste : le problème du personnel

Si vous êtes arrivé jusqu'ici dans notre tutoriel HorusLP, félicitations ! Vous avez maintenant une bonne idée de l'utilisation d'HorusLP.

Cependant, tous les exemples sur lesquels nous avons travaillé ont jusqu'à présent été des permutations du problème du sac à dos, et certaines des exigences et des paramètres sont un peu irréalistes. Travaillons ensemble sur un autre problème pour voir comment HorusLP peut résoudre un problème plus réaliste. Nous allons résoudre le problème de dotation décrit dans la seconde moitié de mon précédent article Toptal.

Pour gagner du temps, nous irons directement à la version finale du modèle (avec les conflits personnels, la réglementation du travail et les indemnités des intérimaires), mais la mise en œuvre du modèle initial plus simple est également disponible sur GitHub.

Commençons donc par poser le problème :

 from horuslp.core.Variables import BinaryVariableGroup, IntegerVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent, CombinedObjective from horuslp.core.constants import MINIMIZE shift_requirements = [1, 4, 3, 5, 2] # the number of workers we need to staff for each shift # the availability and pay rates of each of the employees workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } } # the following people can't work together, sadly. ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } # Dothraki Staffing Corp will provide us with expensive temp workers DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Définissons maintenant les variables, qui dans ce cas seraient des variables binaires déterminant si un travailleur doit travailler son quart de travail, et des variables entières déterminant le nombre de dothrakis que nous embauchons pour chaque quart de travail :

 class StaffingVariables(VariableManager): vars = [] def __init__(self): # like dependent constraints, we can dynamically define variables in the init function super(StaffingVariables, self).__init__() # regular workers varkeys = [] for employee, availability_info in workers.items(): for shift in availability_info['availability']: varkeys.append((employee, shift)) self.vars.append(BinaryVariableGroup('employee_shifts', varkeys)) # dothrakis dothraki_keys = [i for i in range(len(shift_requirements))] self.vars.append(IntegerVariableGroup('dothraki_workers', dothraki_keys, 0, DOTHRAKI_COST))

Maintenant, implémentons la contrainte qui nous oblige à disposer de suffisamment de personnel pour chaque quart de travail :

 class SufficientStaffingConstraint(Constraint): # we need to staff people sufficiently dependent_constraints = [] def __init__(self): super(SufficientStaffingConstraint, self).__init__() for shift_num, shift_req in enumerate(shift_requirements): self.dependent_constraints.append(self.build_shift_constraint(shift_num, shift_req)) def build_shift_constraint(self, sn, sr): class ShiftConstraint(Constraint): name = "shift_requirement_%d" % sn def define(self, employee_shifts, dothraki_workers): variables = [val for key, val in employee_shifts.items() if key[1] == sn] variables.append(dothraki_workers[sn]) return sum(variables) >= sr return ShiftConstraint

Maintenant, nous devons implémenter les contraintes empêchant des personnes spécifiques de travailler ensemble :

 class PersonalConflictsConstraint(Constraint): # some people can't work together dependent_constraints = [] def __init__(self): super(PersonalConflictsConstraint, self).__init__() for person_1, person_2 in ban_list: for shift in range(len(shift_requirements)): self.dependent_constraints.append(self.build_conflict_constraint(person_1, person_2, shift)) def build_conflict_constraint(self, p1, p2, s): class ConflictConstraint(Constraint): name = "Conflict_%s_%s_%d" % (p1, p2, s) def define(self, employee_shifts): if (p1, s) in employee_shifts and (p2, s) in employee_shifts: return employee_shifts[p1, s] + employee_shifts[p2, s] <= 1 return True # returning true will make the constraint do nothing return ConflictConstraint

And finally the labor standards constraint. We'll implement this one slightly differently for demonstrative purposes:

 class LaborStandardsConstraint(Constraint): # we can make someone work more than two shifts a day. dependent_constraints = [] def __init__(self): super(LaborStandardsConstraint, self).__init__() for worker in workers.keys(): # we don't need a constraint builder function, but in those circumstances # we need to set the needed values as class variables and refer to them # via the self keyword due to how python's closure system works class LaborConstraint(Constraint): # we can't use worker directly! wk = worker name = "labor_standard_%s" % worker def define(self, employee_shifts): # we need to access the worker using self. Change self.wk to worker to see # why we need to do this worker_vars = [var for key, var in employee_shifts.items() if key[0] == self.wk] return sum(worker_vars) <= 2 self.dependent_constraints.append(LaborConstraint)

And now let's set up the objectives. The dothraki cost and regular employee costs are calculated very differently, so we'll put them in separate objective components:

 class CostObjective(ObjectiveComponent): # this is the cost function for all the named workers def define(self, employee_shifts, dothraki_workers): costs = [ workers[key[0]]['cost'] * var for key, var in employee_shifts.items() ] return sum(costs) class DothrakiCostObjective(ObjectiveComponent): # don't forget the Dothrakis def define(self, dothraki_workers): dothraki_costs = [ dothraki_workers[sn] * DOTHRAKI_COST for sn in dothraki_workers ] return sum(dothraki_costs) class TotalCostObjective(CombinedObjective): objectives = [ (CostObjective, 1), (DothrakiCostObjective, 1) ]

And now we can define and run the problem:

 class StaffingProblem(Problem): variables = StaffingVariables objective = TotalCostObjective constraints = [SufficientStaffingConstraint, PersonalConflictsConstraint, LaborStandardsConstraint] sense = MINIMIZE # we're minimizing this time, not maximizing. if __name__ == '__main__': prob = StaffingProblem() prob.solve() prob.print_results()

Run the script and you should see the following:

 StaffingProblem: Optimal employee_shifts[('Melisandre', 0)] 0.0 employee_shifts[('Melisandre', 1)] 1.0 employee_shifts[('Melisandre', 4)] 1.0 employee_shifts[('Bran', 1)] 0.0 employee_shifts[('Bran', 2)] 1.0 employee_shifts[('Bran', 3)] 1.0 employee_shifts[('Bran', 4)] 0.0 employee_shifts[('Cersei', 2)] 0.0 employee_shifts[('Cersei', 3)] 0.0 employee_shifts[('Daenerys', 3)] 1.0 employee_shifts[('Daenerys', 4)] 0.0 employee_shifts[('Theon', 1)] 1.0 employee_shifts[('Theon', 3)] 1.0 employee_shifts[('Theon', 4)] 0.0 employee_shifts[('Jon', 0)] 0.0 employee_shifts[('Jon', 2)] 1.0 employee_shifts[('Jon', 4)] 0.0 employee_shifts[('Tyrion', 1)] 1.0 employee_shifts[('Tyrion', 3)] 1.0 employee_shifts[('Tyrion', 4)] 0.0 employee_shifts[('Jaime', 1)] 1.0 employee_shifts[('Jaime', 2)] 0.0 employee_shifts[('Jaime', 4)] 1.0 employee_shifts[('Arya', 0)] 1.0 employee_shifts[('Arya', 1)] 0.0 employee_shifts[('Arya', 3)] 1.0 dothraki_workers[0] 0.0 dothraki_workers[1] 0.0 dothraki_workers[2] 1.0 dothraki_workers[3] 0.0 dothraki_workers[4] 0.0 TotalCostObjective: 335.00 CostObjective: 290.00 * 1 DothrakiCostObjective: 45.00 * 1 shift_requirement_0: 1.00 shift_requirement_1: 4.00 shift_requirement_2: 3.00 shift_requirement_3: 5.00 shift_requirement_4: 2.00 Conflict_Jon_Cersei_2: 1.00 Conflict_Jon_Jaime_2: 1.00 Conflict_Jon_Jaime_4: 1.00 Conflict_Daenerys_Cersei_3: 1.00 Conflict_Daenerys_Jaime_4: 1.00 Conflict_Arya_Jaime_1: 1.00 Conflict_Arya_Cersei_3: 1.00 Conflict_Arya_Melisandre_0: 1.00 Conflict_Arya_Melisandre_1: 1.00 Conflict_Jaime_Cersei_2: 0.00 labor_standard_Melisandre: 2.00 labor_standard_Bran: 2.00 labor_standard_Cersei: 0.00 labor_standard_Daenerys: 1.00 labor_standard_Theon: 2.00 labor_standard_Jon: 1.00 labor_standard_Tyrion: 2.00 labor_standard_Jaime: 2.00 labor_standard_Arya: 2.00

If you compare this with the problem we implemented in the previous tutorial, you should see that the results match.

Emballer

Congratulations for making it through our first HorusLP tutorial! You're now a competent practitioner of HorusLP.

I hope that this article convinced you of the benefits of architecting your MIP models, and that you will make use of HorusLP in your coming projects. You can find the HorusLP source code, as well as the code for all the tutorials, on GitHub. Additional HorusLP documentation and a tutorial page will be added to GitHub very soon.

As HorusLP is a fairly new project, we would love to hear from you and incorporate your input. If you have any questions, comments, or suggestions, please drop me a line either through Toptal or using the contact information you can find on GitHub. I hope to hear from you soon!