Abstract : L'exposé est principalement axé sur la description de la méthode de résolution exacte actuellement disponible sur le site du LIPN. Elle comporte un pré-traitement de complexité linéaire (résolution en continu, heuristique gloutonne, fixation de variables via la relaxation lagrangienne) suivi d'une phase d'énumération hybridant le branch-and -bound et la programmation dynamique. L'histoire de cette conception sera rappelée, depuis la méthode originelle conçue avec Didier Fayard, le principe de l'hybridation élaborée avec Moussa Elkihel et l'implantation efficace réalisée avec Philippe Bourgeois. Quelques interactions avec les résolution des sac à dos "baudruche", fractionnaire et à plusieurs contraintes seront également évoquées, ainsi que celles avec la ré-optimisation dans le cadre de la résolution du dual lagrangien du sac à dos à deux contraintes.

Abstract : Dans cet exposé nous nous intéresserons à des problèmes de programmation entière de type sac à dos 0-1. Nous présenterons comment nous avons parallélisé un algorithme de programmation dynamique basé sur des techniques de dominance. La technique de parallélisation utilisée nécessite la coopération des processeurs mais génère des structures de données irrégulières et le nombre d'états dominés est imprévisible. En conséquence, il est nécessaire d'employer conjointement des techniques d'équilibrages de charges qui seront aussi présentées au cours de l'exposé.

Abstract : Le problème de sac-à-dos séparable quadratique multidimensionnel en variables entières (QMKP) consiste en la maximisation d'une fonction concave séparable quadratique soumise à m contraintes linéaires (dites contraintes de capacité) et à l'intégrité des variables. C'est un problème NP-difficle qui a de nombreuses applications en finance, par exemple (QMKP) modélise un problème de gestion de portefeuilles. Cet exposé a pour objectif de comparer différentes formulations possibles de (QMKP) afin de déterminer la plus adaptée suivant la structure du problème considéré. Ainsi, nous présenterons dans un premier temps 4 formulations possibles de (QMKP). Puis nous comparerons ces 4 méthodes de résolutions exactes de (QMKP) sur des instances de structures différentes.

Abstract : Dans cet exposé, nous nous intéressons à l'analyse de la sensibilité de l'optimum du problème du partage équitable (Knapsack Sharing Problem -KSP-) soumis à une perturbation du profit d'un de ses éléments. Il s'agit de déterminer, pour chaque élément, les bornes d'un intervalle de sensibilité dans lequel le profit de l'élément peut &ecric;tre perturbé sans modifier la solution optimale de l'instance initiale. Une instance du KSP est caractérisée par un ensemble N de n éléments, partitionné en m classes, et par une capacité c. A chaque élément j, j=1,...,n, est associé un profit pj et un poids wj. L'objectif du problème est de maximiser le minimum de la somme des profits des objets mis dans le sac pour chaque classe, tout en respectant la contrainte de capacité c. Considérons une instance KSP résolue à l'optimum, et notons x sa solution optimale. Considérons maintenant l'instance KSP', obtenue à partir de l'instance initiale KSP en perturbant le profit de l'élément s. Nous commençons par déterminer la relation entre les ensembles des solutions réalisables du KSP et KSP'. Par la suite, nous déterminons l'intervalle de sensibilité dans lequel la perturbation imposée sur le profit ps peut varier sans que la solution optimale x ne soit affectée, en décomposant le problème en une série de problèmes de sac-à-dos auxquels on applique les résultats obtenus par Hifi et al. Finalement, nous montrons comment adapter ces résultats pour le KSP et nous proposons une procédure de calcul des limites de l'intervalle de sensibilité de chaque élément, tout en distinguant deux cas selon que la solution optimale correspond à une seule ou à plusieurs classes d'objets.