LIP6 1998/047

• Rapports de recherche
  Assignation de fibres optiques pour la spectroscopie multi-objets
• F. Sourd
• 71 pages - 15/12/1998- document en - http://www.lip6.fr/lip6/reports/1998/lip6.1998.047.ps.gz - 514 Ko
• Contact : Francis.Sourd (at) nulllip6.fr
• Ancien Thème : SYSDEF
Le problème d'assignation de fibres à des objets vient de l'astronomie. Ce problème de géométrie et de combinatoire vise à disposer dans le plan des segments -- ou des rectangles -- sans intersections. Pour résoudre ce problème, nous avons construit une suite d'algorithmes qui converge vers la solution maximale. En fait, les premiers éléments de cette suite donnent de très bons résultats en un temps bref. De plus, ils peuvent être améliorés par des techniques de post-optimisation basées sur ces mêmes heuristiques. Les bons résultats obtenus ont permis de lancer une recherche de la solution exacte. On montre ainsi que les méthodes heuristiques trouvent généralement la solution optimale en quelques
minutes.
• Mots clés : Heuristiques, optimisation, analyse combinatoire, astronomie
• Directeur de la publication : Valerie.Mangin (at) nulllip6.fr