Devoir maison 2

Voyage voyage

L’énoncé du problème est ici.

Vos approches

En gros, j’étais bien impressionné par vos travaux rendus. La plupart ont tenté une approche gloutonne puis une recherche locale, ce qui était à quoi je m’attendais. Mais certains sont allés plus loin:

• fait une petite bibliographie, mais trouvé un seul article de recherche, qui n’aidait pas, car le problème présent est trop simplifié.
• tenté un algorithme génétique. En général se prête bien à des problèmes qui se posent sur des permutations.
• analysé l’instance.
  • Observé que les valeurs non-nulles sont distinctes.
  • Observé que les matrices sont creuses, mais pas exploité cette propriété.
  • Observé que les distances ne satisfont pas l’inégalité triangulaire. Ceci rend le problème symmétrique entre avions et portes et nombre passagers et distances. Mais on ne sais pas comment exploiter cette propriété.
• en général votre approche gloutonne n’était pas décrite de manière assez formelle, par exemple est-ce que la distance d’une porte aux autres, était restreint aux portes déjà affectés, et est-ce que ces distances sont pondérées par les nombres de passagers?
• beaucoup ont vu que la recherche locale nécessitait de la pertubation et des redémarrages pour sortir des minimas locaux. Certains ont documenté leur optimisations de paramètres. J’ai bien aimé également des expériences sur les tailles du voisinage.
• vos codes Python étaient en général très clean, bien documenté. Idem pour le code C++. Parfois vous avez travaillé sur l’optimisation du code, utilisation de packages numba, mise à jour du coût après un échange plutôt que recalcul.
• parfois vous avez tenté d’utiliser un solveur de programmation linéaire. Mais les techniques de linéarisation d’expressions quadratiques n’ont pas été introduits dans le cours et vous ont manquées.

Ma notation

Honêtement j’avais du mal à vous départager, surtout que les approches étaient bien différents parfois. Je suis parti d’une note de base de 15 pour un devoir correct, en augmentant ou diminuant en fonction des aspects séduisants ou décevants de votre devoir.