STAGE – Ingénieur(e) Recherche – Optimisation combinatoire et contraintes conditionnelles

Description de l'offre

Company descriptionDescriptif de l'entreprise

Dassault Systèmes, « The 3DEXPERIENCE Company », offre aux entreprises et aux particuliers les univers virtuels nécessaires à la conception d’innovations durables. Ses solutions leaders sur le marché transforment pour ses clients, la conception, la fabrication et la maintenance de leurs produits. Les solutions collaboratives de Dassault Systèmes permettent de promouvoir l’innovation sociale et offrent de nouvelles possibilités d’améliorer le monde réel grâce aux univers virtuels. Avec des ventes dans plus de 140 pays, le Groupe apporte de la valeur à plus de 200 000 entreprises de toutes tailles dans toutes les industries. Pour plus d’informations : www.3ds.com.

CATIA, SOLIDWORKS, SIMULIA, DELMIA, ENOVIA, GEOVIA, EXALEAD, BIOVIA, NETVIBES, 3D VIA, 3DEXCITE sont des marques déposées de Dassault Systèmes ou de ses filiales aux USA et/ou dans d'autres pays.

Job descriptionDescriptif du poste

Contexte & Présentation d'équipe

Ce stage est proposé par l’organisation « Recherche » dont la mission est de développer et d’évaluer l'applicabilité de nouvelles technologies innovantes, notamment sur des prototypes, pour maintenir un haut niveau de compétences dans tous les domaines techniques stratégiques.

Rôle & Objectif

Un problème d’optimisation combinatoire consiste à trouver dans un ensemble discret, un parmi les meilleurs sous-ensembles (ou solutions) réalisables, la notion de meilleure solution étant définie par une fonction objectif.
Trouver une solution optimale dans un ensemble discret et fini est un problème facile en théorie : il suffit d'essayer toutes les solutions, et de comparer leurs qualités pour voir la meilleure.
Cependant, en pratique, l'énumération de toutes les solutions peut prendre trop de temps. Or, le temps de recherche de la solution optimale est un facteur très important et c'est à cause de lui que les problèmes d'optimisation combinatoire sont réputés si difficiles.

La description de l’ensemble discret est donc implicite, il s’agit de la liste, relativement courte, des propriétés des solutions réalisables. En général, cette liste est définie par des contraintes (équation, inéquations) dans une manière déclarative. C'est-à-dire, l’ordre dans lequel sont définies les contraintes n’est pas important pour la recherche de la solution optimale. Par contre, les méthodes de résolution dépendent fortement de la complexité des contraintes (linéaires, non-linéaires, algébriques, booléennes, etc.).
Parmi l’ensemble de contraintes, on peut avoir des contraintes universelles (qui sont toujours vraies) et des contraintes conditionnelles (vraies sur certaines conditions). Par exemple, en considérant un ensemble d’activités A1, A2, A3, il est toujours vrai que la somme du début de chaque activité et de sa durée soit égale à la fin de l’activité (Ai.début + Ai.durée = Ai.fin). Par contre, si on voudrait dire que l’activité, qui sera la première parmi les trois, doit commencer au moment t0, il est nécessaire d’utiliser les contraintes conditionnelles :
- si (A1.début <= A2.début && A1.début <= A3.début) alors A1.début = t0 ;
- si (A2.début <= A1.début && A2.début <= A3.début) alors A2.début = t0 ;
- si (A3.début <= A1.début && A3.début <= A2.début) alors A3.début = t0 ;

Donc, les contraintes conditionnelles nous permettent d’être beaucoup plus flexibles et puissants dans notre spécification du problème à résoudre.
En général, le problème d’optimisation combinatoire avec des contraintes conditionnelles peut être considérer comme un problème SMT (Satisfiabilité Modulo Théories), qui lui-même est un problème de satisfiabilité booléenne (SAT) modulo une certaine théorie. Formellement, une instance de SMT est une formule du premier ordre sans quantificateur. Le problème SMT est de déterminer si une telle formule est satisfiable. En d'autres mots, imaginons une instance de SAT dans laquelle les variables booléennes sont remplacées par des prédicats, ces prédicats étant classés selon la théorie à laquelle ils appartiennent. Des exemples de théories incluent la théorie des nombres réels, la théorie de l’arithmétique linéaire, des théories de diverses structures de données comme les listes, les tableaux ou les vecteurs de bits, ainsi que des combinaisons de celles-ci.

Ainsi, l’objectif de votre stage sera de participer au développement d'un solveur de type SMT permettant la résolution efficace de problèmes de planification, d’allocation de ressources, de vérification formelle et d’autres types de problèmes de recherche opérationnelle, en s’inspirant d’articles scientifiques récents.
Dans un premier temps, le solveur devra trouver des solutions acceptables avec un temps de calcul raisonnable. Le travail sera fait en étroite collaboration avec les services de développement concernés.

Candidate's profileProfil recherché

Etudiant(e) en Ecole d'Ingénieurs ou Master universitaire, vous préparez un diplôme de niveau Bac+5 ou Bac+6.
Vous vous spécialisez en Mathématiques appliquées/ Développement informatique .
Vous recherchez un stage de fin d'études de 6 mois.

Compétences techniques requises

• C++
• Optimisation, optimisation combinatoire
• Programmation par contraintes

Qualités professionnelles requises

• Rigueur
• Autonomie
• Motivation

Position SummaryRésumé du poste

Position DescriptionDescriptif du poste

Type of contractType de contrat

Contrat proposé

Stage obligatoire de validation de cursus, sous convention de stage.
Durée 6 mois maximum, à débuter dès que possible.

Localisation géographique

Vélizy-Villacoublay (78 - Yvelines)

EducationFormation académique

RequirementsExigences

QualificationsQualifications

Compensation & BenefitsRémunération & Avantages Sociaux

How to apply?Comment postuler ?

Closing StatementsAvis