Lessive, cartes, horaires : RO découvre la recherche opérationnelle

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Aujourd'hui, on va se poser une question qui peut paraître un peu folle, mais qu'est-ce qu'une banale corvée de lessive en plein confinement peut bien avoir en commun avec l'optimisation des radars pendant la Seconde Guerre mondiale ?

Intervenant 20:15

Oui, et même avec le prix Nobel d'économie tant qu'on y

Intervenant 10:18

est. Exactement. La réponse tient en deux mots, recherche opérationnelle. Aujourd'hui, on plonge dans une histoire fascinante pour ceux qui nous écoutent.

Intervenant 20:26

C'est clair. Et notre point de départ, c'est ce quotidien super étouffant du confinement. L'espace vital qui se réduit, le partage chaotique de l'ordinateur, l'école à la maison.

Intervenant 10:36

L'enfer,

Intervenant 20:37

quoi. C'est ça. Et on va vivre ça à travers les yeux de notre héros du jour, un ado qu'on va appeler Romuald Oscar.

Intervenant 10:43

Ou juste RO pour aller plus vite. Et l'objectif de ce décryptage, c'est vraiment de démontrer à notre audience que les mathématiques de très haut niveau, elles ne se cachent pas uniquement dans les labos obscurs, tu vois.

Intervenant 20:53

Ouais, ni sur des tableaux noirs remplis de formules que personne ne comprend.

Intervenant 10:57

Voilà, en fait, elles sont là, littéralement tapis dans la buanderie ou sur un coin de bureau.

Intervenant 21:01

Parce que, derrière le chaos domestique d'un ado qui traîne des pieds pour faire le ménage, se dissimule une discipline scientifique redoutablement puissante.

Intervenant 11:10

Absolument.

Intervenant 21:11

C'est vraiment tout l'enjeu de notre exploration d'aujourd'hui. Observer comment un problème qui a l'air super trivial, comme ça, force l'esprit humain à développer des trésors d'abstraction.

Intervenant 11:20

Alors posons le décor, on est en plein confinement et c'est la première corvée pour notre jeune héros,

Intervenant 21:26

le pauvre.

Intervenant 11:26

Ouais, surtout que son père a inventé un concept de télétravail disons très personnel. Il fait des allers-retours métronomiques entre son poste de travail, le frigo et la télé.

Intervenant 21:37

Très

Intervenant 11:38

productif. Et soudain, paf, l'automate à lessive sonne. Le père hurle sur son fils pour qu'il aille étendre le linge.

Intervenant 21:45

Classique.

Intervenant 11:46

Sauf qu'il y a une contrainte imposée par le voisinage. Il faut utiliser un minimum de cordes à linge pour en laisser aux autres colocateurs de l'immeuble.

Intervenant 21:53

Et c'est là que l'esprit de RO s'éveille. Face à cette contrainte, il refuse de juste jeter les vêtements en boule sur les fils.

Intervenant 12:01

Il a sa fierté quand même, hein ?

Intervenant 22:02

Voilà. Il aborde le truc avec la rigueur d'un géomètre. Il descend à la cave avec un mètre ruban, carrément, et il mesure l'espace exact que prend chaque vêtement humide.

Intervenant 12:12

Attends, il mesure ses chaussettes avec un mètre ruban ?

Intervenant 22:17

Bah ouais. Et il associe une valeur en centimètres, qu'on va appeler la variable aj, pour chaque article qu'il numérote j.

Intervenant 12:25

D'accord, très pointilleux.

Intervenant 22:26

Ensuite, il mesure la longueur totale d'une corde, qu'il nomme L, et toutes les cordes ont cette même capacité maximale L.

Intervenant 12:33

Donc on se retrouve avec un ado armé d'un mètre ruban face à un tas de chaussettes mouillées.

Intervenant 22:37

Exactement.

Intervenant 12:38

Et là, piqué au vif, il cherche de l'aide sur Internet. D'ailleurs, l'anecdote de ses recherches est super drôle parce qu'il tape « théorie des cordes »

Intervenant 22:46

Ah, la fameuse.

Intervenant 12:47

Ouais, en espérant trouver une méthode de séchage. Et bam, il tombe sur l'astrophysique quantique. Forcément. Du coup, il tente « problème de la lessive » et il atterrit sur des techniques de lavage de cerveau de secte. Internet dans toute sa splendeur. C'est ça. Face à ce mur, il finit par contacter sa prof de sciences dures sur les réseaux, Madame Iber Grumbel. Et elle, elle identifie immédiatement le problème mathématique caché là-dessus. Le fameux beanpacking.

Intervenant 23:13

Le problème du remplissage de boîtes. C'est vraiment un pilier de la recherche opérationnelle.

Intervenant 13:19

Ok, mais c'est quoi exactement ?

Intervenant 23:20

Bah le modèle mathématique est super limpide en fait. Comment regrouper un ensemble d'objets de tailles différentes, donc ici nos articles de taille AJ, dans un nombre minimum de contenants de capacité fixe L ?

Intervenant 13:33

Sans jamais que ça déborde

Intervenant 23:34

quoi. Voilà, sans que la somme des tailles dans un contenant dépasse cette fameuse capacité L.

Intervenant 13:39

Ça me fait direct penser au jeu Tetris, où tu sais, ce moment horrible où il faut charger le coffre de la voiture avant de partir en vacances.

Intervenant 23:46

Ah, le cauchemar de l'été.

Intervenant 13:48

Mais ouais, on a de grandes valises, des petits sacs, des chaussures qui traînent et un espace hyper limité. Mais il y a un truc où je bloque. Pourquoi Egero, il les reste coincés ?

Intervenant 23:58

Comment ça ?

Intervenant 13:59

Il connaît la taille de ses vêtements, il connaît la taille des cordes. Un simple ordinateur ou même l'appli calculatrice de son téléphone devrait pouvoir lui recracher la combinaison parfaite instantanément, non ?

Intervenant 24:09

Eh bien non, et c'est ça qui est dingue. La difficulté, elle ne vient pas de l'opération en elle-même. Faire des additions, c'est facile. Ça vient de ce qu'on appelle l'explosion combinatoire.

Intervenant 14:20

L'explosion

Intervenant 24:20

combinatoire. Ouais, le beanpacking, ça appartient à une classe de problèmes d'optimisation qu'on appelle NP difficile. Pour visualiser le truc, prenons un exemple tout bête. Si tu as juste trois chaussettes et deux t-shirts, tester absolument toutes les combinaisons possibles de répartition sur les cordes, ça te prend quelques secondes de réflexion maximum. Logique. Mais ajoute des articles. Disons qu'on arrive à une lessive familiale de 50 pièces.

Intervenant 14:45

Ce qui arrive vite.

Intervenant 24:46

Bah, le nombre de façons d'associer ces 50 éléments, ça dépasse allègrement le nombre d'atomes dans l'univers observable.

Intervenant 14:53

Quoi ? Attends, sérieux ?

Intervenant 24:55

Mais vraiment ! L'algorithme de force brute, tu sais, celui qui essaye toutes les solutions une par une pour trouver la meilleure, il s'effondre complètement face à cette échelle.

Intervenant 15:04

Donc, si on demande à un super ordinateur de tester toutes les configurations pour 50 vêtements, il moulinerait pendant des milliards d'années, juste pour étendre des pantalons ?

Intervenant 25:13

Exactement. C'est le cœur du problème. Alors, pour contourner cette limite mathématique fondamentale, les chercheurs n'utilisent pas la force, ils utilisent la ruse.

Intervenant 15:23

Ah, et ça ressemble à quoi cette ruse ?

Intervenant 25:26

Il développe des heuristiques. Ce sont des méthodes de résolution approchées. Ça ne garantit pas la perfection absolue, tu vois, mais ça donne une excellente solution en une fraction de seconde.

Intervenant 15:35

Ok, je vois. Mais est-ce qu'on peut décortiquer une de ces fameuses heuristiques ? Comment un algorithme s'y prendrait concrètement, là, devant la machine à laver d'euros ?

Intervenant 25:45

La méthode la plus connue pour ce problème, elle s'appelle le first fit decreasing, ou en français, premier arrivé, premier servi, avec tri décroissant.

Intervenant 15:54

Ça sonne bien.

Intervenant 25:55

La première étape, c'est tout bête, on trie tous les vêtements du plus grand au plus petit. On prend le plus encombrant, disons un grand drap de bain, et on le place sur la première corde.

Intervenant 16:04

D'accord.

Intervenant 26:05

Ensuite, on prend le deuxième élément le plus grand, une serviette normale. Est-ce qu'elle rentre sur la première corde avec le drap ? Bomme.

Intervenant 16:13

Euh... Si oui, on la met.

Intervenant 26:15

Voilà. Sinon, on ouvre une deuxième corde. Et on continue comme ça, en essayant toujours de faire rentrer le vêtement dans la toute première corde qui a encore de la place, avant d'en entamer une nouvelle.

Intervenant 16:26

Mais c'est hyper intuitif en fait. C'est exactement ce qu'on fait avec le coffre de la voiture.

Intervenant 26:30

C'est ça. On met d'abord les énormes valises rigides bien au fond, et après on utilise les sacs souples et les manteaux pour boucher les trous qui restent.

Intervenant 16:37

Tout à fait. Le cerveau humain est une excellente machine ahuristique, mine de rien.

Intervenant 26:41

Mais mathématiquement parlant, même si cette méthode est super rapide, elle peut parfois nécessiter une corde de plus qu'une répartition magique.

Intervenant 16:48

Une répartition magique ?

Intervenant 26:50

Oui, une combinaison totalement contre-intuitive, introuvable par l'esprit humain, qui aurait groupé trois petits vêtements avec un vêtement moyen pour libérer un espace inattendu ailleurs.

Intervenant 17:00

Ah, je vois. Et RO, vu qu'il cherchait la perfection absolue pour pas se faire engueuler par son père, il s'est retrouvé complètement paralysé.

Intervenant 27:08

C'est ça. Incapable de garantir qu'il avait optimisé l'espace, il a juste abandonné.