Discussion :

[PsykotropyK]

Bonjour,

J'ai un problème sur une optimisation linéaire (linprog) dû à ma matrice de contrainte qui est trop grande et cause un dépassement de mémoire. Ma matrice de contrainte fait actuellement une dimension de l'ordre de 600k x 900k (et encore c'est une matrice creuse).

Déjà désolé si je ne suis pas très clair, si des gens pensent qu'il est possible d'apporter une solution, je développerais un peu mieux demain, depuis mon boulot, avec le code de génération des matrices de contraintes.

Aussi, je n'explique qu'une partie des contraintes ici, celle de l'affectation dans le temps, mais j'en ai d'autre qui limite la valeur min/max affecté, la valeur min/max trouvé, etc... Je n'explique pas non plus le vecteur de la fonction d'optimisation.

L'idée globale de la partie de la matrice à réduire est de trouver d'une part des valeurs (taille nt), puis de les affecter (taille nx) dans le temps (i pas de temps).

Je crée donc une matrice qui a (nt + i * nx) colonnes. L'idée est d'avoir à la sortie de linprog des x tel que de x_0 à x_nt les montants trouvés et ensuite de x_nt+1 à x_(nt+i*nx) les montant affectés.

Comme sur un pas de temps je ne peux pas affecter plus que la valeur trouvé je suis obligé d'avoir une contrainte qui vérifie que -somme(x_trouvé) + somme(x_affecté_en_i) < 0 et je dois créer une matrice par pas de temps (que je concatène àpres A = [A1; A2; ...; Ai]. C'est cette partie qui me crée trop de ligne de contrainte.

L'idéal serait de pouvoir écrire -somme(i * x_trouvé) + somme(x_affecté) < 0 mais en faisant ça il est susceptible de trop affecter sur un pas de temps donné tout en respectant la contrainte. L'idéal serait de pouvoir mettre un upper bound dans mon linprog, mais celui-ci serait fonction du résultat de linprog...

Comme je sais que c'est pas très parlant comme ça imaginons un cas :

j'ai deux valeur à trouver, affectable sur 3 données. Pour le pas de tps i=1 j'ai un matrice qui ressemble à:

|nt | nx1 | nx2 |...| nxi
-1 0 1 1 0 0 0 0 ... 0 0 0
0 -1 0 1 1 0 0 0 ... 0 0 0

pour i = 2

|nt | nx1 | nx2 |...| nxi
-1 0 0 0 0 1 1 0 ... 0 0 0
0 -1 0 0 0 0 0 1 ... 0 0 0 => on voit que l'affectation possible n'est pas la même.


Vu comme ça, ça me semble insoluble, à part si par miracle, j'ai demain matin un PC tout neuf à mon bureau avec 3x plus de RAM... Enfin si la seul possibilité que je vois c'est d'arriver à réduire ma quantité de donnée envoyé à Matlab, mais dans les réduction simple ça à déja été fait (la première matrice faisait 900k x 2000k)

Désolé d'être aussi peu clair, si quelqu'un à envie de s'intéresser un poil au problème qu'il me le dise, je sortirais l'artillerie lourde demain (i.e. la génération de mes sparse matrix)

[Jerome Briot]

Ma matrice de contrainte fait actuellement une dimension de l'ordre de 600k x 900k (et encore c'est une matrice creuse).

Tu donnes la taille approximative de la matrice pleine équivalente la, non ?
Mais as-tu une idée du nombre de valeurs non-nulles dans ta matrice ?

Sinon je vais peut être dire une bêtise mais... vu que ton problème est linéaire, n'est-il pas possible de le résoudre par morceau ou par sous-système ?