Discussion :

[zghezal]

Bonjour à tous,

J'ai un plus ou moins gros soucis sur lequel j'espère vous pourrez m'apporter des indications. Je ne sais pas si je post dans le bon répertoire.

J'expose dans un premier temps le problème. Puis, je décris mon ébauche de résolution bien qu'encore très limité. Par ailleurs, SI vous voyez d'autre moyen de résoudre ce problème, je suis tout ouïe.

Problème:

Un exemple de données est dans le fichier joint.

Ma données est tout simplement une table.
Chaque observation contient un identifiant unique, clé de ma table. puis quelques caractéristiques intrinsèques liées a cette identifiant.
Enfin, pour l'une des variables spécifiques, nous avons l'historique des mesures de la variable dans le temps dispatché annuellement sur plusieurs colonnes. Cela représente le flux de la variable au niveau de l'identifiant.

Pour rendre plus concret. Imaginons un monde post apocalyptique où on fait très attention a la gestions de l'eau. On a un parc de différents points d'eau (identifiants unique), disons trois points A0, B0 et C0. la gestion est confiée à trois personnes différentes (disons Bob, Snoopy et Pierrot) et chacune est responsable de son point d'eau. Jusqu'ici tout va bien.

Seulement les points d'eau communiquent entre eux. et du jour au lendemain le point A0 peut etre vidé dans un autre point d'eau disons A1 avec une petite perte d'eau. quant à B0, le volume d'eau est vidé dans B11 et B12. Cette fois en cumulant les deux volumes, on a un petit peu plus en terme de quantité.

Il se peut même qu'a partir d'une certaine date, Bob se voit accorder la gérance supplémentaire d'un nouveau point d'eau Z.

Il se peut aussi qu'un beau jour, pour xY raison, A1 et C0 soit versé dans le même point d'eau AC0 toujours avec une legere perte ou gain.

Imaginez après quelques années de gestion, on nous demande d'évaluer comment les quantités A0, B0 et C0 ont été géré. Mais on rencontre un problème, les seuls données dont on dispose sont le nom des point d'eau qui ont été utilisé avec leur historique de volume. nous ne savons plus qui c'est occupé de tel ou tel point d'eau ni des transferts de volume. Avec ces seules données, on voudrait reconstruire la colonne de provenance tel que: A0->A1; A1->AC0;
B0->B11
B0->B12
Z quantité à part
C0->AC0
L'exemple inclus les cas décrits.
Une contrainte supplémentaire est que les réservoirs sont à usage unique. une fois vidé, ils ne sont plus utilisé.

L'idée de la solution est intuitif et simple dans le cas de l'exemple mais la solution devra être utiliser sur des milliers de tables dont le nombre de reservoir pourra aller jusqu'a quelques centaine et la profondeur historique jusqu'a 160 mois a une frequence mensuelle.

Résolution:

- solution simple:
regarder quand les réservoirs se vident et ou ils sont susceptibles d'avoir été transférés en se basant sur la stabilité du niveau volumétrique en prenant en compte à la fois les contraintes techniques et à la fois les caractéristiques (qui peuvent porter de l'information pertinente quand disponible). facile a dire ^^ mais je peche un peu ici.

D'abord la solution pour un cas ou on a 3 reservoirs initiaux et 8 réservoirs au globale aura la forme d'une matrice tel que:

	A0	B0	C0	A1	B11	B12	AC0	K	C1
A0	1	0	0	1	0	0	1	0	0
B0	0	1	0	0	1	1	0	0	0
C0	0	0	1	0	0	0	1	0	1
NA (nouvel assignation)	0	0	0	0	0	0	0	1	0

La matrice contient des 1 lorsques le réservoir d'une colonne donnée a contenu un volume issue du reservoir de la ligne correspondante.
Des contraintes portent sur le contenu de la matrice :
- soit directement par exemple par rapport aux caractéristiques :l'eau contenu dans un réservoir homologué en L ne peut être contenu que dans un reservoir homologué L ou info absente.
- soit indirectement par exemple le transfert ne peut durer que deux mois maximun entre deux réservoirs. ie que le reservoir de transfert a un reservoir ne peut etre rechercher que parmi ceux qui contiennent Au moins une goutte d'eau deux mois apres.

Une fois ces limites/règles établies, Il reste selon moi à chercher la solution optimale ie (je crois qu'on appelle ca l'optimun de pareto) minimiser au mieux la fonction de stabilité de notre data D et de notre solution potentielle S d'une part et minimiser le nombre de solution ranger en nouvel assignation d'autre part.

La fonction de stabilité est plus ou moins la volatilité de ma variable volume au cours du temps. Voila ou j'en suis.

Techniquement, je pensais, pour gérer ces contraintes simplement à de la programmation par contraintes, mais je ne connais pas du tout ce sujet donc je suis assez preneur de conseils qui pourrait m'orienter vers une solution technique efficace et gratos . et si il y a beaucoup plus simple je suis aussi biensur preneur.

Il faut aussi savoir que on a un jeu de test ou la solution est connue



Merci

[Flodelarab]

Bonjour

Ton message ne contient pas de point d'interrogation. C'est souvent une indication que tu n'as pas encore cerné ce que tu cherches, avant de le chercher.

Ma données est tout simplement une table.
Chaque observation contient un identifiant unique, clé de ma table. puis quelques caractéristiques intrinsèques liées a cette identifiant.

Tu as une table ? Et tu nous dis comment elle est faite ? Super. On n'aurait préféré que tu dises ce qu'il y a dedans. C'est le niveau du réservoir ? Ou l'indication des flux entre réservoirs ?

Perso, je n'ouvre pas les fichiers virussés des inconnus sur Internet. Un copié/collé aurait été mieux.

Imaginez après quelques années de gestion, on nous demande d'évaluer comment les quantités A0, B0 et C0 ont été géré.

Cette phrase semble être la question.
Si 100 réservoirs donnent 1 litre et que 100 réservoirs gagnent 1 litre, tu as 100! (100 factorielle) possibilités. Laisse tomber. C'est impossible dans l'absolu. Si tes réservoirs sont des comptes en banque, on peut espérer que les sommes ne soient pas rondes et donc différentes. Sinon, pfff.

Pour info :
100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

[zghezal]

hello,

Désolé si ca n'est pas clair. t'as compris pas mal de truc mais pour je vais essayer de ré-expliquer, je vais poser la problématique du problème.

- Le décor est planté plus en détail dans le message précédent mais pour résumé: on a des quantités d'eau qui migrent de réservoir en réservoir et on perds l'information sur les transferts qui ont eu lieu. On a seulement le relevé des réservoirs au cours du temps. En prenant seulement en compte le relevé des réservoirs et la connaissance des quantités initiales, comment déduire les transferts qui ont eu lieu et ainsi en déduire l'évolution des réserves initiales de la manière la plus probable?
Les variations de volumes importantes se font la plupart du temps dans la phase où l'eau est stocké dans un réservoir et non pas lors des transfert. On peut ajouter comme hypothèse que les quantités initiales sont significativement différentes 2 a 2.
(c'est pour ton commentaire sur le 100!).

-Mes questions:

-> est ce que la piste que je propose vous semble convenir? A savoir définir des contraintes sur les potentiels transferts qui ont eu lieu et définir une fonction d'objectif a minimiser qui va mesurer les variations de volume lors des transferts liés a une potentielle solution.

-> si la piste convient, connaissez vous une librairie de calcul adapté à la problématique? j'ai pensé a utiliser optimization par contrainte : OR tools ou python constraints

-> Si vous reconnaissez dans le problème que je pose une classe de problème qui ait connu et pour laquelle il existe des solutions , je suis intéressé.




voila le virus. Les quantités reportées correspondent aux niveaux des réservoirs.

merci encore

[valentin03]

Il paraît simple de lire (chercher) quels réservoirs ont transférés en moins quand l'un a varié en plus et d'enregistrer.

[tbc92]

Il se peut aussi qu'un beau jour, pour xY raison, A1 et C0 soit versé dans le même point d'eau AC0 toujours avec une legere perte ou gain.

Ca veut dire que si à un moment , AC0 se remplit, forcément, A1 et C0 se vident ? On ne peut pas avoir A1 qui se déverse vers AC0, alors que C0 garderait son contenu ?

Et de façons plus générale, quand un réservoir se vide, il se vide forcément complètement ? On ne peut pas avoir la moitié de A0 qui part vers un réservoir , et l'autre moitié vers un autre réservoir ? En fait non, la réponse est dans ton fichier de données, l réservoir M0 passe progressivement de 50 à 45 puis 0.

Dans ce fichier Exemple, en 2003, la somme des différents réservoirs donne 3357, alors que sur les années précédentes, cette somme donnait 3180 ou 3182. C'est normal ?


Enfin, tu parles de solution la plus probable ... Je ne sais pas trop si cette expression a un sens dans ce contexte. Je parlerais plutôt de solution avec le moins de transferts.