Discussion :

[Invité]

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 !

[Acrim]

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.

[Invité]

Merci pour ta réponse ! Sa m'aide, mais c'est encore un peu flou :

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.

Est ce qu'on peut dire que la programmation linéaire est un cas particulier de la PPC ou les contraintes sont linéaires ?

Ç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.

Ok, ca je comprend. Avec une approche par contrainte on résous avec les arbres de recherches.
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.

[Acrim]

Est ce qu'on peut dire que la programmation linéaire est un cas particulier de la PPC ou les contraintes sont linéaires ?

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.

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.

Ok, ca je comprend. Avec une approche par contrainte on résous avec les arbres de recherches.
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.

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 :

1. suivant une heuristique le solveur décide de fixer la valeur d'une des variables.
2. 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).

[Invité]

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

[Acrim]

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.

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).

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

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.

1/ La PL permet de trouver l'optimum alors que la PPC permet juste de trouver une 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).

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...)

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

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 ?

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.

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

Ne te base pas que sur ce que je dis (je suis forcement un peu partial/partiel). J'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é