Convexité et combinatoire

http://www.roadef.org/content/roadef/bulletins/bulletinNo22.pdfNational audienceDe nombreux problèmes dans l'industrie ou les services peuvent être modélisés comme des problèmes d'optimisation de nature combinatoire. La résolution numérique de ces problèmes nécessite souvent la mise en oeuvre de méthodes spécifiques. On peut néanmoins isoler quelques idées fondamentales à la source de nombreuses approches ou techniques en optimisation combinatoire. Deux méthodes essentielles sont : couper et majorer. L'analyse convexe s'avère être un cadre théorique adapté à ces deux paradigmes. Ainsi l'optimisation convexe a permis d'élaborer de nouvelles méthodes - certaines pratiques, d'autres théoriques - qui complètent les méthodes plus combinatoires. Cet article est destiné à des lecteurs venant de tous les horizons de la recherche opérationnelle ; son objectif est de leur donner l'envie de s'intéresser à l'analyse convexe. Nous évoquons ainsi tour à tour : les problèmes décomposables, le problème de la gestion de la production électrique en France, l'optimisation semidéfinie positive et un problème standard sur les graphes