Optimiser l'organisation d'une soirée

Bonjour,

ça doit faire un moment maintenant que je planche sur un problème qui peut paraître simple, mais qui est pour le moins assez complexe : Optimiser le placement des invités d'un mariage afin qu'ils passent globalement une bonne soirée.

On sait tout a quel point c'est un calvaire à réaliser. L'objectif de mon programme est de prendre en entrée des données sur les invités, et faire une proposition de placement aux organisateurs.

Les données du problème

Voici les éléments dont je dispose :

• Type d’événement à organiser : une soirée de mariage
• Nombre d'invités : $100 \leq N \leq 150$
• Nombre maximum de personnes par table : $6 \leq max \leq 10$
• Caractéristiques connues de chaque invité :
  • age (je pensais partir sur des fourchettes d'age)
  • sexe (masculin, féminin)
  • statut (étudiant, travailleur)
  • orientation sexuelle (hétéro, bi, homo)
  • langues parlées
  • pays déjà visités (dont le nombre de temps qu'ont y a passé en gros)
  • le domaine d'étude/travail (droit, informatique, marketing, social, finance, etc.)

Pour chaque invité, on sait aussi s'il existe des relations (couple, amis, patentée, fratrie, etc) entre eux.

L'objectif à atteindre

Le type d’événement étant un mariage, j'ai commencé à élaborer des règles que je pense pouvoir faire partie de la fonction de décision :

1. La relation de couple est une relation très forte. Il est donc obligatoire que chaque couple soit sur la même table
2. La relation d'amis est la deuxième relation prioritaire après celle du couple
3. On essayera d'éloigner les invités qui sont en relation de parentés
4. La relation de fratrie n'a pas beaucoup d'importance
5. Chaque invité doit avoir le maximum de personnes qui parlent la même langue que lui sur sa table
6. Les invités appartenant à une orientation sexuelle minoritaire (ex : homo) doivent être sur la même table (on paramètrera un homo comme étant autre chose si on sait qu'il ne veut absolument pas être régi par cette règle)
7. On essayera de rassembler les invités qui ont déjà vécus dans les même pays sur plus de 6 mois
8. On essayera de rassembler les invités dont le domaine est proche

Mes interrogations

Merci de m'avoir lu et pour vos retours qui me seront précieux.

Je ferais une programmation linéaire, c'est grosso modo fait pour ca non ?

Les invités appartenant à une orientation sexuelle minoritaire (ex : homo) doivent être sur la même table (on paramètrera un homo comme étant autre chose si on sait qu'il ne veut absolument pas être régi par cette règle)

Je trouve casse gueule la règle de regroupement des homos à une même table. Ça donne l'impression de les parquer toutes ou tous au même endroit.

En fait je pense qu'il faut élargir à un critère "cherche à se caser oui/non", qui bien sûr sera valable pour tout le monde (tout en prenant en compte l'orientation sexuelle, bien sûr). Ainsi on ne met ensemble des prétendants potentiels uniquement s'ils le veulent. Tous les célibataires ne veulent pas forcément se caser.

Alors déjà on va aller directement dans les choses intéressantes en balançant par la fenêtre le fait qu’on s’intéresse à l’organisation d’une soirée. Je serais ravi de discuter sociologie, éthique et autres joyeuseté mais dans un autre topic alors.

Bref on a $N$ tuples que l’on souhaite regrouper par paquet avec différentes contrainte plus ou moins forte sur la valeur de chaque dimension les uns par rapport aux autres.

Une fois les contraintes correctement établies, c’est un problème classique d’optimisation multiobjectif. Il y a des softs qui existent pour ça. Pour creuser la théorie derrière on sort clairement de mon domaine de compétence, peut être que @Höd aurait des choses à dire par contre.

Bonsoir,

Déjà, la première chose qui n'est pas clair est ce que tu cherches à optimiser. Il y a beaucoup de contraintes et je pense sans trop m'avancer que le problème est sur-contraints, notamment parce que la relation 1. posée comme une contrainte non-relaxable défini un problème d'affectation optimale (résolvable en temps polynomial par contre) et il se peut qu'il ne possède qu'une solution. Rajouter une contrainte par dessus ne permettra pas de satisfaire toutes les contraintes.

Le problème de la surcontrainte est qu'il risque de ne pas y avoir de solution faisable (i.e. qui satisfasse toutes les contraintes) et donc il te faudra te contenter d'une solution faisable modulo la relaxe d'une ou plusieurs contraintes. Oublie donc la satisfaction de contraintes (si ce n'est la première relation qui te semble obligatoire).

Je proposerais de partir de la résolution du problème posé par la relation 1 et qui te donne déjà des contraintes fortes sur les placements possibles. Ensuite je vois deux solutions: - Si tu as un ordre strict sur les relations que tu proposes, tu pars d'une solution $x_1$ de $P_1$, et tu résous $P_2$ au mieux selon $x_1$. Si $P_2$ est ok, tu passes à $P_3$, etc. Si tu n'arrives pas à résoudre, alors tu repars de $x_2$, une autre solution faisable de $P_1$. Dès que tu arrives à résoudre la dernière contrainte, tu as une solution faisable, sinon, celui qui arrive le plus loin est la meilleure solution faisable (et si tu as plusieurs solutions qui vont aussi loin, à toi de trouver de quoi les départager, typiquement sur la manière dont ils échouent plus ou moins sur le dernier problème rencontré) - Si tu n'as pas d'ordre strict, alors tu reprends la même procédure mais au lieu d'une sélection linéaire du problème suivant: P_{i+1}, tu fais du Branch and Bound (mais cela t'oblige à définir une fonction objective pour chaque problème en amont).

Là tu as une méthode de résolution probablement optimale car (semi-)exhaustive. Par contre, en pratique je ne suis pas sur que cela passe car l'espace de recherche, bien que fortement contraint, est gigantesque.

Pour moi ici, il n'y a pas forcément à parler de multi-objectif.

Si jamais ça peut aider : jetez un oeil

C'est marrant, j'ai l'impression que ça ressemble beaucoup à ce que j'étudie en cours en ce moment.

Si tu as k tables disponibles, il s'agit de partitionner un graphe en k classes à peu près équivalentes de manière à minimiser les poids des arètes inter-classes (le graphe représentant les liens entre les différentes personnes et pouvant être généré à partir de la liste des invités). C'est un problème NP-complet, et on nous enseigne comment résoudre ça habilement avec différentes méthodes (énumération, descente de gradient, recuit simulé, recherche tabou, algorithme génétique etc…).

Peut être que je m'emballe et qu'il y a mieux, mais l'un de mes projets de ce semestre est de résoudre ce problème avec plusieurs méthodes.

Oo merci pour toutes ces réponses déjà.

@Shig : ton idée me parait plus pertinente. Je vais rajouter cette règle

@Simbilou : autant c'est la première idée qui m'a sauté aux yeux, autant, je n'arrive pas encore à voir comment modéliser mes objectifs car on a une relation entre objectifs eux meme.

@Hod: "sur-contraint" c'est exactement le terme dans mon cas. Merci je n'arrivais pas a mettre la main la dessus.

Tu me rassures. Mais étant mal habitué aux SAT je croyais qu'on pouvais l'appliquer meme dans des cas ou tout n'est pas satisfaisant.

Et c'est là que le bas blesse. Autant je peux obtenir une pondération sur la force des règles les unes par rapport aux autres, autant je n'ai pas d'ordre strict sur les règle. Deux règle peuvent etre équivalente. Et là ta méthode de parcours ne marche plus pour moi. Donc comme tu l'as dis, ça serait plutot du Branch and Bound. Bon par contre, va falloir plus d'explication pour que je pige quelque chose à la manière de faire.

Mais contrairement a ce que tu dis, j'ai l'impression que le voir comme du multi-objectif avec pondération peut convenir avec une complexité correcte. Me trompe-je ?

@Bibiye : j'ai tenté la modélisation par graphe, et pouf toujours le meme problème trop d'objectif a atteindre.

@ Tous : En fait je bloque surtout à la modélisation du problème, si vous avez des propositions dans ce sens, ça m'aiderait à y voir clair.

En multi-objectif on parle d'aggrégation. Ces méthodes présentent beaucoup de désavantages par rapport à des méthodes de type Pareto: - Elles ne donnent qu'un point du front de Pareto et il faut donc les relancer plusieurs fois avec des pondérations différentes pour obtenir plusieurs points - Elles ne permettent pas (pour les versions simples) d'obtenir les parties concaves du front de Pareto.

Je développe plus tard, je n'ai pas trop le temps aujourd'hui.

Pour moi, ce type de problème se résout par une fonction d'évaluation. Chaque combinaison peut être évaluée par une note. Et on cherchera la combinaison qui obtient la meilleure note.

Exemple :

Note par défaut = 10000 points.

• Pour chaque couple séparé, on perd 1000 points

• A chaque table, on cherche à avoir des groupes homogènes en âge. pour chaque table où l'écart ageMaxi-AgeMini est trop élevé, on perd x points.

• Pour chaque table où on a des personnes incompatibles (militants politiques de bords opposés), on perd x points.

etc, etc, à toi de voir comment tu quantifies chaque objectif.

Je crois que cet exercice de quantifier chaque objectif te permettra déjà de mieux définir les objectifs visés. Cette étape est donc essentielle dans ta démarche, même si l'algorithme retenu n'est pas à base de 'note'.

Après, il faudra attaquer l'aspect algorithme, pour trouver la combinaison qui conduit à la meilleure note.

Une petite proposition de débutant en la matière, une approche génétique ne serait elle pas interessante ? Surtout si le problème est NP. En faisant ainsi tu pourrais éliminer peu à peu les contraintes forte tout en optimisant un maximum.

Par contre comment juges-tu "je passe une bonne soirée" ? Et il manque une contrainte je trouve dans les relations, ce sont les personnes qui ne peuvent pas se blairer (des ex par exemples).

Si quand tu auras avancer tu as une proposition d'entrée ce serait sympa pour s'amuser dessus

« Résoudre par une fonction d'évaluation » ne veut en soit rien dire.
Trouver ou établir la fonction d'évaluation d'un problème fait parti de l'étape de formulation du problème et non pas de résolution.

Comme je le disais, appliqué une méthode de résolution à des combinaisons de fonctions d'évaluation s'appelle une méthode d'agrégation et possède beaucoup d'inconvénients, jusqu'à l'oublie de solutions potentiellement optimales (non-accès aux zones concaves du front).

@Ricocotam, une approche génétique serait en effet une très bonne approche vu l'aspect peu structuré du problème. D'autant que ce sont les seuls algorithmes efficaces pour la résolution de problèmes multi-objectif avec approche Pareto. Mais avant de faire cela, il faut modéliser le problème correctement, et il y a plein de manières de faire.

Je ne sais pas si c'est un exercice, qui souhaite faire ressortir un problème de contrainte ou un besoin personnel mais dans ce cas. Je trouve que vos réponses sous-estiment la partie de "science humaine". Vous aurez beau avoir le plus parfait des programmes, sans contrainte viable le résultat sera médiocre et la soirée ennuyante. Je pense que considérer les contraintes comme une gêne pour l'algorithme, est une erreur. C'est à l’algorithme de s'adapter au contrainte.

Comment comptes-tu collectés les données ? Tu souhaites utiliser les connaissances des futurs-mariés et les parents (organisateurs) ?

Je rejoins l'idée de ShigeruM, comment vas-tu savoir si les personnes sont hétéro, bi, homo ? Si ils sont en couple ou "affirmé" c'est évident, mais bi ? Tu vas leur demander dans l'invitation ? J'ose même pas imaginer comment tu souhaites demander si ils veulent-être placer en fonction de leur genre… C'est vraiment "casse gueule".

Je pense que regrouper par domaine (métier) est une mauvaise idée, une soirée permet de nous éloigner de la routine et des heures de travail. Ensuite parler à quelqu'un qui fait la même chose limite l'épanouissement, et la conversation en elle même. Oriente toi vers les activités et les loisirs (voir la suite de mon message).

Faire une table 3ème age n'est pas un super critère. Pour la table des enfants il suffit de les isoler avant de lancer le "vrai algorithme".

Ensuite je rajouterais les caractéristiques/contraintes suivantes (selon les informations que connaissent la famille et les futurs-mariés) :

• Communication (note de 1 à 12) : Parle beaucoup ou pas, c'est une notion importante je pense, mettre en place une moyenne à respecter sur chaque table (1 à 4 ne parle pas beaucoup, 4 à 8 tiens une discussion, 9 à 12 parle beaucoup et peu relancer la conversation sans problème).
• Activité/loisir (choix multiple, par catégorie : sport ; art ; association ; religieux ; cuisine) : ainsi que la fréquence par semaine. Une personne avec une activité fréquente aura un sujet de discussion supplémentaire. (Peut-être envisager de diviser le sport en sous catégorie).
• Centre d'intérêt et passion (choix multiple) : La passion souvent sera reflété par le fréquence du loisir, mais on peut aussi définir les centres d'intérêts (de discussion).
• Ce que les gens n'aiment pas (personne, ou domaine/centre d'intérêt).
• Relier les personnes entres leurs domaines (de compétence/travail), loisirs et centres d'intérêts. Par exemple : un maitre nageur, et quelqu'un qui nage plusieurs fois par semaine ; Une personne qui aime l'art/dessine, et une autre personne qui travaille dans ce domaine, etc…
• Associer des personnes sans loisirs avec une personne qui à un loisirs fréquent et parle beaucoup (notée entre 8 ou 12).
• Ne pas mettre un adolescent tout seul à la table des enfants.
• "De préférence, placez les gens qui se connaissent ensemble ou par affinités ; la glace est déjà rompue ! Ils se sentiront plus détendus et l’ambiance générale y gagnera" conseil de l'article de plan-table.fr.

• Deux règles de confort, pour éviter une amertume :

  • Éviter de mettre un célibataire a côté d'un jeune couple (marié ou non), ou d'une personne du sexe opposé et du même age étant "en couple".
  • Faire attention au couple qui ne peuvent pas avoir d'enfant, ne pas les mettre avec un couple de jeune parent.

Pour ce qui est du nombre de table, le nombre peut varier de 10 à 25 tables, il y a-t-il une limite du nombre de table ? D'ailleurs j'aime l'idée du placement des tables dans cette article sur le plan de table.

• Comment tu comptes gérer les bébés ? Table enfants ou avec leurs parents ? Ou selon le choix des parents ?

Pour une approche rapide, sachant que les données et les contraintes fournies sont subjectives, et que leur simplicité ne permettent pas de solution précise et d'optimisation parfaite, mais uniquement des solutions envisageable. Je ferais comme ceci :

1. Je considère les couples comme un seul invité qui compte double en place assise (et je fusionne leurs caractéristiques, mais je garde dans une autre variable leur indépendance, pour définir le sens du couple gauche/droite). Et je les compte triple si ils ont un bébé ? (Ou tu peux faire cette fusion à l'étape 4).

2. On commence à isoler les enfants, on vérifie si on peut tous les mettre à une table (j'accepte le fait de rajouter une assiette). Dans le cas contraire, on isole les enfants des adolescents. On diminue le minimum à 5 (maximum de chaise par table divisé par deux), si il n'y a pas assez d'adolescents je les mets dans une table où il reste de la place.

3. Une fois la population réduite, on commence avec une boucle sur chaque individu, qui créer un classement "du meilleurs voisins de table" avec un pourcentage "d'entente" (ce classement est un produit du résultat obtenu pour chaque contrainte). Puis obtenir la somme de tous les classements pour obtenir un classement de popularité (c'est-à-dire que la première personne à plus d'affinité avec d'autres invités que la deuxième).

   C'est dans cette étape 3, qu'on définit la priorité d'une contrainte et le pourcentage d'influence de la contrainte

4. Réalisation de l'étape 1, fusion des couples en une seule personne (moyenne des 2 classements du meilleurs voisins, il faut penser à ajuster le classement de popularité, et le pointeur sur le classement du meilleur voisin de chaque invité), réaliser cette étape maintenant, permet d'obtenir un classement des meilleurs voisins plus juste.

5. (Je me demande si il n'y a pas un algorithme existant utilisable ici, comme celui du Sudoku qui consiste à supposer X nombres possible sur une case et ensuite essayer plusieurs combinaisons).

   Une fois que tu as ce classement de popularité, tu vas commencer à placer le dernier à une table. Puis tu piocheras(*) dans les premiers (+/- 10% d'entente) du classement des meilleurs voisins de cette invité celui avec la plus faible popularité. (Tu peux tenir un deuxième classement à jour (que tu modifieras à chaque placement) sur la popularité des invités qui reste à placer).

6. Plusieurs déplacements seront nécessaire pour trouver un taux de satisfaction global.

   (*) Tu peux mettre un seed, choix aléatoire quand tu pioches pour avoir un résultat différent à chaque génération.

Sinon la seule solution qui fonctionne et don je suis partisan : Laisse les gens se placer et faire leur propre placement. Pendant qu'ils attendront le début de la cérémonie, ou entre la cérémonie et le restaurant, les gens vont commencer à discuter avec des personnes… J'entame le débat de la nécessité de planifier ses vacances pour chaque jour.

Je trouve que vos réponses sous-estiment la partie de "science humaine".

Parce qu'il n'y a pas à considérer de partie sciences sociale sur la partie résolution. Il pose un problème et nous donne ses contraintes, il dit qu'il veut pour sur satisfaire la première et pour le reste il s'en moque. On apporte des solutions qui sont indépendantes de ses contraintes ce qui signifie que s'il change d'avis sur le problème et veut rajouter ou modifier des contraintes, ce n'est pas un soucis.

Contrairement à l'approche que tu prones qui: 1. Modifie le problème posé par l'OP sous prétexte que ses critères ne t'intéressent pas ou ne satisfont pas. 2. Propose une solution excessivement dépendante de l'instance du problème posé et donc pas reproductible. 3. Ta solution est encore une fois la même que celle décrite par tout le monde, en moins générale, c'est à dire une solution par aggrégation, qui possède toujours les même défauts, contrairement à des approches plus général de type Pareto (pour une petite introduction, cf. ce message.

J'ai ptet' raté un message dans le lot ou même mal lu le premier mais t'as pensé à utiliser un solveur de contraintes type Choco c'est vraiment conçu pour résoudre ce genre de problèmes.

Après si y'a une volonté didactique derrière, ça peut être intéressant de jeter un oeil aux sources de la lib.

A mon humble avis, je pense que tu ne prend pas en compte une chose fondamentale : l'envie de la personne a être (pour chaque critère) avec des personnes qui partagent ces critères ou non.

Je te prend un exemple sur les langues : moi je parle allemand par exemple(en plus de l'anglais, que tout le monde parle un peu, à différents niveaux) . Je ne veux surtout pas être mis avec d'autres allemand à table, non ! je préférerai être avec des hongrois, des japonais…etc.

Enfin personnellement j'adore découvrir de nouvelles cultures, partager des nouvelles expériences avec tout le monde. notamment avec la jolie fille sur laquelle j'ai jeté mon dévolu . Je ne veux surtout pas être avec "uniquement des gens que je connais ou avec laquelle on a des points communs !"

Je pense que pour avancer ce serait plus sympa que firm1 nous fournisse un jeux de données de test…

@gusfl

Dans l'approche, j'aurais tendance à dire que firm1 cherche un solveur de contraintes et que dans ce topic on devrait laisser de côté la définition de contraintes justement.

Après, à lui de modéliser ses contraintes, de leur donner un poids etc. (et à la rigueur ouvrir un topic pour ça, histoire que tout le monde donne sa vision des contraintes de placement à un mariage).

Mais d'un point de vue purement technique, pour résoudre le problème à partir de contraintes fournies, je ne vois pas de raison d'aller chercher ailleurs qu'une lib de programmation par contraintes et éventuellement d'aller en lire les sources si les algos l'intéressent (Choco, Cream, JaCoP, python-constraint pour ceux que j'ai déjà vus fonctionner). Voire carrément de réimplémenter une telle bibliothèque (ou au moins un algo) si jamais il souhaite bien comprendre ce qui se trame sous le capot.

En fait j'ai l'impression que mon besoin n'est pas bien compris.

Mon problème a deux plusieurs volets :

1. Identifier les règles qui me permettent de placer tout le monde correctement
2. Modeliser le problème
3. Résoudre le problème

Pour l'étape 1, j'ai trouvé quelques règles qui me paraissent logique, mais je ne sais pas si j'en ai oubliés certaines. Avec les messages de Shig et A-312 je crois que je vais rajouter 2 règles en plus.

Pour l'étape 2, je ne cherche pas un solveur, j'en connais plein. Mon problème réside surtout dans "sous quel forme le modéliser". Une fois que j'aurai répondu à cette question clé, j'aurai tout débloqué. Höd a des pistes qui me semble intéressante, mais j'avoue que j'ai un peu de mal à comprendre son vocabulaire un peu trop théorique je trouve.

Peut-être au final que Kje a raison et que je devrais fournir un Jeu de donnée de tests pour que ça avance ?

Et sinon pour A-312, mes données sont issues de la connaissance que les mariés ont de leurs invités. Donc tu t'imagines bien qu'ils ne vont pas faire passer un questionnaire à aux invités.

Il est bien connu que faire un dessin, débloque souvent les choses…

Donc pour

Peut-être au final que Kje a raison et que je devrais fournir un Jeu de donnée de tests pour que ça avance ?

Je dirais, oui ! Encore faut-il que ton exemple permette de comprendre le problème, à toi de bien le choisir.

J'ai adapté ma réponse sur cette hypothèse, connaître les activités/loiris/centres d'intérêts ne posent pas trop de problème (si on a un minimum d'intérêt pour la personne). Et tu peux récupérer ces données en appelant la personne pour prendre des nouvelles (en glissant des questions dans la conversation).

Avant de réaliser l'exemple, il faudrait fixer les caractéristiques nécessaires.