Bonjour,
J'ai des programmes linéaires à un format aplati, autrement dit une
suite d'égalités ou inégalités
2 * x_1 + 3 * y_1 + 7 * z_1 <= 1
2 * x_2 + 2 * y_2 + 5 * z_2 <= 2
par exemple la MIPLIB 2010
http://miplib.zib.de/
Ces problèmes ont en réalité une sémantique qui a été détruite en
passant à un format plat (production, emploi du temps, dimensionnement
de réseaux, etc)
Il me faut les passer à un format qui a un peu plus de sémantique :
indexes (d'entiers), tableaux associatifs, inégalités indexées
indexA = 1, 2, ..., 153
indexB = 3, 5, 7, ... , 121
a[1][3] = 100
a[2][3] = 154
forall (i in indexA) a[i] * x[i] + b[i] * y[i] + c[i] * z[i] <= 2
forall (i in indexB, j in indexA) t[i] + j <= r[j]
Il s'agit donc de "desaplatir" inégalités linéaires pour en faire des
"forall" indexés.
Pour ce faire il faut "reconnaitre" la structure par exemple
2 * x_2 + 2 * y_3 <= 1
3 * x_3 + 4 * y_4 <= 2
a l'air d'être n * x[n] + (n + 1) * y[n + 1] <= (n - 1)
C'est une sorte de problème de compression symbolique, mais j'avoue ne
pas savoir par où commencer.
Diego Olivier