Bonjour.
J'ai un petit problème que je n'arrive pas à résoudre, c'est de la RO, un programme linéaire plus précisément.
J'ai 12 équipes qui s'affrontent, il y a 6 tours, et durant chaque tour tout le monde joue. Elles ne peuvent donc pas toutes s'affronter, mais on va faire en sorte qu'elles s'affrontent au plus une fois.
Jusque là pas de problème particulier, cela ressemble à la génération d'un calendrier pour la Ligue 1 ou le Top 14. Simplement j'ai une contrainte additionnelle : il y a 6 jeux différents, et j'aimerais que au cours des 6 tours, chaque équipe ait exactement joué une fois à chaque jeu. Comme si, pour revenir à mon analogique au Football ou au Rugby, Paris, Lyon, Marseille, Toulouse, Lille et Bordeaux accueillaient les matchs, et qu'on voulait faire en sorte que chacune des 12 équipes passe dans chaque stade exactement une fois.
J'ai formulé mon problème comme un programme linéaire dont l'objectif est une fonction constante car le gros morceau consiste à trouver une solution qui valide un gros ensemble de contraintes. En effet, j'ai programmé de manière à ce qu'on trouve une solution x \in {0,1}^d, où, si la n-ème composante de x vaut 1 cela signifie "telle équipe i affronte telle équipe j sur le terrain k lors de la journée l". Il y a donc tout un tas de contraintes. Par exemple : deux équipes i et j ne peuvent s'affronter qu'une fois au plus. Chaque équipe i se retrouve sur le terrain k exactement une fois. Chaque équipe i apparaît exactement une fois à chaque journée. Chaque terrain k est occupé exactement une fois lors de chaque journée l, etc. etc., si besoin je vous donnerai la totalité des contraintes que j'ai définies. Il y en a un peu plus de 200 si je me souviens bien. Petite remarque sur mon d : il vaut nombre de paires d'équipes x nombre de jeux x nombre de journées, soit dans mon cas 12*11/2*6*6 = 2376. Je ne connais pas grand chose aux programmes linéaires, mais peut-être que plein d'alarmes sont déjà en train de sonner dans vos têtes ?
Bref j'ai testé mon programme (pour être honnête je n'ai pas vérifié que la solution retournée était bel et bien correcte) avec des cas plus simples, i.e. 6 équipes, 3 jeux et 3 tours ; 8 équipes, 4 jeux et 4 tours. Le programme linéaire est résolu en moins d'une seconde. Avec 10 équipes, 5 jeux et 5 tours, ça dure un peu plus longtemps, une bonne minute 30. Avec mon problème original en revanche... ça tourne depuis plusieurs jours sans trouver de solution.
Etant totalement ignorant en recherche opérationnelle, je me demandais si vous aviez à tout hasard des conseils à me donner pour comprendre ce qui ne va pas. Quelques questions concrètes :
- est-ce que la dimension de mon problème est trop élevée pour espérer pouvoir trouver une solution
- j'ai tenté des versions bis de mon problème en supprimant/relaxant certaines contraintes. Mais à la réflexion je me demandais si les contraintes n'étaient justement pas utiles pour "contraindre" (CQFD) le problème et éliminer d'emblée un très grand nombre de solutions à ne pas considérer ? Est-il possible que si mon programme tourne depuis si longtemps, c'est justement qu'il manque certaines contraintes qui permettraient au solveur de "faire le tri" plus rapidement ?
- j'ai l'impression que lorsque le problème est infaisable, le solveur le constate immédiatement et ne passe pas des heures/jours à mouliner, est-ce vrai ?
Pour info, car je me rends compte je ne l'ai mentionné nulle part pour le moment, j'ai codé ça en R avec le package lpSolve.
Merci d'avance pour vos réponses et pour votre aide, et bonne soirée
Partager