Synchronisation hypermédia: modélisation et optimisation par les graphes

L'utilisation croissante d'Internet et des documents hypermedia rend cruciale la nécessité de disposer d'algorithmes en ligne robustes pour gérer la complexité et l'interactivité. L'un des problèmes résultants ayant émergé récemment est la synchronisation de documents hypermédia qui considère que chaque objet multimédia peut être compressé ou étiré dans le temps comme un ressort. L'hétérogénéité des objets qui composent un document hypermédia fait de leur présentation un problème difficile en temps et en place. D'un autre côté, l'interactivité impose que des mises à jours en temps réel de la planification du document doivent être possibles, augmentant ainsi le besoin d'algorithmes plus rapides pour la prise de décision.

Les documents hypermédia sont composés d'objets multimédia (audio, vidéo, texte, image...), dont la durée de présentation doit être ajustée pour satisfaire un ensemble de contraintes temporelles qui expriment le déroulement de l'animation, telle qu'elle est définie par l'auteur. Mais pour que ces contraintes puissent être satisfaites, l'auteur doit accepter une certaine flexibilité sur la durée (que nous appelons "idéale") de présentation de chaque objet, les pauses étant totalement interdites si elles ne sont pas explicitement demandées. Pour estimer la qualité d'un ajustement, une fonction de coût, généralement convexe, est introduite pour chaque objet. En résumé, le problème que nous tentons de résoudre ici est de trouver un ajustement de la meilleure qualité, i.e. qui minimise la somme des coûts des objets multimédia. Il est identifié comme le problème de la "tension de coût minimum" dans un graphe. Nous étudions trois modèles différents, dépendants du type des coûts (fonctions linéaires par morceaux ou booléennes) et de la flexibilité des durées (intervalles continus ou ensembles de valeurs discrètes).

Dans le premier modèle, les coûts sont des fonctions convexes linéaires par morceaux et la flexibilité des durées est exprimée par des intervalles continus. Le problème peut être modélisé par des programmes linéaires continus. Il s'agit d'une solution très répandue en pratique pour le problème de synchronisation hypermédia. Une autre manière de résoudre le problème est l'algorithme de "mise à conformité" (out-of-kilter) introduit en premier lieu pour le problème du "flot de coût minimum". Nous proposons une adaptation de cette méthode pour des coûts linéaires par morceaux. Cet algorithme est pseudo-polynômial. Plus récemment, un algorithme fût proposé pour résoudre un problème plus générique appelé le problème "dual du flot à coût convexe entier". Il consiste à transformer le problème de tension de coût minimum en un problème de flot de coût minimum, résolu par la méthode très répandue de "mise à l'échelle" (cost-scaling). Cet algorithme est polynômial. Nous discutons d'une comparaison pratique de ces méthodes et comment elles peuvent être utilisées dans des logiciels de synchronisation hypermédia.

Les auteurs de documents hypermédia ont souvent besoin de minimiser le nombre d'objets multimédia qui ne sont pas planifiés à leur durée idéale, la flexibilité des durées étant toujours exprimée par des intervalles continus. Cependant, à cause de la nature booléenne des fonctions de coût, les techniques décrites précédemment ne peuvent plus être utilisées directement, le problème appartenant maintenant au domaine de la programmation entière mixte. Nous proposons une méthode basée sur une relaxation linéaire pour résoudre le problème. Nous montrons qu'il est toujours possible d'utiliser la formulation en tension dans cette relaxation, ce qui nous permet de définir des stratégies efficaces basées sur des méthodes présentées pour le premier modèle, afin d'obtenir de très bonnes solutions en un temps raisonnable.

Dans la dernière variante du problème, nous considérons, à la place d'intervalles continus, un ensemble de valeurs discrètes pour exprimer la flexibilité de la durée de chaque objet multimédia. Le coût est toujours supposé être une fonction linéaire par morceaux. Nous proposons une formulation entière qui implique des variables de décision/binaires pour chaque valeur possible de chaque ensemble de flexibilité. Ce genre de problème est prouvé beaucoup plus difficile à résoudre dans le contexte de la programmation linéaire. Des résultats préliminaires sont présentés.