Lors de la formalisation des problèmes de LP, il faut souvent traiter des variables multi-index. Lorsque vous travaillez avec des problèmes de grandes dimensions, c'est franchement une chose courante.
Les interrelations de ces variables multi-indices dans la fonction objectif (la forme linéaire est également un critère d'optimisation linéaire) et les contraintes (sous la forme d'égalités et d'inégalités linéaires) doivent être générées par programme. Lorsque vous travaillez avec PuLP (port de bibliothèque LP pour Python), deux approches principales pour une telle génération sont utilisées:
- Générer explicitement la matrice A (matrice de contraintes) à l'aide des générateurs de liste Python. Par exemple, comme ceci: Problème de Sudoku
- Génération de variables symboliques avec liaison aux index via des dictionnaires sous une forme implicite. Cela peut être fait manuellement via un dict ou en utilisant un plugin PuLP
Le problème LP classique de presque toutes les dimensions peut être facilement formalisé de l'une de ces manières, mais lors du développement de nouvelles structures de contraintes (en particulier lorsque la logique des interrelations de variables devient plus compliquée, de nouvelles variables de sens apparaissent, certains indices sont abandonnés ou de nouveaux indices sont introduits) agrégation / décomposition de groupes de variables, etc.) nécessite un suivi facile des variables multi-index dans le code du programme Python lui-même, ce qui est directement absent des approches ci-dessus.
Pour résoudre ce problème, il est proposé d'utiliser l'add -on PuLP-MiA (lien vers le référentiel avec une brève description de la fonctionnalité).
L'auteur est loin de penser qu'il s'agit d'une solution à tous les problèmes qui se posent dans la formalisation et la solution des problèmes de LP avec une structure complexe de restrictions, cependant, dans de nombreuses années de pratique (en particulier lorsque la modification se produit avec de longs intervalles de temps), l'approche a fait ses preuves, principalement grâce aux commodités suivantes:
- La création / liaison aux variables existantes se fait automatiquement
- Association explicite d'un nom de variable et de ses indices
- Nom de variable - chaîne arbitraire
- Index - valeurs numériques
- Le nombre d'index est conditionnellement illimité (il peut ne pas y avoir d'index du tout)
- Les résultats de la résolution du problème LP sont affichés sous la forme d'un dictionnaire, où les clés sont des variables multi - index différentes de zéro (le comportement peut être modifié)
Peut-être que l'addon sera très utile pour quelqu'un dans une recherche à long terme des opérations. Licence MIT. Il est installé traditionnellement via pip .
PS Pour ceux qui ont fini de lire, ce sera encore petit
exemple de formation d'une série de restrictions))
from itertools import product
from pulp_mia import Task, Constraint
i_set = list(range(5))
j_set = list(range(5))
m_set = list(range(2))
g_set = list(range(4))
s_set = list(range(5))
k_set = list(range(5))
task = Task(debug=True)
for i, m, g, s, k in product(i_set, m_set, g_set, s_set, k_set):
a_new = Constraint('<=')
for j in j_set:
a_new.setCoeff(('x', i, j, m, g, s, k), 1)
a_new.setBValue(1)
task.addConstraint(a_new)
print(task)
#TASK info:
# NAME: test-task
# SIZE: 5000 x 1000
(pour le reste, voir la brève description de l'addon )
PPS oui, quelque part sous le capot vit un dictionnaire ordinaire.