Discussion :

[laureat]

Bonjour à tous,

Voilà, je n'arrive pas à différencier entre un modèle de type programmation linéaire en nombres entiers et un modèle de type programmation par contrainte?Quel est l'avantage du premier par rapport au deuxième?
Et quel est parmi ces modèle celui qui permet d'avoir une bonne qualité de solution pour le problème de tournée de véhicule?

Merci d'avance de vos réponses.

[Acrim]

Je connais bien la programmation par contraintes mais un peu moins la PL. Pour ce que j'en sais :
- La PPC s'occupe principalement des variables qui ont un domaine discret et qui sont liées par des relations "logiques" (les contraintes) de haut niveau.
- La PL à variables continues s'occupe des problèmes dont les relations peuvent s'exprimer sous forme d’équations linéaires.

Selon moi l'avantage de la PPC c'est de pouvoir attaquer des problèmes de taille modéré possédant de nombreuses contraintes 'tordues'.

L'avantage de la PL c'est de pouvoir attaquer des très grand problèmes (nombre de variables, taille des domaines) des lors qu'on peut le modéliser sous forme d’équations linéaires.

Pour le problème du TSP si c'est un TSP pur avec beaucoup de point de passage plutôt PL. Si c'est un TSP avec fenêtre de temps, précédences, prise en compte du chargement des véhicules, des pauses déjeuner etc la PPC peut être très intéressante.

[laureat]

Merci Acrim pour ta réponse.

J'ai lu quelque part que dans un modèle de type de programmation par contrainte, on trouve des équations non linéaires ce qui constitue un inconvénient majeur de leur utilisation. Est-ce que c'est vrai?

Je connais bien la programmation par contraintes mais un peu moins la PL. Pour ce que j'en sais :
Pour le problème du TSP si c'est un TSP pur avec beaucoup de point de passage plutôt PL. Si c'est un TSP avec fenêtre de temps, précédences, prise en compte du chargement des véhicules, des pauses déjeuner etc la PPC peut être très intéressante.

Pourrait-tu me donner un document qui explique bien la modélisation du problème TSP avec programmation par contrainte.
Merci!

[Acrim]

Merci Acrim pour ta réponse.

J'ai lu quelque part que dans un modèle de type de programmation par contrainte, on trouve des équations non linéaires ce qui constitue un inconvénient majeur de leur utilisation. Est-ce que c'est vrai?

Oui effectivement les contraintes ne correspondent pas à des équations linéaires. Tu peux, certes, modéliser ton problème seulement avec des contraintes "mathématiques" mais c'est passer à coté de l’intérêt de la PPC. Les solveurs mettent à ta disposition des contraintes plus "évoluées" comme : allDifferent (toutes tes variables doivent avoir une affectation differente), atMostNValue, cumulative, lex, occurence etc... très utiles pour prendre en compte des aspects complexes des problèmes.

Certes ce ne sont pas sous problèmes linéaires mais tous les problèmes ne peuvent pas se réduire à un ensemble d'équations linéaires (surtout si on ne souhaite pas le relaxer etc).

Pourrait-tu me donner un document qui explique bien la modélisation du problème TSP avec programmation par contrainte.
Merci!

Par exemple, dans la partie "Model" de "Solving small VRPTWs with Constraint
Programming Based Column Generation" (tu le trouveras facilement sur le net).

[laureat]

Par exemple, dans la partie "Model" de "Solving small VRPTWs with Constraint
Programming Based Column Generation" (tu le trouveras facilement sur le net).

En francais, c'est possible?