Discussion :

[bdx3324]

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

[dourouc05]

- est-ce que la dimension de mon problème est trop élevée pour espérer pouvoir trouver une solution

Ça n'a pas l'air délirant. On peut résoudre des MIP de plusieurs millions de variables en quelques minutes/heures (mais pas n'importe lesquels). Maintenant, je pense d'abord à un problème de logiciel en lisant ça :

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.

lp_solve est vraiment mauvais en termes de performance et son développement ne se poursuit pas vraiment. Regarde plutôt un solveur comme SCIP (si la licence te le permet), HiGHS (pas encore parfaitement au point pour les MIP, peut-être déjà mieux que lp_solve), GLPK (si tu dois, il n'est pas vraiment meilleur que lp_solve et son développement est aussi plus ou moins à l'arrêt), Cbc (l'un des moins mauvais solveurs entièrement libres, mais son développement est au point mort), CP-SAT dans OR-Tools (si ta couche de modélisation t'y donne accès), voire un solveur commercial si possible (Gurobi, CPLEX, Xpress-MP).

J'ai l'impression que tu utilises directement lp_solve en R, sans utiliser une couche de modélisation. C'est une très mauvaise pratique, dans le sens où tu ne peux pas changer de solveur facilement (en plus, tu as une API extrêmement difficile à utiliser). En R, tu as ROI comme couche de modélisation de très très bas niveau (https://roi.r-forge.r-project.org/index.html) ou encore OMPR (https://dirkschumacher.github.io/ompr/). À titre personnel, je préfère utiliser Julia pour tout ce qui est modélisation : https://jump.dev/ ; R n'a pas l'air d'être un choix délirant, cependant.

(Pour être complet : parfois, tu dois directement utiliser les interfaces du solveur, surtout quand tu utilises des fonctionnalités très avancées. Cependant, une bonne couche de modélisation te facilitera toujours le travail en n'utilisant que les quelques fonctions avancées dont tu as besoin, tout le reste étant fait dans la couche de modélisation.)

- 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 ?

Oui, ces contraintes peuvent être très utiles. Par contre, si elles sont redondantes (indiquer deux fois la même chose : par exemple, si tu as déjà x <= 1 et y <= 1, inutile d'ajouter x + y <= 2), ça peut ralentir fortement la recherche (ou alors le solveur remarque les contraintes inutiles et les enlève dès le départ).

(Par ailleurs, le solveur commence souvent par générer une série de plans sécants, justement pour éliminer beaucoup de points pas très intéressants.)

Tu parles beaucoup de contraintes avec des coefficients entiers (et loin de 0, -1, +1) : peut-être y a-t-il moyen d'ajouter des coupes de Gomory ? (Faire des combinaisons linéaires de contraintes, diviser par un certain nombre, puis arrondir.) Parfois, ça marche très bien. Souvent, avec un bon solveur (SCIP un peu, CPLEX moyennement, surtout Gurobi), ça sera fait pour toi plus efficacement que tu pourrais jamais le faire en R.

Pour l'analyse de performance, il faut distinguer plusieurs cas (je pars de l'hypothèse que tu utilises un bon solveur, c'est-à-dire pas lp_solve) : le solveur a du mal à résoudre le relâchement linéaire (nœud racine), auquel cas les solveurs MIP ne pourront pas grand-chose pour toi ; le solveur trouve une solution entière, mais a du mal à prouver son optimalité (quelques contraintes pourraient l'aider) ; le solveur ne trouve pas de solution entière rapidement (si tu peux trouver une solution réalisable, donne-la-lui, ça pourra faire beaucoup de différence).

- 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 ?

Non, ça dépend vraiment des cas. Si le relâchement linéaire est irréalisable, le solveur le remarque directement ; parfois, le LP a une solution continue, mais aucune solution entière, c'est un cas où le solveur peut prendre très longtemps pour prouver qu'il n'existe pas de solution.

Sinon, si tu veux de l'aide plus pratique, n'hésite pas à poster ton modèle ici (ou ton code, s'il est assez facile à transposer en modèle) et, idéalement, une instance de ton problème (liste des équipes et toute autre donnée nécessaire pour lancer ton programme).

[tbc92]

Tu as 12 équipes, j'aurais préféré 10 ou 14 ou 2n avec n premier de manière générale.
Pour cette configuration, il y a des mouvements archi-simples qui conviennent. Pour 12 équipes, c'est un petit peu plus compliqué.

Ton besoin, c'est un besoin quotidien pour les clubs de bridge : On a 12 paires, on va faire x tours, (x=6, c'est bien si on a 12 paires), et au bridge, il y a des jeux préparés à l'avance par l'arbitre, et chaque équipe va jouer évidemment une seule fois chacun des jeux.
Pour les mouvements simples (2n paires avec n premier), les joueurs connaissent par coeur la disposition.
Pour les mouvements tordus, parce que le nombre d'équipes est trop petit, voici un lien : mouvement howell

Edit : je me rends compte en relisant que c'était plus l'exercice de programmation que la solution elle-même qui t'intéressait, tu pourras au moins comparer ta solution avec celles proposées sur ce lien

[bdx3324]

Bonjour et un grand merci pour vos réponses.

Effectivement, plus que la solution en soi (qui m'intéresse quand même, il y a une finalité !), c'est également la méthode & le code qui m'intéressent. Cependant, j'aimerais si possible éviter de devoir installer et prendre en main des softs que je ne maîtrise pas pour y aller. Dans l'idéal, j'aimerais rester sur mon simple code de programmation linéaire où je n'ai qu'à définir la matrice des contraintes linéaires et hop retrouver la solution. En soi je me fiche que mon solveur ne soit pas hyper efficace, enfin tant que c'est raisonnable. Que ça dure 1h ou 3h ce n'est pas grave ; que ça mette 1 semaine au lieu de 30 secondes en revanche si ! Là mon problème est que même au bout de plusieurs jours de calcul... toujours rien, il doit y avoir une erreur de ma part !

En jouant un peu avec mon programme, je pense que j'ai des contraintes redondantes, et visiblement ça ralentit l'exécution. En effet, je m'étais noté des contraintes à satisfaire, et sur un cas avec 10 équipes, 5 terrains, 5 rencontres, selon que je définis certaines contraintes ou pas, le temps d'exécution pour trouver une solution passe de 43s à plusieurs minutes. Est-ce que ça semble cohérent ? Avoir des contraintes redondantes ralentit (peut-être de manière très drastique avec la dimension) le temps pour trouver une solution ? Et au contraire, j'ai l'impression qu'ajouter certaines contraintes va permettre d'accélérer la résolution.

Dans ce cas, je me demandais comment vous me conseilleriez de procéder afin de ne définir que des contraintes indispensables, et éliminer celles qui sont redondantes (si souhaité je peux vous détailler l'ensemble des contraintes que j'ai définies et on les passe en revue) ?

Merci d'avance pour votre aide !

[dourouc05]

Que ça dure 1h ou 3h ce n'est pas grave ; que ça mette 1 semaine au lieu de 30 secondes en revanche si ! Là mon problème est que même au bout de plusieurs jours de calcul... toujours rien, il doit y avoir une erreur de ma part !

Avec un très mauvais solveur comme lp_solve, c'est très possible que le problème ne vienne pas de toi et que plusieurs semaines de calcul ne suffisent pas.

Sinon, pour le reste de ton paragraphe : tu maîtrises LP_solve et son fonctionnement interne ?

Est-ce que ça semble cohérent ? Avoir des contraintes redondantes ralentit (peut-être de manière très drastique avec la dimension) le temps pour trouver une solution ? Et au contraire, j'ai l'impression qu'ajouter certaines contraintes va permettre d'accélérer la résolution.

Avec un très mauvais solveur, l'impact peut être extrêmement grand : les autres ont une phase de presolve efficace pour limiter l'impact de contraintes trop redondantes.

De manière générale, beaucoup de contraintes limitent la performance d'un solveur LP (purement continu : la complexité dépend du nombre de contraintes), mais peuvent grandement améliorer celle d'un solveur MIP (discret : les contraintes peuvent éliminer des solutions extrêmes fractionnaires, entre autres -- la complexité reste exponentielle en le nombre de variables dans le pire cas).

Dans ce cas, je me demandais comment vous me conseilleriez de procéder afin de ne définir que des contraintes indispensables, et éliminer celles qui sont redondantes (si souhaité je peux vous détailler l'ensemble des contraintes que j'ai définies et on les passe en revue) ?

Une première série de contraintes redondantes, c'est celles qui sont identiques ou multiples les unes des autres : x <= 1 et x <= 1 et x <= 2. Tu espères que ta matrice de contraintes ait un rang de trois, eh non, ce n'est que un.

L'idéal serait de voir tout ton modèle, on pourrait voir ça plus ou moins facilement (ou tenter sur un autre solveur). Tu dois pouvoir générer un fichier LP avec write_lp pour l'API C (http://web.mit.edu/lpsolve/doc/write_lp.htm). Fais attention à bien nommer toutes les variables et les contraintes, c'est beaucoup plus facile pour s'y retrouver. Ce n'est pas toujours facile de découvrir ces problèmes avec une écriture mathématique (parfois, une somme complexe se réduit à un terme de manière pas évidente à voir, par exemple).