% \section{Composante Optimisation Combinatoire (OC)} \label{probresOC} \small{\textit{Participants~: L.~Alfandari, H.~Bennaceur, R. Castro de Andrade, F.~Djerourou, M.I.~Khemmoudj, O.~Laval, J.-L.~Lemalade, L.~Létocart, N.~Marcos, A.~Nagih, F.~Pekergin, G.~Plateau, A.~Rasoanaivo, J.~Sadki-Fenzar, N.~Touati, S.~Toulouse}} % J-F.~Culus, \subsection{Thèmes de recherche} Initié en partie depuis septembre 2004 par l'\acs{ACI} JC (cf. \S~\ref{difOC}), le projet de recherche principal de la composante OC est centré sur les méthodes de décomposition (schémas itératifs) pour la résolution exacte de problèmes difficiles d'optimisation combinatoire, méthodes issues de la programmation mathématique. Plus précisément, ce projet s'intéresse à l'accélération et au pilotage de tels schémas sous deux angles spécifiques~: la \textit{résolution approchée} d'une part (pour trouver \guillemotleft~rapidement~\guillemotright\ de \guillemotleft~bonnes~\guillemotright\ solutions) et les méthodes de \textit{stabilisation} et de \textit{réoptimisation} d'autre part (pour accélérer la convergence en fin de résolution). % (cf. \S~\ref{persprech1}). Par ailleurs, la composante OC se consacre à la poursuite de travaux fondamentaux et appliqués en \textit{optimisation en nombres entiers}. L'aspect fondamental concerne plus spécifiquement la modélisation, les relaxations, la complexité et l'approximation, les heuristiques, les méta-heuristiques, et les méthodes de résolution exacte, tandis que les applications sont tournées vers le transport, le dimensionnement de réseaux et la gestion de production agricole. Enfin, le groupe OC poursuit également des recherches dans le domaine de la \textit{satisfaction et de l'optimisation des systèmes de contraintes}. En particulier, des méthodes combinant des techniques d'optimisation combinatoire et de satisfaction de contraintes ont été conçues, et appliquées notamment aux bases de données et à la production d'énergie nucléaire. \paragraph{Optimisation en nombres entiers} \hfill %% MODIF_SOSO_DEB \smallskip L'optimisation combinatoire a pour vocation de construire, pour des problèmes d'optimisation en variables mixtes ou en nombres entiers, des solutions exactes ou approchées. Les approches émergentes sont issues de la programmation mathématique, qui offre des formalismes unifiés pour une large gamme de problèmes et permet ainsi d'élaborer des méthodes de résolution génériques efficaces. La validation peut alors se faire à la fois sur un plan théorique --- notamment par l'analyse du double point de vue de l'approximation et de la complexité --- et sur un plan expérimental. \medskip \textbf{1}\ \textbf{Résolution efficace de problèmes d'optimisation en nombres entiers de très grande taille} S'appuyant sur une forte complémentarité des domaines de recherche de ses différents membres, le projet de recherche de la composante OC s'inscrit plus précisément dans le cadre de la résolution globale et efficace de problèmes d'optimisation en nombres entiers de très grande taille, avec des volets théoriques, algorithmiques et applicatifs. \medskip Les modèles étudiés sont pour la plupart issus des domaines de la planification des ressources dans les systèmes de production et de la gestion des flux dans les réseaux de transport. Dans ces domaines, la prise en compte récente des contextes d'incertitude d'une part, d'éléments qualitatifs d'autre part (notamment dans les réseaux), a mené à l'introduction de nouvelles familles de modèles, intégrant la formulation de contraintes particulières, ainsi qu'un nombre toujours accru de variables de décision. Les problèmes résultants sont d\`es lors très difficiles, de par leur taille (plusieurs milliers de variables et de contraintes), mais aussi de par leur structure combinatoire (présence de variables discrètes), et nécessitent, pour leur résolution effective, l'élaboration d'outils théoriques et algorithmiques spécifiques. Par ailleurs, le contexte opérationnel est en demande d'un arbitrage constant entre la double exigence de qualité des solutions fournies et de temps de calcul raisonnables. Alors qu'en planification stratégique, l'intérêt de l'étude de différents scénarios prime sur les temps de calcul nécessaires pour les obtenir, en planification opérationnelle, le temps de réponse devient crucial~: en cas de perturbation majeure, il faut reconstruire le plan de production en temps réel, tout en minimisant l'écart par rapport au plan prévisionnel afin de réduire l'impact sur la suite des opérations. De nouveau, les outils actuels ne sont pas capables de répondre à ces deux exigences sur des problèmes rendus de plus en plus complexes. \medskip %% MODIF_SOSO_TODO : EN DIRE UN PEU PLUS POUR EQUILIBRER PARTIES JUSTIFICATION & DESCRIPTION Pour pallier les insuffisances des approches existantes prises séparément, on souhaite élaborer des schémas hybrides sachant tirer profit des avantages de chacune d'elles~: la capacité de produire de bonnes solutions réalisables en temps de calcul acceptable pour les approches de type (méta)heuristique d'une part, la vision globale du problème propre aux approches basées sur la programmation mathématique, comme la génération de colonnes, d'autre part. Les schémas hybrides sont en effet souvent plus robustes et permettent de traiter une classe plus large d'instances. L'efficacité de la résolution globale peut aussi être améliorée par l'utilisation de techniques de réoptimisation exploitant l'historique des résolutions des instances successives d'un même problème. Une telle approche, combinant hybridation et réoptimisation, permet d'élaborer des méthodes de résolution qui, non seulement fournissent des solutions de très bonne qualité en temps de calcul raisonnable, mais aussi permettent de recalculer ces solutions en cas de faible perturbation des données. Ces recherches sont élargies à des modèles et problèmes émergents, prenant en compte la qualité des solutions produites, l'introduction de l'incertitude, ou encore la notion d'aide à la décision (notion de robustesse, diversification des solutions, modélisation multicritère, etc.). \medskip \textbf{2}\ \textbf{Aspects fondamentaux et appliqués} Le projet central du goupe OC est nourri des travaux fondamentaux et appliqués qui sont poursuivis par ailleurs. Sous l'angle de la programmation mathématique elle-même, des efforts particuliers sont produits sur l'étude de relaxations fortes pour les problèmes d'optimisation en variables 0-1, linéaires et non linéaires. Concernant la partie approximation polynomiale, elle se concentre plus particulièrement sur la classification des problèmes d'optimisation combinatoire, notamment sous l'angle encore peu développé de l'approximation différentielle. Par ailleurs, certaines familles de problèmes (notamment, recouvrement et partitionnement) font l'objet de recherches algorithmiques spécifiques pour leur résolution ou pour l'amélioration de leur degré d'approximation. %% MODIF_SOSO_TODO : EN DIRE UN PEU PLUS SUR L'APPROX (ST, LA, LL ?) - LA MODELISATION (LA ?) - LES APPLICATIONS %% MODIF_SOSO_FIN \paragraph{Satisfaction et optimisation des systèmes de contraintes} \hfill Les activités de recherche de ce thème concernent le raisonnement à base de contraintes. Dans ce domaine, la connaissance est décrite sous forme de contraintes ou relations (symboliques ou numériques). L'objectif est d'étudier la cohérence (ou la satisfaction) et l'optimisation du système de contraintes associé à une base de connaissances. La conception de méthodes pour ces problèmes se base essentiellement sur les outils de deux domaines différents, mais très complémentaires, à savoir la Recherche Opérationnelle (RO) et l'Intelligence Artificielle (IA). Le travail actuel concerne la combinaison des techniques d'optimisation combinatoire (\textit{relaxation lagrangienne}, \textit{branch and bound}, \textit{méthodes de recherche locale}) et les techniques de satisfaction de contraintes pour résoudre les problèmes CSP et CSP valués. \paragraph{Modélisation stochastique de systèmes discrets} \hfill La recherche de ce thème concerne la modélisation de systèmes à événements discrets par des processus stochastiques et au développement de méthodes de résolution. Un intérêt particulier est attribué à la modélisation et l'évaluation des performances des systèmes complexes, dont les modèles sont de très grande taille dans leur représentation classique. Pour contourner les problèmes dus aux espaces d'états de modèles comprenant des mécanismes de contrôle complexes, on peut recourir à une modélisation par des processus continus. Cette approche consiste, d'une part, à reconstituer l'information perdue du fait de la transformation discret-continu et, d'autre part, à développer les algorithmes numériques nécessaires à leur résolution. \subsection{Résultats significatifs} \label{res1} \textit{Optimisation en nombres entiers} \be \item Au sein d'un schéma itératif, une succession d'instances d'un problème dit auxiliaire doit être résolue. L'introduction des techniques de réoptimisation dans un tel schéma consiste à accélérer la résolution d'une instance de la suite en tirant profit des résolutions des instances qui la précèdent. L'élaboration de ces techniques n'a de sens que si les données des instances sont suffisamment voisines. Pour mieux appréhender cette question de la réoptimisation, il a été décidé de l'entamer dans le cadre de problèmes classiques d'optimisation. C'est pourquoi les travaux se sont d'abord orientés vers la résolution efficace du dual lagrangien du problème du sac à dos à deux dimensions (biknapsack) en variables 0-1. Réalisés dans le cadre de la thèse de Babacar Thiongane, ils ont permis des avancées significatives relativement à l'évolution des données de l'objectif et d'obtenir ainsi une large base de résulats théoriques, algorithmiques et expérimentaux~: \bi \item[--]\ état de l'art sur la \textit{postoptimisation} (analyse de sensibilité, paramétrisation et réoptimisation) en programmation en nombres entiers~\cite{ocad:TNP03a}, \item[--]\ étude de la \textit{complexité} du problème de la paramétrisation en programmation linéaire en 0-1 et élaboration d'un nouvel algorithme, \item[--]\ \textit{réoptimisation} dans le dual lagrangien du biknapsack en variables 0-1~: élaboration de deux approches (MARIE et ASIA) pour la résolution efficace du dual lagrangien par des méthodes de sous-gradients adaptées~\cite{ocad:TNP05,ocad:TNP06}~; combinaison de métaheuristiques et de techniques de réoptimisation pour la construction d'heuristiques performantes pour le problème de biknapsack en variables 0-1~\cite{ocad:TNP06}. \ei \item Des études ont été menées pour le dimensionnement de réseaux de télécommunications. Dans le cas général, la génération de colonnes adaptée à l'optimisation en nombres entiers a été appliquée avec succès en utilisant un \textit{Branch-and-Bound} (méthode par séparation et évaluation) et des coupes géométriques pour éviter d'engendrer des colonnes inadéquates (thèse d'Irène Loiseau). Lorsque les demandes sont incertaines, des techniques issues de l'optimisation stochastique en nombres entiers ont été appliquées (\textit{Branch-and-Cut} et méthodes \guillemotleft~à la Benders~\guillemotright)~\cite{ocad:ALMP04,ocad:ALMP05,ocad:ALMP06}. \item Le statut, en termes de complexité (résolution exacte en temps polynomial) et d'approximabilité (ordre du degré d'approximation que l'on peut espérer obtenir en temps polynomial), de différents problèmes a été décidé~: ces résultats concernent des problèmes de multiflots entiers maximaux et de multicoupes minimales~\cite{ocad:CLR05}, notamment dans les graphes en anneaux~\cite{ocad:BCLR06}, ainsi que certains problèmes de partionnement et de recouvrement d'un graphe par des chaînes de longueur bornée, pour lesquels de meilleures bornes d'approximation classique et différentielle ont également été obtenues~\cite{ocad:MT07d}. \item Des travaux ont été réalisés sur l'élaboration de modélisations sous forme de PLNE (programmes linéaires en nombres entiers) d'ordre polynomial pour la détermination de sous-graphes connexes de poids minimal d'un graphe valué (par exemple, chemin élémentaire, arbre et cycle)~\cite{ocad:MPL03}. \item Des schémas d'approximation utilisant des méthodes de programmation dynamique spécifiques ont été développés et analysés pour des sous-problèmes apparaissant dans des problèmes classiques de couverture de tâches en transport et de localisation d'entreprise~\cite{ocad:A07}. \\ \noindent \textit{Satisfaction et optimisation des systèmes de contraintes} \item Une réécriture originale du problème SAT en un CSP binaire a été exploitée pour montrer qu'il existe de nombreux liens algorithmiques et des concepts équivalents utilisés pour ces deux problèmes~\cite{ocad:B04}. Différents types de méthodes améliorant la résolution du problème Max-CSP ont par ailleurs été développées~: \bi \item[--]\ méthodes de recherche locale intégrant les techniques de consistance locale (consistances d'arc) et de réduction du voisinage, \item[--]\ méthodes exactes hybrides combinant les techniques d'optimisation combinatoire et de satisfaction de contraintes~\cite{ocad:KBN05}. La plupart de ces méthodes ont été implémentées et testées sur des instances aléatoires, académiques et réelles~\cite{ocad:KB06b}.\\ \ei \noindent \textit{Modélisation stochastique de systèmes discrets} \item Par une modélisation qui s'appuie sur l'approximation de diffusion, le comportement transitoire des flux de classes différentes dans les réseaux de communications modélisés par des réseaux de files d'attente a été étudié. L'approximation de diffusion est utilisée dans les modèles à classes multiples pour contourner le problème de l'influence de certains types de transfert de données sur le reste du trafic, tout en compensant la perte d'information due à la transformation des processus discrets en continus~\cite{ocad:CP05b}. Pour représenter les mécanismes de contrôle complexes des réseaux de communications, des modèles de diffusion à sauts multiples sont développés. La validité de la combinaison des sauts avec l'approximation de diffusion pour un modèle de routeur opto-électronique a été montrée et une méthode de résolution numérique pour ce type de modèle a été développée~\cite{ocad:CPS05a}. \ee \subsection{Perspectives de recherche} \label{persprech1} \textit{Optimisation en nombres entiers} \be \item Concernant la mise en \oe uvre de schémas itératifs de type génération de colonnes, nos principaux travaux portent sur les deux points suivants~: \bi \item[--]\ \textit{la réoptimisation}, méthode permettant d'améliorer la complexité des itérations dans la phase de convergence (une thèse en cours). \item[--]\ \textit{l'approximation}, qui offre une justification théorique du comportement des heuristiques (une thèse en cours), \ei \be \item L'objectif actuel est la transposition de techniques de réoptimisation (initiées par les travaux sur les problèmes de sac-à-dos en variables 0-1) à un schéma de type génération de colonnes pour la résolution des problèmes de très grande taille, notamment dans le cadre de la gestion en temps réel des flux dans des réseaux de transport. Ces recherches se poursuivent en priorité vers la réoptimisation de problèmes en nombres entiers avec application au sac à dos quadratique~\cite{ocad:LNP07} et au plus court chemin avec contraintes de ressources~\cite{ocad:TLN07}. La problématique abordée est celle de la résolution globale efficace d'une suite d'instances du problème traité. Trois axes sont donc développés~: \bi \item[--]\ dans le cadre des dualités lagrangiennes et agrégées, la prise en compte de l'évolution des données du problème (méthodes de sous-gradient, génération de colonnes), \item[--]\ l'hybridation de métaheuristiques et d'heuristiques duales, \item[--]\ l'incrémentalité, c'est-à-dire la prise en compte de l'évolution du nombre de contraintes et/ou de variables. \ei \item En approximation, une perspective est d'étudier l'hybridation de méta-heuristiques et d'heuristiques à garantie de performance à la mise en \oe uvre de schémas itératifs. Plus précisément, il s'agirait de construire des populations de solutions diversifiées et de qualité contrôlée, de sorte à mieux piloter le schéma itératif de résolution. %afin d'aboutir à une performance globale à la fois théorique et expérimentale. De nouveau, le but de l'étude est celui du pilotage \item Il est également nécessaire de compléter l'expertise de la composante dans le domaine des approches polyédrales, de sorte à entamer une voie de recherche complémentaire aux travaux actuels sur l'accélération de la convergence des schémas itératifs. En effet, de telles approches permettraient de diminuer le nombre d'itérations de ces schémas par la diminution du domaine de recherche à chaque itération. \ee \item Concernant l'approximation polynomiale au pire des cas, un axe privilégié est celui de la classification des problèmes d'optimisation discrète sous l'angle différentiel, au travers de deux défis essentiels~: d'une part, décider du degré d'approximation différentielle de problèmes de type MaxSAT/MaxCCSP~; d'autre part, établir un cadre pertinent de réduction pour la préservation du rapport constant d'approximation différentiel, en menant une étude d'ordre structurel sur les instances des problèmes à lier par réduction. L'étude des problèmes de logique, par des méthodes \`a base de voisinages, a fait l'objet d'un post-doctorat CNRS en 2006-2007 qui a permis d'améliorer les bornes pour l'approximation différentielle des problèmes Max$k$SAT. Notons que ce projet est en lien étroit avec le groupe de travail \textit{Approximation \& Complexité} (cf.~\S~\ref{oc-diffusion-grpw}). \item La résolution exacte de problèmes non linéaires en nombres entiers, et plus particulièrement de problèmes à objectif quadratique, contraintes linéaires avec des variables bivalentes, est actuellement à l'étude par l'intermédiaire de méthodes lagrangiennes et de techniques de convexification~\cite{ocad:LPP07}.\\ \noindent \textit{Satisfaction et optimisation des systèmes de contraintes} \item Les perspectives concernent essentiellement les applications des techniques CSP et de l'optimisation combinatoire aux problèmes réels industriels. Plus précisément, il s'agit d'approfondir l'étude d'approches combinant la programmation par contraintes et la recherche locale (prenant en compte un autre type de contraintes du problème de placement des arrêts des réacteurs nucléaires). \`A court terme, il est prévu d'étudier l'extension de certaines formes de consistance locale aux CSP pondérés (\textit{WCSP}) et de développer d'autres formes de consistance locale basées sur la consistance d'arc. Un autre objectif est également de travailler sur le logiciel de référence de \textit{WCSP Toolbar} pour y intégrer les résultats obtenus et évaluer les performances des méthodes élaborées. \\ \textit{Modélisation stochastique de systèmes discrets} \item Dans le cadre des travaux de modélisation des systèmes à événements discrets, le premier objectif est le développement de méthodes de résolution robustes et efficaces en temps d'exécution. Une étude de comparaison de coûts s'impose, afin de déterminer l'adéquation entre la complexité des modèles et l'efficacité des différentes méthodes. Ensuite, on peut envisager l'étude de plusieurs systèmes complexes par des modèles de diffusion à sauts multiples~: serveurs web, centres d'appels, routeurs optique-électroniques, etc. \\ \textit{Applications} \item Bien que la recherche en OC se fonde sur le développement et l'étude théorique de méthodes génériques de résolution, les techniques développées s'appliquent à de nombreux domaines (transport, réseau, etc.). Il convient naturellement de continuer à les éprouver auprès des industriels, en consultation ou sur la base de projets. \ee \subsection{Diffusion de la recherche} \label{difOC} \subsubsection*{\'Evaluation de la recherche} \paragraph{Comités éditoriaux} \begin{itemize} \item[--]Anass Nagih~: Bulletin de la Société Fran\c{c}aise de Recherche Opérationnelle et d'Aide \`a la Décision (ROADEF) en 2003. \item[--] Gérard Plateau~: Journal of Heuristics depuis 1995 \item[--] Gérard Plateau~: European Journal of Operational Research (2000-2006) \item[--] Gérard Plateau~: RAIRO - Operations Research depuis 1986 \end{itemize} \paragraph{Comités de programmes} \begin{itemize} \item[--] Gérard Plateau~: MIC'2003, 5th Metaheuristics International Conference, Kyoto, Japon, 25-28 août 03. \item[--] Gérard Plateau~: MIC'2005, 6th Metaheuristics International Conference, Vienne, Autriche, 22-26 août 05. \item[--] Gérard Plateau~: ALIO/EURO Vth Meeting, Paris, 26-28 octobre 05. \item[--] Gérard Plateau~: APMOD'06, 8th Applied mathematical Programming and MODelling meeting, Madrid, Espagne, 19-21 juin 06. \item[--] Gérard Plateau~: MIC'2007, 7th Metaheuristics International Conference, Montréal, Canada, 25-29 juin 07. \item[--] Gérard Plateau~: NCP'07, Non Convex Programming, INSA, Rouen, 17-21 décembre 07. \end{itemize} \paragraph{Comités de lecture ou d'évaluation} \begin{itemize} \item[-- Laurent Alfandari.] Rapporteur d'une demi-douzaine d'articles pour des revues et conférences internationales (Comp. Opt. and Appli., Eur. J. of OR, RAIRO-OR, etc.). \item[-- Lucas Létocart.] Rapporteur de trois articles pour des revues internationales (Dis. Appl. Maths, RAIRO-OR, TOP). \item[-- Anass Nagih.] Rapporteur de six articles pour des revues et conférences internationales (Eur. J. of OR, RAIRO-OR, CP-AI-OR, ROADEF). \item[-- Gérard Plateau.] Rapporteur de vingt articles pour des revues et conférences internationales (Eur. J. of OR, OR, Workshop Math. Programming, MIC, ROADEF). \end{itemize} \subparagraph{Autres responsabilités d'évaluation} \begin{itemize} \item[--]Gérard Plateau~: FQRNT (Fonds québécois de la recherche sur la nature et les technologies)~: évaluation d'une demande de projet en janvier 2004 (Québec) \item[--]Gérard Plateau~: CRSNG (Conseil de recherche en sciences naturelles et en génie du Canada)~: évaluation d'une demande de projet en janvier 2004 (Ottawa) \item[--]Gérard Plateau~: CNRS~: expertises de projets Agence Nationale de la Recherche 2005 \item[--]Gérard Plateau~: Ministère~: expertises de dossiers pour la DS1 puis de la DSPT9 - Master en 2004 et en 2007. \item[--]Gérard Plateau~: Membre du comité scientifique du GDR RO~: expertise de projets 2005-2006. \item[--]Gérard Plateau~: Région Champagne-Ardenne~: Expertise d'un dossier d'allocation post-doctorale en mars 2004 \item[--]Gérard Plateau~: Membre des comités scientifiques des laboratoires d'informatique de Tours et d'Avignon en 2007. \end{itemize} \paragraph{Jurys hors LIPN} \begin{itemize} \item[Jury de thèse :] G. Plateau (6, rapporteur~:5), A. Nagih (2, rapporteur~:1), S. Toulouse (1, rapporteur~:1). \item[Jury d'habilitation à diriger des recherches :] G. Plateau (1, rapporteur~:1). \end{itemize} %\medskip \textbf{--}\ Babacar \textsc{Thiongane}, \textit{Ré-optimisation dans le dual lagrangien du biknapsack %en variables 0-1}, Thèse de Doctorat d'Informatique, Université Paris 13, mention Très Honorable avec les %Félicitations du jury, 24 février 2003 (thèse financée par Allocation de recherches) [Encadrement en collaboration %avec Anass Nagih (50\%), LIPN]. \\ %Jury : A. Billionnet (IIE), M. Guignard (Wharton School, Philadelphie, USA), N. Maculan (UFRJ, Rio de Janeiro), %A. Nagih (Paris 13), G. Plateau, C. Roucairol (Versailles-St Quentin les Yvelines, présidente), %Rapporteurs : A. Billionnet, N. Maculan. %(Postdoctorant à l'université de Montréal (Canada).) %\medskip \textbf{--}\ Irène \textsc{Loiseau}, \textit{la génération de colonnes en nombres entiers}, Thèse de Doctorat %d'Informatique, Université Paris 13, mention Très Honorable., 29 juin 2005. [en collaboration avec Nelson Maculan %(50\%), UFRJ (Brésil) \\ %Jury : A. Lisser N. Maculan (UFRJ, Rio de Janeiro), A. Nagih (Paris 13), G. Plateau, J. Vauzeilles (présidente, %Paris 13), Rapporteurs : A. Lisser (Paris 11), C. Roucairol (UVSQ). \\ %(Maître de Conférences, Université de Buenos Aires (Argentine).) \\ %\item[Jury d'Habilitation à diriger des Recherches (G. Plateau)] \hfill %\medskip \textbf{--}\ Alain \textsc{Faye}, \textit{Contributions à la programmation quadratique en 0-1}, %Habilitation à Diriger des Recherches en Informatique, Université Paris 13, 17 décembre 2003. \\ %Jury : A. Billionnet (IIE), M. C. Costa (CNAM), D. Fayard (Paris 11), R. Mahjoub (Clermont Ferrand), %Ph. Michelon (Avignon), Gérard Plateau (président), J. Vauzeilles (Paris 13), %Rapporteurs : M. Guignard (Wharton School, Philadelphie), R. Mahjoub, Ph. Michelon. \\ %(Maître de Conférences, IIE, Evry.) %\medskip \textbf{--}\ Anass \textsc{Naghi}, \textit{Contributions la résolution des problèmes en nombres entiers : %ré-optimisation, problèmes de grande taille et planification en transport}, Habilitation à Diriger des Recherches %en Informatique, Université Paris 13, 14 décembre 2004. \\ %Jury : A. Billionnet (IIE), D. Gauyacq (DR\&T SNCF, Paris), N. Maculan (UFRJ, Rio de Janeiro), G. Plateau, %A. Quilliot (Clermont-Ferrand), F. Soumis (école Polytechnique de Montréal), J. Vauzeilles (présidente, Paris 13), %Rapporteurs : M. Guignard (Wharton School, Philadelphie), A. Billionnet, A. Quilliot. \\ %(Professeur à l'université de Metz depuis septembre 2006.) %\end{itemize} \subsubsection*{Organisation de la recherche} \paragraph{Organisation de conférences et événements scientifiques} \begin{itemize} \item[--]Anass Nagih~: Membre du comité d'organisation du Prix Robert Faure 2003 (prix récompensant une contribution originale dans le domaine de la Recherche Opérationnelle et l'Aide \`a la Décision). \item[--]Laurent Alfandari et Lucas Létocart~: Membres du comité d'organisation des Journées Franciliennes de Recherche Opérationnelle de 2003 \`a 2006~: organisation de 8 journées \item[--]Anass Nagih~: organisation de la participation du LIPN \`a la manifestation {\it Savante Banlieue}, Villetaneuse, 13-14 octobre 2005. \end{itemize} \paragraph{Gestion de groupes de travail}\label{oc-diffusion-grpw} Un nouveau groupe de travail, \textit{Approximation \& complexité}, a été créé en septembre 2006. Sa vocation première est la structuration de $\mathbf{NPO}$, c'est-à-dire l'étude de la complexité d'approximation des problèmes difficiles d'optimisation combinatoire, en attaquant les problèmes sous un angle structurel plutôt qu'algorithmique. L'idée est alors de faire concourir à l'objectif de classification différentes approches et savoir-faire qui sont présents au laboratoire dans d'autres contextes de recherche~: l'optimisation combinatoire (groupe OC), la combinatoire analytique (groupe AD), la combinatoire algébrique (LCR) et la théorie de la complexité (OCAD \& LCR). %% MODIF_SOSO_DEB : SUPPRESSIONS %% en privilégiant le cadre différentiel d'une part, l'étude du comportement en moyenne des solutions d'autre part %% et ce dans l'espoir d'acquérir une meilleure connaissance de la struture même des problèmes. En effet, c'est souvent par une meilleure connaissance de leur structure que l'on parvient à classifier les problèmes. %% Bien entendu, ce groupe est avant toute chose un lieu de discussion (présentation d'articles et de nouvelles problématiques), mais aussi d'echange (mini-tutoriaux) et de formation (en proposant notamment des cours de type formation doctorale, ouverts à l'ensemble du laboratoire~: théorie des groupes en janvier-février 2007, complexité en septembre-octobre 2007). %% MODIF_SOSO_FIN \subsubsection*{Contrats} %\vskip 1cm \noindent {\footnotesize \begin{tabular}{lp{.5cm}lllp{1cm}p{.5cm}p{.5cm}p{.5cm}} \rotatebox{40}{Type} & \rotatebox{40}{Coordinateur} & \rotatebox{40}{Resp. scient.} & \rotatebox{40}{Nom} & \rotatebox{40}{Financeur} & \rotatebox{40}{Période} & \rotatebox{40}{Durée (mois)} & \rotatebox{40}{Budget global (k\texteuro)} & \rotatebox{40}{Part LIPN (k\texteuro)} \\ \acs{ACI} & \acs{LIPN} & A. Nagih & COGiTO & \acs{MENESR} & 09/2004-08/2007 & 36 & 66 & 66 \\ \acs{CIFRE} & \acs{SNCF} & G. Plateau & & \acs{SNCF} & 10/2002-09/2005 & 36 & 22,5 & 22,5\\ Contrat & \acs{EDF} & H. Bennaceur & & \acs{EDF} & 05/2003-04/2006 & 36 & 75 & \\ Contrat & \acs{EDF} & H. Bennaceur & & \acs{EDF} & 08/2006-01/2008 & 18 & 83 & 10\\ Veille & \acs{SNCF} & A. Nagih & & \acs{SNCF} & 02/2005-11/2007 & 34 & 22,5 & 22,5 \end{tabular}} \subsubsubsection{\acs{ACI} COGiTO} Le projet de recherche d'OC bénéficie (depuis septembre 2004) du soutien d'une \acs{ACI} Jeunes Chercheuses et Jeunes Chercheurs, composée d'Anass Nagih, Laurent Alfandari, Lucas Létocart, Agnès Plateau (\acs{CNAM}) et Sophie Toulouse, sur le thème \textit{Planification et gestion optimisée des ressources en transport~: réoptimisation et hybridation de la génération de colonnes et des métaheuristiques} (2004-2007). Ce projet, qui va de la modélisation à la réalisation informatique via la résolution, a notamment offert le cadre de collaborations avec des partenaires académiques (\textsc{gerad}) et industriels (\acs{SNCF}). Il a également permis de réaliser courant 2005 une plate-forme logicielle d'optimisation appelée \textsc{COGiTO}.\\ \subsubsubsection{\acs{CIFRE} \acs{SNCF}} Dans le cadre de la thèse \acs{CIFRE} \acs{SNCF} de Nicolas Marcos, le travail a concerné la gestion de production et la planification en transport ferroviaire. Plus spécifiquement, un outil générique d'aide à la décision pour la gestion des locomotives fret à la \acs{SNCF} a été élaboré grâce à de nouvelles modélisations du problème utilisant l'aspect multiflot de cette application~\cite{ocad:MAGQNAP05}. \subsubsubsection{Contrats \acs{EDF}} L'étude du \textit{problème de placement des arrêts des réacteurs nucléaires} a été développée dans le cadre de la thèse d'Idir Khemmoudj. Il s'agit d'un problème d'ordonnancement couplé à un problème de planification de la production (contrat \acs{EDF}-\acs{LIPN}). Dans un premier temps, la contribution de la programmation logique par contraintes à la résolution de ce problème a été évaluée. Un système combinant la programmation par contraintes et la recherche locale pour construire des plans d'arrêts avec un meilleur profit a ensuite été développé. \subsubsubsection{Veille \acs{SNCF}} Le contrat d'étude et de veille sur les approches de modélisation et techniques de résolution exploitables pour optimiser la planification de ressources de production mobiles entre la \acs{SNCF}-DI\&R et les membres de l'\acs{ACI} Jeunes Chercheurs vise à recenser les formalisations existantes (et récentes) qui sont envisageables pour les problèmes de planification de ressources mobiles dans le domaine des transports, ainsi que la complexité de ces modélisations. Un panorama comparatif des approches de résolution existantes (et récentes) pour ces modèles (approches standards ou dédiées, optimales vs approchées) est dressé. Enfin, les performances numériques de certaines approches sont évaluées, à partir notamment de problèmes concrets fournis par la \acs{SNCF}-DI\&R. \subsubsection*{Dissémination} L'année 2005 a été l'occasion de rédiger trois chapitres sur les problèmes de sac-à-dos, de transport aérien et du voyageur de commerce, dans un ouvrage consacré à l'optimisation combinatoire~\cite{ocad:AN06,ocad:MT07a,ocad:PN07}. \paragraph{Invitations, tutoriels} \begin{itemize} \item[--] Anass Nagih~: Conférencier-invité par la Direction de la Stratégie de la SNCF, la Direction des Opérations et la Direction de l'Innovation et de la Recherche dans le cadre du projet ``Mieux concevoir pour mieux produire''~; titre ``Planification des ressources humaines'', siège de la \acs{SNCF} Paris (17 juin 2003). \item[--] Gérard Plateau~: Tutoriel pour les Journées Franciliennes de Recherche Opérationnelle~; titre ``Sur le sac à dos en variables 0-1'', Paris (13 janvier 2006). \end{itemize} \paragraph{Actions de vulgarisation de la recherche} \begin{itemize} \item[--]Lucas Létocart~: Présentation d'une démonstration "Courses et jeux de fourmis" \`a la manifestation {\it Savante Banlieue}, Villetaneuse, 13-14 octobre 2005. \end{itemize} \subsubsection*{Collaborations} \paragraph{Collaborations universitaires} \be \item Les collaborations d'Anass Nagih avec Fran\c{c}ois Soumis et Yassir Miladi (école Polytechnique de Montréal et \textsc{gerad}) s'articulent principalement autour de~: \bi \item la construction de rotations d'équipages en planification opérationnelle~; \item les heuristiques lagrangiennes pour le problème de plus court chemin contraint~; \item la réduction de l'espace des états dans un algorithme de type programmation dynamique. \ei \item Une collaboration entre les membres de l'\acs{ACI} Jeunes Chercheurs et Jeunes Chercheuses et le \textsc{gerad} a été mise en place sous la forme d'invitations réciproques d'enseignants-chercheurs. \item Dans le cadre de la thèse de Jean-Luc Lemalade, financée par une bourse de coopération franco-malgache, en partenariat avec le \textsc{cirad} Montpellier et le \textsc{fofifa} Antananarivo, une étude porte sur l'optimisation de la gestion des ressources agricoles en milieu forestier tropical, dans le but d'éviter l'extension des surfaces à cultiver en gérant les parcelles en milieu de façon originale (cloisonnement, bandes anti-érosion, utilisation optimale des jachères et rotation des cultures) menant à un équilibre entre l'espace agricole et l'espace forestier~\cite{ocad:LANP06}. \item L'application suivante a été développée par Hachemi Bennaceur et Idir Khemmoudj~: \textit{Contraintes dans les bases de données} (en collaboration avec F.~Boufares). \\ L'étude de la validité d'un schéma relationnel \guillemotleft~Entité-Association~\guillemotright\ d'une base de données repose sur la vérification de la cohérence du système de contraintes associé à ce schéma. Plus précisément, elle a porté sur différents types de contraintes (cardinalités, dépendance fonctionnelles, rôle, etc.) et sur les méthodes pour résoudre les systèmes de contraintes permettant de décider si une base de données est instanciable. Une extension de ces résultats à la modélisation UML a également été proposée~\cite{ocad:BB04a}. \item évaluation des performances dans le projet \acs{CNRS}-PAN (Pol 16684) (coopération franco-polonaise). Projet de coopération bilatérale \acs{CNRS}-PAN~: \textit{Analyse transitoire des réseaux à service intégrés par l'approximation de diffusion}. 2004-2005. Fehran Perkergin. \item Projet de coopération bilatérale \acs{CNRS}-PAN (Pol 16684)~: \textit{Processus de diffusion à sauts multiples en modélisation des systèmes de télécommunications}. 2006. Fehran Perkergin. \ee \subsection{Formation à la recherche} %\noindent{\footnotesize \begin{tabular}{lll} %nom & date & position actuelle pour HdR \\ %Frédéric Roupin & 2007 & \acs{MCF} \acs{IIE} \\ %-- & -- & -- %\end{tabular}} \medskip \no \textit{\textbf{Thèses soutenues}} \bi \item[1999-2003] Babacar Thiongane~: \textit{Ré-optimisation dans le dual lagrangien du biknapsak en variables 0-1} \\ Financement de la thèse~: Allocation de Recherche du Ministère \\ Soutenue le 24 février 2003 \\ Directeurs~: Gérard Plateau et Anass Nagih \\ Situation actuelle du diplômé~: Post-doc au Canada. \item[2001-2005] Irène Loiseau~: \textit{La génération de colonnes en nombres entiers} \\ Soutenue le 29 juin 2005 \\ Directeurs~: Gérard Plateau et Nelson Maculan \\ Situation actuelle du diplômé~: Enseignant Chercheur à l'Université de Buenos Aires, Argentine. \item[2002-2006] Nicolas Marcos~: \textit{Modélisation et Optimisation de la Gestion du Matériel Roulant à la SNCF} \\ Soutenue le 23 novembre 2006 \\ Directeurs~: Gérard Plateau, Anass Nagih et Laurent Alfandari\\ Situation actuelle du diplômé~: Chef de projets de recherche à la SNCF, Direction de l'Innovation et de la Recherche, Paris. \item[2002-2007] Mohand Ou Idir Khemmoudj~: \textit{Modélisation et résolution de systèmes de contraintes : Application au problème de placement des arrêts et de la production des réacteurs nucléaires d'EDF} \\ Soutenue le 04 avril 2007 \\ Directeurs~: Hachemi Bennaceur et Marc Porcheron\\ Situation actuelle du diplômé~: Post-doc EDF-LIPN, Paris. \item[2002-2007] Fay\c cal Djerourou~: \textit{Contribution à la résolution complète et incomplète du problème de satisfaction de contraintes pondérées} \\ Soutenue le 15 juin 2007 \\ Directeur~: Hachemi Bennaceur\\ Situation actuelle du diplômé~: Ingénieur en informatique, Paris. \ei \medskip \no \textit{\textbf{HDR soutenues}} \bi \item[2003] Alain Faye~: \textit{Contributions à la programmation quadratique en 0-1} \\ Soutenue le 17 décembre 2003 \\ Coordinateur~: Gérard Plateau \\ Situation actuelle du diplômé~: Maître de Conférences HDR à l'IIE-CNAM. \item[2004] Anass Nagih~: \textit{Contributions à la résolution des problèmes en nombres entiers~: ré-optimisation, problèmes de grande taille et planification en transport} \\ Soutenue le 14 décembre 2004 \\ Coordinateur~: Gérard Plateau \\ Situation actuelle du diplômé~: Professeur à l'Université de Metz. \item[2007] Frédéric Roupin~: \textit{Algorithmes Combinatoires et Relaxations par Programmation Linéaire et Semidéfinie. Application à la Résolution de Problèmes Quadratiques et d'Optimisation dans les Graphes.} \\ Soutenue le 24 novembre 2006 \\ Coordinateur~: Gérard Plateau \\ Situation actuelle du diplômé~: Maître de Conférences HDR au CNAM. \ei \medskip \no \textit{\textbf{Doctorants}}\\ \medskip \noindent{ \footnotesize \begin{tabular}{lll} nom & date & position actuelle pour thèses \\ O. Laval & 10/2005-10/2008 & Allocataire - moniteur \\ J.-L. Lemalade & 10/2002-12/2006 & bourse coopération franco-malgache \\ A. Rasoanaivo & 10/2006-10/2009 & bourse \acs{AUF} \\ J. Sadki-Fenzar & 10/2006-10/2009 & Allocataire - monitrice \\ N. Touati & 10/2005-10/2008 & Allocataire - monitrice \end{tabular}} \paragraph{Participations à des écoles (printemps, été, hiver, automne)} \begin{itemize} \item[--] Olivier Laval~: Séminaire de Mathématiques supérieures (SMS)~: Optimisation combinatoire~: Méthodes et applications, Département de mathématiques et de statistique (DMS) de l'Université de Montréal, 19-30 juin 2006. \item[--] Nora Touati~: Ecole printanière sur les tournées de véhicules, HEC Montréal, 10-12 mai 2006. \item[--] Nora Touati~: GERAD Summer School~: Column generation, Ecole Polytechnique de Montréal, 15-19 mai 2006. \end{itemize} \paragraph{Cours de DEA / Master 2 recherche} \begin{itemize} \item[-- 2003 à 2004.] (L. Létocart, A. Nagih)~: \textit{Méthodes Avancées en Optimisation Discrète}, DEA \textsc{ia-oc}, Paris 8 - Paris 13. \item[-- 2004 à 2005.] (L. Létocart, A. Nagih, S. Toulouse)~: \textit{Méthodes Avancées en Optimisation Discrète}, DEA \textsc{ia-oc}, Paris 8 - Paris 13. \item[-- 2003 à 2005.] (G. Plateau)~: \textit{Optimisation en nombres entiers}, DEA \textsc{ia-oc}, Paris 8 - Paris 13. \item[-- 2005 à 2007.] (L. Létocart, A. Nagih, S. Toulouse)~: \textit{Méthodes Avancées en Optimisation Combinatoire}, Master Mathématiques-Informatique 2\ieme année recherche, Paris 13. \item[-- 2005 à 2007.] (L. Alfandari, L. Létocart)~: \textit{Aide à la Décision}, Master Mathématiques-Informatique 2\ieme année recherche, Paris 13, et Master 2\ieme année Modélisation Informatique des Connaissances et du Raisonnement, Paris 13. \item[-- 2005 à 2007.] (G. Plateau)~: \textit{Optimisation combinatoire}, Master Mathé\-ma\-tiques-Infor\-ma\-tique 2\ieme année recherche, Paris 13. Option du Master Mathématiques-Informatique-Technologies 2\ieme année recherche (\textit{Mathématiques et Applications au codage et à la cryptologie}), Paris~8. \item[-- 2005 à 2007.] (Sophie Toulouse)~: \textit{Optimisation Combinatoire}, DEA IGMA (\textit{Informatique et Génie Mathématique}), Université d'Antananarivo (Madagascar). \end{itemize} \paragraph{Stages de DEA / Master 2 recherche} \begin{itemize} \item[-- 2003] (A. Nagih, G. Plateau, S. Lenestour (Air France))~: T. Soulimane (DEA \textsc{ia-oc} Paris 13, Air France)~: \textit{Application des métaheuristiques au problème de reconstruction des rotations d'équipages} \item[-- 2003] (A. Nagih, G. Plateau, D. De Almeida (SNCF))~: S. Nicolas (DEA \textsc{ia-oc} Paris 13, \acs{SNCF})~: \textit{Optimisation de la gestion des lignes \`a voie unique} \item[-- 2003] (A. Nagih, G. Plateau)~: A. Birri (DEA \textsc{ia-oc} Paris 13, \textsc{gdf})~: \textit{élaboration d'une méthode de dimensionnement des réseaux de transport de gaz} \item[-- 2004] (A. Nagih, D. De Almeida (SNCF))~: A. Quivet (DEA \textsc{ia-oc} Paris 13, \acs{SNCF})~: \textit{Approches de résolution pour des modèles d'optimisation de la gestion des locomotives~: étude et implantation} \item[-- 2004] (A. Nagih, G. Plateau)~: E. Dumont (DEA \textsc{ia-oc} Paris 13, Eurodécision)~: \textit{Optimisation de la diversité des cablages dans le domaine de l'automobile} \item[-- 2005] (L. Létocart, A. Nagih)~: N. Touati (DEA \textsc{ia-oc} Paris 13, \acs{LIPN})~: \textit{Ré-optimisation au sein d'un schéma de génération de colonnes} \item[-- 2005] (L. Létocart, A. Nagih, G. Plateau)~: R. Ouaras (DEA 103 Paris 9-Dauphine, \acs{LIPN})~: \textit{Ré-optimisation du sac \`a dos quadratique} \item[-- 2005] (L. Létocart, A. Nagih)~: G. Elain (DEA \textsc{ia-oc} Paris 13, Thalès)~: \textit{Modèles réalistes de placement d'acteurs virtuels} \item[-- 2005] (A. Nagih, D. De Almeida (\acs{SNCF}))~: J. Tea (DEA \textsc{ia-oc} Paris 13, \acs{SNCF})~: \textit{Métaheuristiques pour des modèles d'optimisation de la gestion des locomotives~: étude et implantation} \item[-- 2005] (L. Alfandari, A. Nagih, A. Plateau (\acs{CNAM}))~: S. Djabouabdallah (DEA \textsc{ia-oc} Paris 13, \acs{LIPN})~: \textit{étude de méthodes de résolution approchée des problèmes de planification} \item[-- 2006] (L. Létocart, A. Nagih, G. Plateau)~: T. Radakovic (Master MMI2 Paris 13, \acs{LIPN})~: \textit{Ré-optimisation du sac \`a dos quadratique} \item[-- 2006] (L. Alfandari, A. Nagih, A. Plateau (\acs{CNAM}))~: J. Sadki-Fenzar (Master MMI2 Paris 13, \acs{LIPN})~: \textit{Méthodes de décomposition pour la résolution de problèmes de planification} \item[-- 2006.] (V. Ravelomanana, S. Toulouse)~: H. Razafisambatra (DEA IGMA Tananarive)~: \textit{Approximation de problèmes définis sur des collections d'ensembles}. \item[-- 2006.] (V. Ravelomanana, S. Toulouse)~: S. Djabali (P6-UPMC, \acs{LIPN})~: \textit{Approximation en moyenne}. \item[-- 2007] (L. Létocart, M-C. Plateau, G. Plateau)~: A. Benouali (Master MMI2 Paris 13, \acs{LIPN})~: \textit{Méthodes lagrangiennes pour la résolution du sac-\`a-dos quadratique avec contrainte de cardinalité} \item[-- 2007] (L. Létocart, N. Touati)~: Z. Beddar (Master MMI2 Paris 13, \acs{LIPN})~: \textit{Résolution de modèles d'optimisation de grande taille~: méthodes de décomposition et algorithme de génération de colonnes} \end{itemize}