Au fil des rencontres avec les membres du projet ValueBugs, j'ai fréquemment eu l'occasion d'observer la perplexité de mes interlocuteurs quant à la présence d'un mathématicien appliqué/informaticien dans le projet. Si quelques explications rapides permettent habituellement de donner une idée, somme toute floue, de mon rôle au sein du projet, il est souvent plus difficile, à l'oral et en quelques phrases, de donner une intuition plus précise sur l'intérêt de l'optimisation combinatoire dans un projet citoyen tel que ValueBugs.

Premier encart, pour ceux qui se demandent ce qu'est le projet ValueBugs, en quoi ça consiste, le rapport avec les larves ou même quelle est l'origine du monde ou le but de la vie, (presque) tout est détaillé ici!

Optimisation Combinatoire ?!?

À la lecture de ce terme un peu obscur, les curieux technophiles se seront rués sur Wikipedia et auront trouvé la définition suivante:

Dans sa forme la plus générale, un problème d'optimisation combinatoire (on dit aussi optimisation discrète) 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

Bon... Pas sûr que la définition soit plus claire que le terme lui-même. L'objectif de ce billet est de donner une idée plus précise de ce qui se cache derrière l'optimisation combinatoire et son application/utilité dans ValueBugs. Pour ce faire, intéressons nous au problème de distribution des larves en début de phase d'expérimentation.

Des larves ?!? Mais pourquoi ?!?

La réponse est ici.

La répartition des larves

Un peu de contexte d'abord. Une phase d'expérimentation commence habituellement par l'obtention d'un grand nombre de larves non matures. Les larves sont ensuites réparties entre les différents citoyens chercheurs qui pourront alors commencer à les engraisser à grand renfort de déchets organiques, jusqu'à la récolte des larves mûres (pupes). Derrière ces quelques phrases, en apparences anodines, se cache en réalité un problème dont les tenants et aboutissants peuvent s'avérer complexes. C'est ce problème que je vais chercher à expliciter dans les paragraphes à venir. Et pour ce faire prenons un exemple concret. Considérons 4 citoyens chercheurs (qui doivent être approvisionnés en larves):

  • Alice
Alice
par Pypeartv - CC-BY-SA (https://fr.wikipedia.org/wiki/Fichier:Scrabble_letter_A.svg)
  • Bob
Bob
par Pypeartv - CC-BY-SA (https://fr.wikipedia.org/wiki/Fichier:Scrabble_letter_B.svg)
  • Charles
Charles
par Pypeartv - CC-BY-SA (https://fr.wikipedia.org/wiki/Fichier:Scrabble_letter_C.svg)
  • Denise
Denise
par Pypeartv - CC-BY-SA (https://fr.wikipedia.org/wiki/Fichier:Scrabble_letter_D.svg)

un universitaire (chez qui se trouvent toutes les larves au début de la distribution):

  • Étienne
Etienne
par Pypeartv - CC-BY-SA (https://fr.wikipedia.org/wiki/Fichier:Scrabble_letter_E.svg)

et une associative (qui a la lourde responsabilité de s'occuper manuellement pour le moment de la distribution et dont le lieu de travail sert d'entrepôt de stockage de larves):

  • Marie
Marie
par Pypeartv - CC-BY-SA (https://fr.wikipedia.org/wiki/Fichier:Scrabble_letter_M.svg)

La situation actuelle est décrite sur la carte suivante (pour des raisons de lisibilité, de simplicité et un petit peu de flemme aussi, je ne considérerai que les distances à vol d'oiseau): Étienne livre les larves à Marie qui se charge d'assurer la répartition des larves entre les quatre citoyens chercheurs. La gestion de la répartition des larves étant une tâche suffisamment chronophage et compliquée, les citoyens se déplacent pour venir chercher leurs larves (le sens des flèches indique le déplacement).

Solution actuelle
Fond OpenStreetMap, Image CC-BY-SA

Dans la mesure où cette façon de distribuer les larves respecte l'ensemble des contraintes imposées, on parle alors de solution réalisable.

À quel moment a-t-on posé des contraintes?

Explicitement à aucun moment, en effet. Mais! (parce qu'il y a toujours un mais), considérons les plans de distrbutions détaillés par les cartes ci dessous.

Solution non réalisable 1
Fond OpenStreetMap, Image CC-BY-SA
Solution non réalisable 2
Fond OpenStreetMap, Image CC-BY-SA
Solution non réalisable 3
Fond OpenStreetMap, Image CC-BY-SA

Si je vous demandais si l'un de ces trois plans d'approvisionnement peut être considéré comme correct, j'imagine que la réponse majoritaire serait non. Dans le premier cas, aucun citoyen chercheur n'est approvisionné, dans le second cas, Alice ne reçoit aucune larve et dans le troisième si tous les citoyens chercheurs sont couverts, les larves étant dans le laboratoire d'Étienne, il est évident qu'aucun citoyen chercheur ne récupère de larves.

Il semblerait que l'on ait mis le doigt sur quelque chose. Pour considérer un plan
d'approvisionnement comme valable, il faut au moins:

  • que tous les citoyens chercheurs soient approvisionnés en larves
  • les larves étant livrées au labo d'Étienne, que le premier convoi parte du laboratoire.

Les conditions qui déterminent si un plan d'approvisionnement est viable sont donc appelées contraintes.

Il existe en réalité une autre contrainte implicite que nous considérerons par la suite:

  • en l'absence de consentement explicite d'Alice, Bob, Charles et Denise, on considère que ces derniers refusent de stocker chez eux des larves pour d'autres citoyens chercheurs (les sagouins...).

Nous aurons l'occasion de revenir sur ce point, mais pour des raisons évidentes, le fait que le domicile d'un citoyen-chercheur ne puisse pas être considéré comme un lieu de transit est le comportement par défaut.

Ok, mais à quel moment on optimise ?

J'y viens! Si je vous présente les deux plans d'approvisionnement suivants et que je vous demande de d'en choisir un...

Solution actuelle
Fond OpenStreetMap, Image CC-BY-SA
Solution alternative en étoile
Fond OpenStreetMap, Image CC-BY-SA

... il y a fort à parier que la seconde solution vous apparaisse comme meilleure. Mais l'est-elle réellement? Comment évalue-t-on la qualité d'une solution? Si je vous demande pourquoi la seconde solution est meilleure, la réponse évidente serait du type:

Il y a moins de trajets.

C'est un fait, la distance cumulée de tous les trajets est plus petite dans le second cas. Mais supposons que l'on pose la question à Étienne et que ce dernier n'ait pas un tempérament prosocial (oui, pour ceux qui le connaissent, c'est dur à imaginer, mais on fait comme si =D). Dans ce cas, n'aimant pas particulièrement être dérangé, que ce soit pout amener des larves à Marie ou pour accueillir Denise qui vient chercher les siennes, Étienne pourrait être tenté de considérer la première solution comme meilleure car elle implique moins d'intéractions sociales.

Si l'exemple précédent peut paraître tiré par les cheveux (même si je suis persuadé que l'on connaît tous au moins un ours qui, à la place d'Étienne, préférerait la première solution), il a le mérite de mettre le doigt sur le fait qu'il n'y a pas de manière universelle d'évaluer une solution.  C'est pourquoi l'optimisation combinatoire implique d'expliciter ce que l'on cherche à minimiser ou maximiser. Celà se fait habituellement sous forme d'une fonction qui attribue un score à une solution, on parle alors de fonction objectif.

Du coup, comment on choisit cette fonction?

Un des points clés de la modélisation d'un problème tel que le nôtre est le choix de la fonction objectif, le but étant de trouver la fonction la plus pertinente possible. Dans notre cas, si la somme des distances paraît être un bon candidat, il existe d'autres possibilités qui peuvent s'avérer bien plus pertinentes et/ou plus équitables. Parmi elles, la distance maximale parcourue par un citoyen chercheur. Étant donnée une solution, sa qualité est déterminée par la plus grande distance parcourue par l'un des citoyens chercheurs pour s'approvisionner en larves. On cherche alors à minimiser cette distance.

À la lueur de cette fonction objectif, toutes les solutions réalisables présentées précédemment sont équivalentes, elles ont le même coût (on parle de coût lorsque l'on minimise et de profit lorsque l'on maximise), à savoir la distance BM qui reste inchangée. Alors pourquoi cette fonction objectif est elle si intéressante?

Considérons le cas suivant qui comprend nos quatre citoyens chercheurs avec des localisations différentes et Étienne. Nos quatre citoyens chercheurs ont lu ce billet et sont maintenant convaincus du bienfondé d'accueillir des larves chez eux pour d'autres citoyens chercheurs. Comme il leur est possible de le faire, ils décident de ne mettre aucune limitation sur la quantité de larves qu'ils sont prêts à héberger (abnégation quand tu nous tiens...).

Scénario bis
Fond OpenStreetMap, Image CC-BY-SA

Si l'on cherche à minimiser la distance totale parcourue, on obtient la solution optimale suivante dans laquelle Étienne fait le tour des citoyens pour leur donner leurs larves.

Scénario bis - minimiser la distance totale
Fond OpenStreetMap, Image CC-BY-SA

Pour ceux qui se disent:

Attends! Si chaque citoyen accepte des larves chez lui, pourquoi on ne prend pas la solution suivante où Étienne amène toutes les larves à Alice, qui prend ce dont elle a besoin et emmène le surplus chez Bob et ainsi de suite jusque Denise?
Scénario bis - chaîne
Fond OpenStreetMap, Image CC-BY-SA

La question est super pertinente, d'autant plus qu'intuitivement, c'est la solution vers laquelle on aimerait tendre. Seulement, un trajet aller implique un trajet retour qu'il est normal de comptabiliser danns le trajet des citoyens. Si l'on évalue la première solution, on obtient le coût suivant:

$\begin{eqnarray}c(sol_1) & = & e + d + c + b + a \\ & = & a + b + c + d + e\end{eqnarray}$

De l'autre côté le coût de la seconde solution est donnée par:

$c(sol_2) = 2a + 2b + 2c + 2d$

En utilisant le fait que $e - e = 0$, et en réécrivant un peu on obtient:

$\begin{eqnarray}c(sol_2) & = & 2 (a + b + c + d) +e - e \\ & = & (a + b + c + d + e) + a + b +c +d - e \\ & =& c(sol_1) + a + b + c + d - e \end{eqnarray}$

Comme la distance $e$ est plus petite que la somme des distances $a + b + c + d$ (merci l'inégalité triangulaire), on a:

$c(sol_2) > c(sol_1)$

et donc la première solution est meilleure que la seconde.

Si l'on considère la seconde fonction objectif qui considère la plus grande des distances parcourues par un citoyen chercheur, le coût de la première solution est égale à la plus grande valeur entre:

  1. la distance parcourue par Étienne,
  2. la distance parcourue par Alice,
  3. la distance parcourue par Bob,
  4. la distance parcourue par Charles,
  5. la distance parcourue par Denise.

Autrement écrit:

$\begin{eqnarray} c'(sol_1) & = & max (dist(etienne), dist(alice), dist(bob), dist(charles), dist(denise))\\ & =&  max(a + b + c + d + e, 0, 0, 0, 0) = a + b + c + d + \end{eqnarray}$

en effet Étienne effectue seul l'ensemble des trajets. De l'autre côté, la solution 2 a pour coût:

$\begin{eqnarray}c'(sol_2)& = & max (dist(etienne), dist(alice), dist(bob), dist(charles), dist(denise)) \\ & =  & max(2a, 2b, 2c,  2d, 0) \\  & = & 2a\end{eqnarray}$

La seconde solution est meilleure que la première (et accessoirement on peut montrer que c'est l'une des solutions optimales autrement dit, il n'existe pas de solution ayant un coût plus petit).

Je clotûre sur ce point le petit moment technique de ce billet, pour en revenir à nos moutons.

Et c'est tout pour le modèle?

On pourrait s'arrêter là, trouver une solution optimale (par exemple celle donnée ci-dessous) sous ces contraintes et basta, tout le monde rentre chez soi avec le sentiment du travail bien fait. On pourrait...

Solution actuelle
Fond OpenStreetMap, Image CC-BY-SA

Seulement, on peut faire mieux.

Mais... s'il s'agit d'une solution optimale, comment peut-on faire mieux?

En effet, il s'agit d'une solution optimale pour ce jeu de contraintes. Mais on peut imaginer des contraintes moins strictes qui restent fidèles à la réalité.

Stocker des larves chez soi

Une première contrainte que l'on peut assouplir est la suivante:

  1. en l'absence de consentement explicite d'Alice, Bob, Charles et Denise, on considère que ces derniers refusent de stocker chez eux des larves pour d'autres citoyens chercheurs.

En quoi est-ce intéressant? Dans le pire des cas, aucun citoyen chercheur n'accepte de stocker des larves et rien ne change. Seulement, il suffit qu'un seul citoyen chercheur accepte de prendre la livraison d'un autre pour que de nouvelles solutions réalisables puissent être choisies et possiblement l'une d'entre elle sera globalement meilleure. Le modèle avec la contrainte assouplie (on parle de contrainte relaxée) est appelé relaxation.

Dans notre exemple, si Alice accepte de recevoir un surplus de larves, la solution suivante est meilleure que la solution initiale:

Solution réalisable avec Alice en stock
Fond OpenStreetMap, Image CC-BY-SA

Dans cette solution la distance maximale est parcourue par Denise, or comme vu précédemment, rien n'empêche Denise d'aller chercher ses larves directement au laboratoire d'Étienne (si tant est qu'il soit bien luné =D). On obtient alors une solution encore meilleure qui s'avère être une solution optimale sous ces contraintes.

Solution optimale avec Alice en stock
Fond OpenStreetMap, Image CC-BY-SA

Cet exemple illustre bien, à mon goût, à quel point la relaxation d'une contrainte peut modifier l'aspect d'une solution optimale.

Récupérer les larves autrement

Une autre contrainte que l'on peut relaxer est celle du lieu. Jusqu'à maintenant, nous avons implicitement considéré que les échanges de larves se font de domicile à domicile. D'autres modalités de récupération/livraison peuvent être envisagées. Il peut être intéressant, par exemple, de récupérer les larves lorsque l'on revient de son travail.

Reprenons l'exemple précédent et supposons que Denise travaille au quartier européen alors que Bob travaille à la gare du Midi. Les trajets sont représentés en bleu sur la carte.

Localisation citoyens avec déplacement travail
Fond OpenStreetMap, Image CC-BY-SA

Il est possible de prendre ce genre de libertés supplémentaires en compte en considérant pour chaque paire de citoyens autant de "trajets" que de possibilité d'approvisionnement possible, le coût de chaque "trajet" étant défini par le distance du détour efectué. Explcitons cette dernière phrase avec un exemple. Considérons le couple (Alice, Bob), Bob peut soit effectuer le "trajet" domicile/domicile. Le coût de ce trajet est donc la distance de l'aller/retour jusque chez Alice, mais il peut aussi effectuer le "trajet" travail/domicile, le coût de ce dernier étant égal à la longueur du détour effectué pour passer prendre ses larves chez Alice en sortant du travail plutôt que de rentrer directement chez lui.

Si l'on considère le couple (Bob, Denise) il n'existe alors aucun "trajet" possible entre les deux puisqu'aucun d'entre eux n'accepte de stocker des larves.

On peut alors dessiner sur la carte, l'ensemble des trajets possible et leur coût associé. Le but étant alors de sélectionner un chemin par citoyen chercheur qui minimise la distance maximale et qui satisfassse aux contraintes non relaxées. Une illustration graphique est donnée ci-dessous, les flèches vertes représentant les trajet domicile/domicile et les bleues les trajets travail/domicile.

Ensemble des trajets possibles
Fond OpenStreetMap, Image CC-BY-SA

Dans l'illustration ci-dessus, les flèches d'orientation ne sont pas indiquées pour garder une illustration relativement lisible. L'idée de cette dernière est surtout de mettre en avant la quantité de trajets possibles pour quatre citoyens chercheurs, un seul ayant accepter de prendre des larves supplémentaires et uniquement deux ayant renseigné un trajet pour le travail.

Ce qu'il faut retenir de tout ça, c'est que plus le nombre de degrés de libertés est grand, meilleure est la solution mais plus dur est le problème à résoudre.

Naturellement, d'autres possibilités peuvent être prises en compte, mais pour ce billet je m'arrêterai là, je pense que vous avez saisi le concept.

Aller plus loin dans la fidélité à la réalité

Un autre point important pour essayer de coller au maximum au problème réel est la notion de temporalité.  En effet, Bob étant veilleur de nuit à la Gare du Midi, il finit tous les matins à 4:00.  Sachant celà il devient peu réaliste d'envisager une solution où Bob passe chez Alice à la sortie du travail.

Pour prendre ce genre de choses en considération il convient d'associer à chaque lieu de livraison/récupération un intervalle de disponibilité permettant de déterminer si le trajet est réalisable. Ainsi pour le couple (Bob, Alice), si Alice renseigne un créneau à domicile de 16:00 à 20:00 et que Bob déclare son trajet de travail entre 4:00 et 4:30, on peut supprimer le "trajet" domicile/travail précédemment cdonsidéré.

Ces contraintes apparaissent assez intuitives, c'est pourquoi je ne m'étendrai pas non plus sur la question.

Bon ça a l'air assez simple, pourquoi n'est-ce pas déjà mis en place?

Naturellement un grand nombre de subtilités ont été passées sous silence pour rester le plus compréhensible et pédagogique possible (j'espère avoir réussi mon pari sur le coup là). Seulement dans les faits la modélisation n'est pas quelque chose de particulièrement évident.

Pour maximiser les chances de résoudre le problème dans des temps raisonnables, il existe toute une série de contraintes sur l'écriture du modèle qui feront peut-être (s'il y a demande) l'objet d'un futur billet.

De plus il n'existe pas un seul et unique modèle pour un problème donné, les choix réalisés dans la modélisation influent grandement sur notre capacité à le résoudre en temps raisonnable. Si certaines tendances peuvent être déterminées (ou tout du moins pressenties à l'écriture du modèle), c'est l'implémentation et les tests qui déterminent réellement l'efficacité pratique d'un modèle.

Et du coup en quoi ça nous concerne?

Afin de pouvoir évaluer l'efficacité pratique d'un modèle et pour pouvoir trouver la meilleure solution possible, il faut des données qui soient le plus proches possibles de la réalité et surtout, et c'est là que le bât blesse, qu'un maximum de citoyens chercheurs acceptent de me fournir des données sensibles (lieux et horaires de disponibilités, adresse, ...) et d'autres moins sensibles mais personnelles quand même (capacité/volonté de stocker des larves, durée maximale de stock, quantité maximale de larves que l'on peut/veut stocker, ...).

La liste complète des données qui me seraient utiles fera l'objet d'une discussion sur le forum du projet, mais si vous êtes intéressés par participer au développement du modèle en fournissant ces dernières n'hésitez pas à manifester votre intérêt auprès de moi.