Programmation en nombres entiers mixtes : un guide pour la prise de décision computationnelle

La recherche opérationnelle, la science de l'utilisation des ordinateurs pour prendre des décisions optimales, a été utilisée et appliquée dans de nombreux domaines du logiciel. Pour donner quelques exemples, les entreprises de logistique l'utilisent pour déterminer l'itinéraire optimal pour se rendre d'un point A à un point B, les compagnies d'électricité l'utilisent pour déterminer les calendriers de production d'électricité et les entreprises manufacturières l'utilisent pour trouver des modèles de personnel optimaux pour leurs usines.

Aujourd'hui, nous allons explorer le pouvoir de la recherche opérationnelle en parcourant un problème hypothétique. Plus précisément, nous utiliserons la programmation en nombres entiers mixtes (MIP) pour déterminer le modèle de dotation optimal pour une usine hypothétique.

Algorithmes de recherche opérationnelle

Avant de nous plonger dans notre exemple de problème, il est utile de passer en revue certains concepts de base de la recherche opérationnelle et de comprendre un peu les outils que nous utiliserons aujourd'hui.

Algorithmes de programmation linéaire

La programmation linéaire est une technique de recherche opérationnelle utilisée pour déterminer le meilleur résultat dans un modèle mathématique où l'objectif et les contraintes sont exprimés sous la forme d'un système d'équations linéaires. Un exemple de modèle de programmation linéaire pourrait ressembler à ceci :

 Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2)

Dans notre exemple très simple, nous pouvons voir que le résultat optimal est 5, avec a = 2 et b = 3. Bien qu'il s'agisse d'un exemple plutôt trivial, vous pouvez probablement imaginer un modèle de programmation linéaire qui utilise des milliers de variables et des centaines de contraintes. .

Un bon exemple pourrait être un problème de portefeuille d'investissement, où vous pourriez vous retrouver avec quelque chose comme ci-dessous, en pseudo-code :

 Maximize <expected profit from all stock investments> Subject to: <investment in the technology sector must be between 10% - 20% of portfolio> <investment in the consumer staples must not exceed investment in financials> Etc. ...

Ce qui serait plutôt complexe et difficile à résoudre à la main ou par essais et erreurs. Les logiciels de recherche opérationnelle utiliseront plusieurs algorithmes pour résoudre ces problèmes rapidement. Si vous êtes intéressé par les algorithmes sous-jacents, je vous recommande de vous renseigner sur la méthode du simplexe ici et la méthode du point intérieur ici.

Algorithmes de programmation d'entiers

La programmation en nombres entiers est comme la programmation linéaire avec une allocation supplémentaire pour que certaines ou toutes les variables soient des valeurs entières. Bien que cela puisse ne pas sembler être une grande amélioration au début, cela nous permet de résoudre de nombreux problèmes qui auraient pu rester non résolus en utilisant uniquement la programmation linéaire.

L'un de ces problèmes est le problème du sac à dos, où on nous donne un ensemble d'éléments avec des valeurs et des poids assignés et on nous demande de trouver la combinaison d'éléments de valeur la plus élevée que nous pouvons insérer dans notre sac à dos. Un modèle de programmation linéaire ne pourra pas résoudre ce problème car il n'y a aucun moyen d'exprimer l'idée que vous pouvez mettre un élément dans votre sac à dos ou non, mais vous ne pouvez pas mettre une partie d'un élément dans votre sac à dos - chaque variable est une variable continue. variable!

Un exemple de problème de sac à dos peut avoir les paramètres suivants :

Et le modèle MIP ressemblera à ceci :

 Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint)

La solution optimale, dans ce cas, est a=0, b=1, c=0, d=1, la valeur de l'item total étant 17.

Le problème que nous allons résoudre aujourd'hui nécessitera également une programmation en nombres entiers puisqu'un employé d'une usine peut être programmé pour un quart de travail ou non. Par souci de simplicité, vous ne pouvez pas programmer un employé pour les 2/3 d'un quart de travail dans cette usine.

Pour rendre possible la programmation en nombres entiers, plusieurs algorithmes mathématiques sont utilisés. Si vous êtes intéressé par les algorithmes sous-jacents, je vous recommande d'étudier ici l'algorithme des plans de coupe et l'algorithme de branchement et de liaison.

Exemple de problème : planification

Description du problème

Aujourd'hui, nous allons explorer le problème de la dotation en personnel d'une usine. En tant que direction de l'usine, nous voudrons minimiser les coûts de main-d'œuvre, mais nous voulons assurer une couverture suffisante pour chaque quart de travail afin de répondre à la demande de production.

Supposons que nous ayons cinq équipes avec les demandes de personnel suivantes :

Et, supposons que nous ayons les travailleurs suivants :

Pour garder le problème simple, supposons pour le moment que la disponibilité et le coût sont les seules préoccupations.

Nos outils

Pour le problème d'aujourd'hui, nous allons utiliser un logiciel open source appelé CBC. Nous nous interfacerons avec ce logiciel en utilisant PuLP, qui est une bibliothèque de modélisation de recherche opérationnelle populaire pour Python. Vous pouvez trouver des informations à ce sujet ici.

PuLP nous permet de construire des modèles MIP de manière très Pythonique et s'intègre parfaitement au code Python existant. Ceci est très utile car certains des outils de manipulation et d'analyse de données les plus populaires sont écrits en Python, et la plupart des systèmes de recherche opérationnelle commerciaux nécessitent un traitement approfondi des données avant et après l'optimisation.

Pour démontrer la simplicité et l'élégance de PuLP, voici le problème du sac à dos de plus tôt et résolu dans PuLP :

 import pulp as pl # declare some variables # each variable is a binary variable that is either 0 or 1 # 1 means the item will go into the knapsack a = pl.LpVariable("a", 0, 1, pl.LpInteger) b = pl.LpVariable("b", 0, 1, pl.LpInteger) c = pl.LpVariable("c", 0, 1, pl.LpInteger) d = pl.LpVariable("d", 0, 1, pl.LpInteger) # define the problem prob = pl.LpProblem("knapsack", pl.LpMaximize) # objective function - maximize value of objects in knapsack prob += 5 * a + 7 * b + 2 * c + 10 * d # constraint - weight of objects cannot exceed 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 status = prob.solve() # solve using the default solver, which is cbc print(pl.LpStatus[status]) # print the human-readable status # print the values print("a", pl.value(a)) print("b", pl.value(b)) print("c", pl.value(c)) print("d", pl.value(d))

Exécutez ceci et vous devriez obtenir le résultat :

 Optimal a 0.0 b 1.0 c 0.0 d 1.0

Passons maintenant à notre problème d'horaire !

Codage de notre solution

Le codage de notre solution est assez simple. Tout d'abord, nous voudrons définir nos données :

 import pulp as pl import collections as cl # data shift_requirements = [1, 4, 3, 5, 2] 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 } }

Ensuite, nous voudrons définir le modèle :

 # define the model: we want to minimize the cost prob = pl.LpProblem("scheduling", pl.LpMinimize) # some model variables cost = [] vars_by_shift = cl.defaultdict(list) for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%s" % (worker, shift), 0, 1, pl.LpInteger) vars_by_shift[shift].append(worker_var) cost.append(worker_var * info['cost']) # set the objective to be the sum of cost prob += sum(cost) # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum(vars_by_shift[shift]) >= requirement

Et maintenant on lui demande juste de résoudre et d'imprimer les résultats !

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var.name for var in vars if var.varValue == 1], }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']))

Une fois le code exécuté, vous devriez voir les résultats suivants :

 Result: Optimal Shift: 0 workers: Arya_0 Shift: 1 workers: Melisandre_1, Bran_1, Theon_1, Arya_1 Shift: 2 workers: Bran_2, Jon_2, Jaime_2 Shift: 3 workers: Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3 Shift: 4 workers: Bran_4, Theon_4

Montez un peu la difficulté : Contraintes supplémentaires

Même si le modèle précédent était intéressant et utile, il ne démontre pas pleinement la puissance de la programmation en nombres entiers mixtes. Nous pourrions aussi facilement écrire une boucle for pour trouver les x travailleurs les moins chers pour chaque quart de travail, où x est le nombre de travailleurs nécessaires pour un quart de travail. Pour démontrer comment MIP peut être utilisé pour résoudre un problème qui serait difficile à résoudre de manière impérative, examinons ce qui se passerait si nous ajoutions quelques contraintes supplémentaires.

Contraintes supplémentaires

Supposons qu'en raison de la nouvelle réglementation du travail, aucun travailleur ne puisse être affecté à plus de 2 équipes. Pour tenir compte de l'augmentation du travail, nous avons recruté l'aide de Dothraki Staffing Group, qui fournira jusqu'à 10 travailleurs Dothraki pour chaque quart de travail à un taux de 40 $ par quart de travail.

Supposons également qu'en raison de certains conflits interpersonnels en cours à l'extérieur de notre usine, Cersei et Jaime ne soient pas en mesure de travailler aux côtés de Daenerys ou de Jon. De plus, Jaime et Cersei sont incapables de travailler ensemble. Enfin, Arya, qui a des relations interpersonnelles particulièrement complexes, est incapable de travailler dans le même quart de travail avec Jaime, Cersei ou Melisandre.

L'ajout de ces deux nouvelles contraintes et ressources ne rend en aucun cas le problème insoluble par des moyens impératifs, mais il rend la solution beaucoup plus difficile, car il faudra tenir compte des coûts d'opportunité de l'affectation d'un travailleur à un quart de travail particulier.

Solution

Avec la programmation en nombres entiers mixtes, cependant, c'est beaucoup plus facile. Nous devons simplement modifier notre code comme suit :

Définissez la liste des bannissements et quelques contraintes :

 ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Remplir les variables pour implémenter les contraintes d'interdiction et de décalage maximum :

 for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%d" % (worker, shift), 0, 1, pl.LpInteger) # store some variable data so we can implement the ban constraint var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # store vars by variable so we can implement the max shift constraint vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost'])

Ajoutez les variables Dothraki :

 for shift in range(len(shift_requirements)): dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger) cost.append(dothraki_var * DOTHRAKI_COST) dothrakis_by_shift[shift] = dothraki_var

Nous aurons également besoin d'une boucle légèrement modifiée pour calculer les exigences de décalage et d'interdiction :

 # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # set the ban requirements for shift, vars in vars_by_shift.items(): for var1 in vars: for var2 in vars: worker_pair = var1[1][0], var2[1][0] if worker_pair in ban_list: prob += var1[0] + var2[0] <= 1 # set the labor standards: for worker, vars in vars_by_worker.items(): prob += sum(vars) <= 2

Et enfin, pour imprimer les résultats :

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var[1][0] for var in vars if var[0].varValue == 1], "dothrakis": dothrakis_by_shift[shift].varValue }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']), 'dothrakis hired:', int(result['dothrakis']))

Et nous devrions être prêts à partir. Exécutez le code et vous devriez voir la sortie ci-dessous :

 Result: Optimal Shift: 0 workers: Arya dothrakis hired: 0 Shift: 1 workers: Melisandre, Theon, Tyrion, Jaime dothrakis hired: 0 Shift: 2 workers: Bran, Jon dothrakis hired: 1 Shift: 3 workers: Bran, Daenerys, Theon, Tyrion, Arya dothrakis hired: 0 Shift: 4 workers: Melisandre, Jaime dothrakis hired: 0

Et voilà, un résultat qui respecte la liste des travailleurs interdits, suit la réglementation du travail et utilise judicieusement les travailleurs Dothraki.

Conclusion

Aujourd'hui, nous avons exploré l'utilisation de la programmation mixte en nombres entiers pour prendre de meilleures décisions. Nous avons discuté des algorithmes et techniques sous-jacents utilisés dans la recherche opérationnelle et examiné un exemple de problème représentatif de la manière dont la programmation en nombres entiers mixtes est utilisée dans le monde réel.

J'espère que cet article vous a inspiré pour en savoir plus sur la recherche opérationnelle et vous a fait réfléchir à la manière dont cette technologie peut être appliquée à vos projets. Nous n'avons vraiment vu que la pointe de l'iceberg en ce qui concerne le monde passionnant des algorithmes d'optimisation et de la recherche opérationnelle.

Vous pouvez trouver tout le code lié à cet article sur GitHub. Si vous souhaitez en discuter davantage, partagez vos commentaires ci-dessous!