Et c’est où qu’on picole dans tout ça ?

mardi 8 février 2005.
 
Abstract : Nous décrivons et nous présentons un problème de localisation particulier, bien que découlant des problèmes dits "classiques". Nous décrivons les spécificités de notre problème, et le modelisons sous la forme d’un problème d’optimisation, que nous résolvons.

De tout temps, les Hommes ont aimé faire leur réveillon du nouvel an avec des potes. "Bon, c’est où qu’on picole cette année ??". Ce cri plein d’entrain et d’énergie, nous l’avons d’ailleurs tous entendu aux approches des fêtes de fin d’année.

Mais ce problème de choix est (et a toujours été) beaucoup plus délicat qu’il n’en a l’air ! Nous nous proposons de résoudre pour vous, oui ! vous ! lecteur aimé !, cet épineux problème : "Mais où passer ce putain de réveillon, bordel ???"

C’est après de longues et difficiles études que La Gros-Naze Scientific Team vous présente une démarche révolutionnaire, pour résoudre le problème présenté. Bien que comportant des hypothèses Gros-Naze specific, nous avons la certitude qu’il est possible d’adapter notre démarche à des problèmes similaires ; réduisant leur complexité à celle de faire planter un Windows 98 au mieux de sa forme (problème de complexité logarithmique, voire même constante).

Pour illustrer nos propos et les avantages de notre démarche, nous prendrons tout d’abord l’exemple suivant (à ne pas suivre).

Nos rivaux et concurrents (que nous respectons malgré toutes leurs déficiences aussi bien mentales que éditoriales) - la Multinationale Vieille-Tanche inc. pour ne pas la nommer - se confine dans un empirisme dépassé et absurde. Ah ah ah ! Rions gaiement et de bon coeur !!

Les espèces de demeurés qui font partie de ce respectueux regroupement d’arrièrés organisent une beuverie pré-réveillon. Naturellement, ils picolent tous comme des trous, et lorsque vient finalement à l’ordre du jour l’épineux problème, ils commencent à s’engueuler comme de vieux poivrots qu’ils sont tous et à se foutre sur la gueule [Ça explique peut-être leur sale gueule, NDLR]. Tout commentaire étant inutile devant tant de ridicule, nous nous contenterons de rire devant cette candeur et innocence. Ah ah ah !

Alors que nous autres, à la Gros-Naze Inc, avons défini une démarche à la rigueur très germanique ; afin que l’émotionnel (et Dieu sait que nous autres, Gros-Naze, avons un émotionnel grand comme ça !) ou le taux éthylique (et Dieu sait que nous autres, Gros-Naze, avons un taux éthylique haut comme ça !) ne prenne pas le dessus sur le rationnel lorsque d’importantes décisions doivent être prises.

Dans un premier temps, nous résumerons les contraintes des gens. Lors d’une seconde partie, nous aborderons le difficile problème de la prise de décision et proposerons un algorithme permettant de trouver un consensus acceptable et accepté par tous. Finalement, nous conclurons et mettrons en perspectives les résultats obtenus en posant d’autres problèmes directement liés a la thématique présentée dans ce document.

(putain, après une intro comme ça, j’ai intérêt d’assurer).

Les contraintes

Notre problème est un classique problème de localisation. Ce type de problème a déjà largement été traité. Le lecteur intéressé se réferera à [SBob05,Opti4Vr01,ZDS03] pour une présentation plus en détail. Notre version du problème est identique à celle trouvée classiquement dans la littérature, à ceci prêt que nous ajoutons quelques contraintes non-usuelles.

Difficile mise en évidence de la restriction suivante : technologiquement parlant, il a été prouvé que voyager vite[AirF04], efficacement et de manière pratique[SNC+] et pas chère[BNP04,CA05] n’était pas possible. Par ailleurs, la présence d’éléments "perturbateurs" (dans le sens scientifique du terme : change une situation d’équilibre) complique encore plus la situation. Ceci nous amène naturellement à la contrainte suivante :

(1.1) ne peut être "loin" de Grenoble.

Évidemment, le concept de "loin" reste à définir. Il dépend d’un ensemble complexe de données tant technologiques (puissance du moteur) que temporelles (après 5h de route, j’ai envie de dormir) ou encore météorologiques (c’est quoi, ce truc blanc ?). Bref, en première approximation, on peut considérer "loin" comme correspondant à quelques heures de routes ; 5 étant considéré comme une limite raisonnable (mais a ne pas dépasser)

Il nous fait également rajouter les contraintes habituelles

(1.2) être capable d’héberger tout le monde dans des conditions décentes

(1.3) pouvoir grailler comme des chancres

La résolution

Ceci nous mène naturellement au problème d’optimisation suivant :

Maximiser le "fun" du nouvel an
soumis a :
-  Temps de route à partir de Grenoble < 5h
-  Maison ou appartement, mais offrant des capa d’hébergement
-  Un Carrouf’ tout près

Notre problème étant combinatoire, il n’existe pas de méthode efficace permettant de trouver rapidement la solution optimale ; l’énumération étant le seul algorithme avec garantie de résultat. Par chance, le problème considéré dans ce document est de petite taille, permettant d’appliquer (justement) des méthodes basées sur l’énumération intelligente des solutions. Cependant, nous avons choisi d’utiliser un algorithme de "deep cut". Nous ne pouvons donner la garantie de lister exhaustivement toutes les solutions possibles du problème. Cela dit, a première vu, il nous semble que non.

Une étude poussée du polyèdre nous a permis d’extraire trois solutions viables au problème considéré :
-  Grenoble
-  Valence
-  Nice

Il serait possible de relâcher la contrainte (1.1) pour augmenter l’espace des solutions, mais la solution trouvée dans ces cas-la serait moins représentative de la situation réelle ; et du coup moins fun (fait étrange ; puisque généralement quand on augmente l’espace des solutions, on améliore la valeur de la fonction objectif. Ce phénomène fera l’objet d’une étude future). Ce serait malgré tout dommage, surtout que dans [Mail04], les auteurs écrivent "Les GNs, c’est comme les Marines : ça ne laisse jamais quelqu’un sur le carreau".

Nous avons ensuite étudié chacunes des possibilités et sa pertinence par rapport aux autres possibles solutions. Par exemple, la solution Niçoise a été écartée du fait de la difficulté technologique associée. En effet, il aurait fallu que nous développions un algorithme massivement parallèle afin que les structures engagées tienne le choc. Or, dans le temps impartis et compte tenu des ressources disponibles, cela n’était pas possible, même pour des Gros-Naze. Il s’est donc avéré que la formule Valençoise soit la meilleure.

Conclusion

Nous présentons une approche rigoureuse pour le problème de localisation dans le contexte de réveillons de Nouvel-an. Nous soulignons l’originalité de notre problème en énumérant les contraintes Gros-Naze specific et formulons le problème d’optimisation associé. À l’aide d’un algorithme "deep cut", nous extrayons du polytope des solutions un sous-ensemble restreint de possibilités, à partir duquel nous pouvons prendre une décision simplement.

Nous avons vérifié expérimentalement les qualités de la solution obtenue, et, bien que ayant passé un réveillon très satisfaisant, nous nous sommes aperçus que notre modélisation n’était pas assez précise, puisque ne prenant pas en compte certaines incertitudes et autres phenomènes aléatoires. Nous travaillons donc sur une version de notre problème intégrant des processus (poissonniens et ravioliens uniquement pour l’instant).

Notons que nous avons tout de même plus mangé au cours du-dit réveillon qu’un Ziak après un jeûne de 3 jours...

(Ce dossier explosif aurait dû être publié avant le réveillon 2004/2005. Malheureusement, suite à des ennuis techniques de l’un de nos fournisseurs, l’édition de ce grand dossier a été repoussé. Les membres de la Gros-Naze Publishing Team vous présente humblement ses excuses. Cela dit, la méthode présentée ci-dessous est intemporelle, et pourra donc être appliquée dans la joie, la bonne humeur, et la charité chrétienne, pour le réveillon 2005/2006).
Répondre à cet article

Forum