CDI/Postdoc dans l'Equipe Optimisation Combinatoire, Cnam-Ensta
Forum 'Emplois' - Sujet créé le 2019-06-14 par sourour elloumi
Contexte
Les problèmes d'optimisation quadratique en variables mixtes-entières consistent à optimiser une fonction dans un espace de contraintes où chacune des fonctions (objectif et contraintes) du problème peut faire intervenir une fonction quadratique de plusieurs variables. Ils généralisent la programmation linéaire (cas où le degré de tous les polynômes est 1). Ces problèmes ont de nombreuses applications pratiques et constituent actuellement un champ de recherche très actif. Une des difficultés de la résolution globale de cette classe de problèmes réside dans la nature non-convexe à la fois de la fonction à optimiser et/ou des contraintes. Traditionnellement, ces problèmes sont résolus par un algorithme de branch-and-bound. Cet algorithme est basé sur deux opérations : l'évaluation (bounding) et la séparation (branching). Ainsi à chaque noeud de l'arbre de recherche l'évaluation consiste à calculer une borne, basée sur une relaxation convexe du problème de départ, et la séparation à modifier la région réalisable du problème en faisant varier les bornes d'une variable. Nous avons développé un algorithme de résolution de problèmes quadratiques en variables mixtes entières appelé MIQCR (Mixed Integer Quadratic Convex Reformulation). Cet algorithme fonctionne en 2 phases. Dans la première, nous calculons une relaxation/reformulation convexe du programme initial. La deuxième phase consiste à résoudre le problème convexifié par un algorithme de branch-and-bound. Le logiciel SMIQCP (Solution of Mixed Integer Quadratically Constrained Programs) qui est l'implémentation de la méthode MIQCR a permis de démontrer l'efficacité expérimentale de cette approche. En effet, cet algorithme de résolution est aujourd'hui une des méthodes concurrentielles pour l'optimisation quadratique à l'échelle internationale. En particulier, il a permis d'améliorer la résolution d'un nombre significatif d'instances non encore résolues de la librairie d'instances qplib (http://qplib.zib.de). Pour toutes ces raisons, nous souhaitons proposer une version stable du logiciel pour une utilisation externe et en particulier via la plateforme coin-or (https://www.coin-or.org/). Dans ce contexte, le candidat devra permettre la distribution de ce logicielle à grande échelle. Le candidat intégrera l'équipe Optimisation Combinatoire du laboratoire Cedric du Cnam.
Missions
La mission principale du candidat est de finaliser le développement du logiciel SMIQCP pour le rendre distribuable. Une publication pour ces travaux dans une revue comme Mathematical Programming Computation pourra également être envisagée.
Compétences
Le candidat doit être titulaire d'un master ou d'un doctorat en recherche opérationnelle ou en informatique. Il est demandé une bonne maîtrise des méthodes résolution de programmation mathématique et/ou de l'optimisation globale. Le candidat doit avoir des bases solides en programmation (de préférence en C ou C++ ) et être capable d'utiliser et de mettre en oeuvre des outils de configuration de programmes.
Durée 4 mois
Date de début prévue 1 septembre 2019
Lieu d'exercice Laboratoire Cedric-Cnam, 2 rue de conté 75003 Paris.
Rémunération 2500 euros/mois net
Candidatures Toute candidature est à envoyer à amelie.lambert@cnam.fr et à sourour.elloumi@ensta-paristech.fr. La date limite des candidatures est le 10 juillet 2019
Les problèmes d'optimisation quadratique en variables mixtes-entières consistent à optimiser une fonction dans un espace de contraintes où chacune des fonctions (objectif et contraintes) du problème peut faire intervenir une fonction quadratique de plusieurs variables. Ils généralisent la programmation linéaire (cas où le degré de tous les polynômes est 1). Ces problèmes ont de nombreuses applications pratiques et constituent actuellement un champ de recherche très actif. Une des difficultés de la résolution globale de cette classe de problèmes réside dans la nature non-convexe à la fois de la fonction à optimiser et/ou des contraintes. Traditionnellement, ces problèmes sont résolus par un algorithme de branch-and-bound. Cet algorithme est basé sur deux opérations : l'évaluation (bounding) et la séparation (branching). Ainsi à chaque noeud de l'arbre de recherche l'évaluation consiste à calculer une borne, basée sur une relaxation convexe du problème de départ, et la séparation à modifier la région réalisable du problème en faisant varier les bornes d'une variable. Nous avons développé un algorithme de résolution de problèmes quadratiques en variables mixtes entières appelé MIQCR (Mixed Integer Quadratic Convex Reformulation). Cet algorithme fonctionne en 2 phases. Dans la première, nous calculons une relaxation/reformulation convexe du programme initial. La deuxième phase consiste à résoudre le problème convexifié par un algorithme de branch-and-bound. Le logiciel SMIQCP (Solution of Mixed Integer Quadratically Constrained Programs) qui est l'implémentation de la méthode MIQCR a permis de démontrer l'efficacité expérimentale de cette approche. En effet, cet algorithme de résolution est aujourd'hui une des méthodes concurrentielles pour l'optimisation quadratique à l'échelle internationale. En particulier, il a permis d'améliorer la résolution d'un nombre significatif d'instances non encore résolues de la librairie d'instances qplib (http://qplib.zib.de). Pour toutes ces raisons, nous souhaitons proposer une version stable du logiciel pour une utilisation externe et en particulier via la plateforme coin-or (https://www.coin-or.org/). Dans ce contexte, le candidat devra permettre la distribution de ce logicielle à grande échelle. Le candidat intégrera l'équipe Optimisation Combinatoire du laboratoire Cedric du Cnam.
Missions
La mission principale du candidat est de finaliser le développement du logiciel SMIQCP pour le rendre distribuable. Une publication pour ces travaux dans une revue comme Mathematical Programming Computation pourra également être envisagée.
Compétences
Le candidat doit être titulaire d'un master ou d'un doctorat en recherche opérationnelle ou en informatique. Il est demandé une bonne maîtrise des méthodes résolution de programmation mathématique et/ou de l'optimisation globale. Le candidat doit avoir des bases solides en programmation (de préférence en C ou C++ ) et être capable d'utiliser et de mettre en oeuvre des outils de configuration de programmes.
Durée 4 mois
Date de début prévue 1 septembre 2019
Lieu d'exercice Laboratoire Cedric-Cnam, 2 rue de conté 75003 Paris.
Rémunération 2500 euros/mois net
Candidatures Toute candidature est à envoyer à amelie.lambert@cnam.fr et à sourour.elloumi@ensta-paristech.fr. La date limite des candidatures est le 10 juillet 2019