Bonjour,
J'ai un peu de mal à cerner la différence entre la programmation par contrainte et la programmation linéaire.
Quelqu'un pourrait-il m'expliquer ?
Merci !
Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Discussion :
Différence entre programmation par contraintes et linéaire
Bonjour,
J'ai un peu de mal à cerner la différence entre la programmation par contrainte et la programmation linéaire.
Quelqu'un pourrait-il m'expliquer ?
Merci !
Avec la programmation linéaire tu modélises les relations entre les variables via un ensemble d'équations linéaires et avec la programmation par contraintes tu modélises les relations entre les variables de te problème via un ensemble de contraintes (c-a-d relations logiques etc qui ne sont pas forcement linéaires. Par exemple il existe la contrainte "alldifferent" obligeant les variables à prendre des valeurs distinctes etc). Regarde la doc d'un solveur de contraintes si tu veux une idée plus précise du genre de contraintes que tu peux rencontrer.
Ça change complètement l'approche utilisable pour la résolution. Avec un approche par contraintes la résolution se basera sur le parcours d'un arbre de recherche avec affectation de variables/retrait des valeurs devenues impossibles/etc.
Merci pour ta réponse ! Sa m'aide, mais c'est encore un peu flou :
Est ce qu'on peut dire que la programmation linéaire est un cas particulier de la PPC ou les contraintes sont linéaires ?Avec la programmation linéaire tu modélises les relations entre les variables via un ensemble d'équations linéaires et avec la programmation par contraintes tu modélises les relations entre les variables de te problème via un ensemble de contraintes (c-a-d relations logiques etc qui ne sont pas forcement linéaires.
Ok, ca je comprend. Avec une approche par contrainte on résous avec les arbres de recherches.Ça change complètement l'approche utilisable pour la résolution. Avec un approche par contraintes la résolution se basera sur le parcours d'un arbre de recherche avec affectation de variables/retrait des valeurs devenues impossibles/etc.
Et avec la programmation linéaire ? On ne résoud pas avec un arbre de recherche ??
Ce que j'ai du mal à comprendre, c'est la méthode de résolution.
Par exemple, pendant un stage j'ai modélisé un problème de VRP à l'aide d'équation linéaires. Et j'ai optimisé mon problème ainsi modélisé à l'aide d'un solveur de contraintes (ILOG)... Ce qui fait que franchement, j'ai du mal à voir la frontière entre les deux...
Je précise que je n'ai pas eu de formation en RO, et que j'ai appris "sur le tas". Ce qui explique que certains concepts soient un peu confus pour moi.
Tu pourrais effectivement modéliser un problème en PPC en utilisant que des contraintes linéaires. Mais je ne pense pas que le solveur sache en tirer partie. Les méthodes de résolution n'ont vraiment rien à voir.Envoyé par darnold
L'autre différence est aussi que la PPC travaille avec des variables définies sur des domaines finis entiers alors que la PL non. La PLNE (PL avec des entiers) ressemble beaucoup à la PL (du point de vue de la modélisation) mais la résolution ne peut pas s'appuyer sur les mêmes mécanismes que la PL.
J'ai appris la PL sur le tas mais pour la partie PPC théorique je connais relativement bien.
Dans un solveur de contraintes généralement ça se passe de la façon suivante :
- suivant une heuristique le solveur décide de fixer la valeur d'une des variables.
- Il examine ensuite chacune des contraintes pour voir si a cause de cette affectation il y a des valeurs à enlever dans le domaine des autres variables.
A chaque retrait de valeur il revérifie chaque contraintes jusqu'à atteindre le point fixe. A ce moment soit :
- chaque variable est affectée : on a trouvé une solution,
- une variable n'a plus de valeur dans son domaine de définition : pas de solution, il faut remettre en cause l'un des affectations faite par le solveur et choisir une autre valeur pour la variable,
- une variable a plus d'une valeur dans son domaine : on fixe une de ces variables et on continue la recherche.
La PL elle va se baser sur des approches comme le simplex qui va consister à parcourir les "coins" du polyèdre formé par les équations linéaires.
Pour la PLNE, la recherche (banch and bound par exemple) va aussi suivre un "arbre de recherche". A chaque nœud, on va cherche une borne max/min afin de déterminer s'il peut y avoir une solution intéressante dans cette partie.
Voila pour résumer, j’espère que ça t'aidera un peu (désolé pour la mise en forme je manque un peu de temps).
Si j'ai bien compris :
- la PLNE permet la recherche de l'optimum à l'aide de méthodes pour parcourir l'arbre de manière efficace.
- La PPC vas tenter de trouver une solution à l'aide d'heuristiques qui vont lui permettre de fixer telle ou telle variable, jusqu'à avoir trouver la bonne solution.
Sa m'amène à plusieurs remarques qui sont peut-être fausses :
1/ La PL permet de trouver l'optimum alors que la PPC permet juste de trouver une solution ?
2/ La PPC ne permettant pas de trouver l'optimum, on est donc contraint de recourir par la suite à des algos de recherche locale (genre Tabou) pour améliorer la solution ? (j'ai remarqué cette méthodologie dans plusieurs publications...)
3/ Vu ces deux réflexions, la PL semble plus efficace dans la qualité du résultat. Je suppose que sa se compense par la complexité temporelle des algo utilisés qui doit être plus élevée que la PPC ?
PS : je vais être amener à faire un compte rendu sur le sujet à mon chef de projet. Histoire de "sourcer" mes informations, et sans être indiscret, quelle est ta situation ? Es-tu un professionnel, un chercheur, un étudiant, un enseignant ? En tout cas, merci pour tes précieuses lumières
Le but du jeu c'est de détecter au plus tôt les parties de l'arbre de recherche qui ne peuvent pas mener à une solution (cf. branch and bound).
Un élément clef pour l'efficacité de la PPC c'est la propagation, c'est à dire la capacité à détecter les valeurs inconsistantes dans les domaines des variables (c'est à dire les valeurs qui ne peuvent pas participer à une solution étant donné les variables fixées par le solveur). Là encore le but est de ne pas trop perdre de temps dans des parties de l'arbre de recherche où il n'y a pas de solution.
La PPC permet de prouver la "satisfiabilité" (autrement dit qu'il existe bien une solution pour un ensemble de contraintes). Mais on peut faire de l'optimisation avec de la PPC, en posant une contrainte sur ta "fonction objectif". En gros, on résout une première fois le problème pour trouver une solution (ou on sait calculer directement une borne). On calcule le cout de cette solution. Puis on re-résout le problème en rajoutant une contrainte de la forme : cout(solution) < cout_solution_trouvée (pour une minimisation). On recommence à chaque nouvelle solution trouvée... jusqu’à ce qu'on trouve plus de solution. On sait alors que la dernière solution trouvée est la solution de cout min (et inversement pour une maximisation).
Cf. ma réponse à ta question précédente. On peut utiliser la PPC comme première étape parce qu'on a besoin d'une solution réalisable pour initialiser l'algo de recherche locale. Sinon oui on peut aussi utiliser une recherche locale qui peut permettre d'améliorer rapidement la solution trouvée (mais en perdant la garantit de trouver une solution de cout min à la fin). Etc...
J'aurais tendance à penser le contraire
La PL est plus efficace pour attaquer de très gros problèmes modélisés avec des équations linéaires. La PPC est "généralement" intéressante pour les problèmes comportant de nombreuses contraintes "tordues" (qui seront plus difficiles à gérer avec de la PL) mais de taille plus faible en nombre de variables. Voilà pour caricaturer.
Ne te base pas que sur ce que je dis (je suis forcement un peu partial/partiel).PS : je vais être amener à faire un compte rendu sur le sujet à mon chef de projet. Histoire de "sourcer" mes informations, et sans être indiscret, quelle est ta situation ? Es-tu un professionnel, un chercheur, un étudiant, un enseignant ? En tout cas, merci pour tes précieuses lumièresJ'ai fait une thèse dans le domaine de la programmation par contraintes. Et maintenant je fais rien de bien passionnant. Si tu as besoin de plus d'éléments biographique contacte moi en pv ca sera plus adapté
Merci pour cette réponse détaillée !
C'est très clair, et ça rejoins ce que je lis ailleurs.
C'est une astuce qu'on peut faire soit-même ou c'est ce que font effectivement les solveurs ? Je suppose que ça doit être plutôt long comme processus ?Mais on peut faire de l'optimisation avec de la PPC, en posant une contrainte sur ta "fonction objectif".
A ma connaissance c'est ce que font les solveurs (et aucune autre manière de faire me vient à l'esprit). Cela peut être effectivement long. D'où l’intérêt de passer du temps à choisir une bonne heuristique pour l'exploration de ton arbre et à trouver une bonne évaluation de ta borne.
Ce qu'il faut voir aussi, c'est que les solutions trouvées à chaque étape sont des solutions réalisables (dans le sens où elles respectent toutes les contraintes de ton problème). Une approche possible si tu as un temps limité et que tu ne cherches pas absolument la meilleure solution possible, c'est de renvoyer la dernière solution trouvée (donc la meilleure du point de vue du cout) lorsque tu atteins la durée max de recherche que tu as décidé de ne pas dépasser.
Cad, concrètement ?Cela peut être effectivement long. D'où l’intérêt de passer du temps à choisir une bonne heuristique pour l'exploration de ton arbre
Parce que moi en pratique, je vois les choses comme ça :
- On créé nos variables, nos contraintes (all-différentes et compagnie), notre fonction objectif (d'ailleur on dit fonction fonction objectif ou objective?)
- On donne le tout à manger au solveur de contraintes (Choco, Ilog CP ou autre)
=> Ou intervient le "choix" de la "bonne heuristique"?
cad ?et à trouver une bonne évaluation de ta borne
C'est la fonction "objectif" pour moi il s'agit du nom commun "objectif et non pas de l'adjectif objectif/objective (math, programmation et sémantique... j'adore
Sinon pour en revenir à nos solveurs. Lors de la définition de ton problème, où lors de la configuration de l'objet qui sert à résoudre ton problème, tu as normalement la possibilité de choisir ton heuristique (cf. setHeuristic dans Choco). Cela doit être précisé dans la doc de ton solveur.
Une valeur v (aussi proche que possible de la valeur optimale de ton objectif m) pour laquelle tu sais qu'il y a une solution compris entre m et v (sans forcement savoir laquelle). Le but est de pouvoir rajouter une contrainte qui va fortement réduire ton arbre de recherche.
Comment la trouver ? Grâce à des relaxations (simplification du problème). Après tout dépend du problème... mais en général lorsque tu trouves une bonne manière d’évaluer une borne pour un problème intéressant, tu publie un article
tu as normalement la possibilité de choisir ton heuristique (cf. setHeuristic dans Choco)L'heuristique est ce qui permet au solveur de choisir les variables à fixer.1. suivant une heuristique le solveur décide de fixer la valeur d'une des variables.
C'est bien beau, mais j'ai un peu de mal à voir concrètement quelle forme prend une heuristique... C'est une formule de proba, une variable, ???
et à trouver une bonne évaluation de ta borneDonc si on cherche à minorer m, j'en déduit que v sera un majorant.Une valeur v (aussi proche que possible de la valeur optimale de ton objectif m) pour laquelle tu sais qu'il y a une solution compris entre m et v (sans forcement savoir laquelle). Le but est de pouvoir rajouter une contrainte qui va fortement réduire ton arbre de recherche.
En fait, ça revient à donner un domaine de valeurs le plus petit possible à fonction objectif, c'est ça ?
Tu as l'air de connaître Choco. A tu un opinion sur ce solveur ? Comment choisir, par exemple, entre un Choco et un ILOG CP ? Pour l'instant, les différences que je vois entre les deux sont que ILOG dispose d'un vrai langage de modélisation de contraintes (alors qu'avec CHOCO il faut passer par des interface Java). Peut être que la différence se trouve au niveau de la liste de contraintes globales supportées ?
Par exemple tu as des heuristiques qui consiste à dire au solveur de toujours fixer l'une des variables dont le domaine à le moins d’éléments à un moment donnée. Tout ce qu'il faut c'est dire au solveur comment choisir la variable et comment choisir la valeur. Voila pour la cas classique.
C'est ça.
Je connais effectivement Choco. Pour moi l'avantage de Choco est qu'il est open-source. Je sais que des modifications ont été faites pour faciliter la pose des problèmes et pour se rapprocher du paradigme déclaratif (cacher le fonctionnement interne) mais je ne sais pas jusqu'où ils sont allés.
N'ayant jamais utilisé ILOG CP je ne pourrais pas faire de comparaisons.
Bon, je pense que tu as répondu à toutes mes question (pour l'instant).
Maintenant je vais creuser un peu les différentes pistes, ce qui m'amènera très probablement à poser d'autre question
Je marque le sujet comme résolu, j'en ouvrirai un autre si j'ai d'autres questions !
Merci beaucoup pour ton aide !
Je rajoute ce lien :
http://hal.archives-ouvertes.fr/docs/00/29/35/64/PDF/demassey03phd.pdf
C'est une thèse qui présente une méthode Hybride PL PPC. L'introduction est intéressante car elle détaille bien les spécificités des deux méthodes, et leurs avantages respectifs.
Répondre avec citation
Partager