Le séminaire OCAD accueille Ali Ridha Mahjoub (LAMSADE, Université Paris Dauphine).

Les techniques d’optimisation combinatoires se sont avérées très efficaces pour formuler, analyser et résoudre à l’optimum des problèmes concrets difficiles. En particulier, plusieurs problèmes de conception de réseaux ont été formulés comme des modèles d’optimisation combinatoire. Avec l’introduction de nouvelles technologies de pointe telle que la technologie des fibres optiques, le domaine des télécommunications a connu un développement considérable ces dernières années. Aujourd’hui, il ne s’agit plus d’assurer seulement la transmission de sons, mais plus généralement celle de données. En plus celle-ci ne cesse d’augmenter en volume (comme dans les réseaux Internet). En conséquence, les opérateurs de télécommunications sont souvent confrontés à des problèmes de synthèse de réseaux composites. Ces problèmes concernent plutôt la planification à moyen ou à long terme, et consistent à trouver la topologie optimale du réseau (en terme de liens) et le dimensionnement pour écouler la demande. Très souvent, des études de fiabilité (sécurisation de réseaux) viennent se greffer à ces problèmes de synthèse de réseaux. En effet il est crucial au moment de la conception du réseau de tenir compte des possibilités de panne de liaisons ou de nœuds dans le réseau. Les fibres optiques ont une capacité presque illimitée, et une rupture dans le réseau peut être de lourdes conséquences. Pour cela la fiabilité d’un réseau de télécommunications est toujours un objectif principal dans sa conception.

Nous discutons d’un modèle général de conception de réseaux fiables. Nous étudions le problème de séparation pour certaines familles de contraintes valides. Nous étudions aussi la relaxation linéaire du problème et caractérisons, dans certains cas, les graphes pour lesquels cette relaxation est entière. Nous discutons enfin de certaines applications algorithmiques dans le cadre d’une méthode de coupes pour le problème.