4 avr 07
a 10h30 Abdel Lisser parle sur Stochastic Frequency Assignment ProblemWe consider the Frequency Assignment Problem (FAP) in the case when the important components of problem formulation are uncertain and can be modelled by random variables. In particular, we look at the case when the interference between sources and/or demand for frequences have random nature. Several optimization models which belong to stochastic programming approach are considered. Solution schemes based on semi-definite relaxations are developed. Presented results including numerical experiments confirm that stochastic programming modeling tools coupled with semi-definite relaxations constitute a promising approach for solving frequency assignment problems under uncertainty.
28 mars 07
a 10h30 Thang expose l'article AdWords and Generalized On-line Matching de Mehta, Saberi, U. Vazirani, V. Vazirani.
22 mars 07
a 14h Alexander Lazarev (Computer center of the russion academy of science, Moscow) speaks on his work on scheduling and combinatorial problems (knapsack, partition).
22 mars 07
a 11h Christoph expose des 2-approximations pour le problème d'ordonnancement 1|prec|Σwj Cj. C'est une très belle généralisation de la règle de Smith. L'exposé sera basé sur une note de cours de Shmoys.
17 oct 06
à 14h Vincent JOST parle sur Ordonnancement chromatique: polyèdres, complexité et classification.27 sept 06
à 10h Pietro Belotti et Sebastian Orlowski (Konrad-Zuse-Zentrum für Informationstechnik Berlin) donnent deux exposés de 25 minutes chacuns:20 sept 06In the first part, we will give a general overview on network design and routing problems. Starting from typical industrial applications, we will give some ideas on how to model these problems mathematically using mixed-integer programming techniques. The focus of the second part will be how to tackle these problems algorithmically. Using a very specific example, we will describe a typical solution approach using a branch-and-cut algorithm.
à 10h30 Renaud Sirdey (de Nortel) parlera sur Optimisation combinatoire et autocommutateurs:6 sept 06L'industrie des télécommunications est à l'origine de nombreux problèmes combinatoires parmi les plus difficiles, généralement autour de problématiques liées à la conception, au dimensionnement et à l'exploitation des réseaux. Une autre source de problèmes combinatoires se cache au sein des machines qui constituent ces réseaux : les autocommutateurs.
Le but de cet exposé est double. Il s'agit tout d'abord de donner un aperçu, au travers d'une sélection d'exemples, de la variété des problèmes d'optimisation combinatoire rencontrés dans le cadre de la conception des autocommutateurs du sous-système radio des réseaux GSM puis de présenter plus en détail un problème de reconfiguration dynamique d'autocommutateurs à architecture répartie qui fait actuellement l'objet d'un travail de thèse de doctorat.
La première partie de notre exposé consistera donc essentiellement en la présentation de méthodes opérationnelles de résolution de problèmes réels : résolution de problèmes de flots et configuration de cellules radios, résolution de variantes du problème de bin-packing et gestion de l'interface entre deux autocommutateurs, résolution de problèmes de sac à dos max-min et passage en mode dégradé d'une station de base, etc. Nous insisterons sur les contraintes, principalement liées au temps réel, qui restreignent le champ des méthodes de résolution utilisables, en particulier lorsqu'il s'agit de résoudre des problèmes NP-difficiles.
La seconde partie de notre exposé sera consacrée à l'étude d'un problème de reconfiguration dynamique d'autocommutateurs. Il s'agit d'un problème d'ordonnancement à contraintes de ressources, NP-difficile au sens fort, qui consiste grossièrement à ordonner des déplacements de processus entre les processeurs d'un système réparti en tenant compte de contraintes de capacité. Après avoir exhibé quelques cas particuliers polynomiaux, nous présenterons une variante de l'algorithme du recuit simulé basé sur la notion de (alpha,beta)-acceptabilité, où beta définit une exigence de qualité (distance à l'optimum) et où alpha est la probabilité de satisfaire cette exigence. Appliquées à notre problème, ces considérations théoriques ont donné lieu à un algorithme de résolution approchée dont les performances pratiques s'accordent remarquablement avec la théorie. Enfin, nous concentrerons notre propos sur les aspects théoriques, études des polytopes des sous-tournois sans circuit et des programmes de déplacements que nous avons introduits, et pratiques, mise en oeuvre et évaluation empirique d'un algorithme de recherche arborescente polyédrique (branch-and-cut), de l'application des méthodes d'optimisation polyédrique à notre problème. D'autres aspects seront brièvement évoqués.
à 10h00 Christoph Dürr expose l'article de Bock, S.; Pinedo, M.: A Decomposition Scheme for Scheduling Problems with Jobs that have Equal Processing Times.16 juin 06 (vendredi !):
à 10h30 Christoph Dürr exposera des algorithmes classiques pour le problème de flot de coût minimal [chapitre 9 de Network flows par Ahuja, Magnanti, Orlin].5 avril 06:
à 10h30 Philippe Baptiste nous explique son papier Scheduling Unit Tasks to Minimize the Number of Idle Periods: A Polynomial Time Algorithm for Offline Dynamic Power Management à SODA'06 : en gros on a n tâches de durée unitaires à exécuter sur une machine, chaque tâche j doit être placée dans un intervalle [rj;Dj] donnée, et il faut minimiser le nombre de périodes de temps mort. La motivation est qu'on veut minimiser le nombre de fois où la machine doit se réveiller de son hibernation.15 mars 06:
à 10h15 Christoph Dürr parlera de cet algorithme de Tarjan dont on n'a pas parlé la semaine dernière. Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines, M. R. Garey, D. S. Johnson, B. B. Simons and R. E. Tarjan, SIAM J. Computing, 10 (1981), pp. 256-269.8 mars 06:
à 10h30 Konstantin nous explique l'algorithme en O(n^2) de Barbara Simons pour le problème d'ordonnancement 1| rj; pj=p; dj|- où il s'agit de placer n tâches de même durée p, sur une machine en respectant les dates de relâchement et les dates limites respectifs. -- Notez que ce problème se résoud en O(n log n) en utilisant une structure de donnée de Tarjan, dont on ne parlera pas.1 mars 06:
Christoph Dürr parle sur un article de la conférence DA'06 : The Knuth-Yao Quadrangle-Inequality Speedup is a Consequence of Total-Monotonicity par Wolfgang W. Bein, Mordecai J. Golin, Lawrence L. Larmore, Yan Zhang22 fèv 06:
Emilie Winter parle sur ses travaux sur l'ordonanncement dans les contrôleurs de radars.1 fèv 06:
Miki Hermann parle sur sa recherche actuelle, comment il aborde la programmation par contraintes, par la complexité et l'algèbre universelle.25 jan 06:
C.Dürr parle sur LIFT and PROJECT. Une méthode pour ajouter des contraintes à un programme linéaire afin de diminuer le fossé entre optimum fractionel et optimum entier.