Programmation par contraintes

• [^]Re: Programmation par contraintes

  Posté par tgl () le 09/12/2005 à 02:22. (lien). Évalué à 3.

  En relisant ton message, je vois que tu cherches "un logiciel", et pas vraiment un langage. Bon, donc je suis limite off-topic, mais en fait non, pas vraiment : on n'a finalement pas besoin d'un logiciel bien paufiné quand on a un bon interpréteur Prolog sous la main... Voilà ton problème en Prolog Eclispe (le seul que j'ai sous la main). Le gros du code servirait pour n'importe quel autre problème du même type, donc c'est fait une fois pour toutes, et seul le prédicat "contraintes(M)" est spécifique à ton cas :

  % chargement du solveur
  :- lib(fd).
  
  % tableau 2D -> ligne (liste)
  ligne(M,I,L) :-
  	dim(M,[_,Y]),
  	length(L,Y),
  	(for(J,1,Y), foreach(A,L), param(M,I) do
  		A is M[I,J]).
  
  % tableau 2D -> colonne (liste)
  colonne(M,J,C) :-
  	dim(M,[X,_]),
  	length(C,X),
  	(for(I,1,X), foreach(A,C), param(M,J) do
  		A is M[I,J]).
  
  % contrainte sur la somme des éléments d'une liste
  sigma(L,S) :-
  	(foreach(X,L), fromto(0,A,B,S) do
  		B #= A + X).
  
  % liste de toutes les variables d'un tableau 2D
  variables(M,V) :-
  	dim(M,[X,_]),
  	(for(I,1,X), fromto([],V1,V2,V), param(M) do
  		ligne(M,I,L), append(V1,L,V2)).
  
  % impose un domaine sur toutes les variables
  domaine(M,D) :-
  	variables(M,V), V::D.
  
  % les contraintes particuulières
  contraintes(M) :- 
  	% le tableau est de dimension 3x5
  	dim(M,[3,5]),
  	% avec des valeurs entières dans [1,9]
  	domaine(M,[1..9]),
  	% AB vaut 3
  	AB is M[1,2], AB #= 3,
  	% BE vaut 5
  	BE is M[2,5], BE #= 5,
  	% CD ne vaut pas 2
  	CD is M[3,4], CD #\= 2,
  	% la somme de la ligne A est 19...
  	ligne(M,1,LigA),
  	sigma(LigA,19),
  	% ...et elle ne comporte pas de 5
  	(foreach(X,LigA) do X #\= 5),
  	% la somme de la colonne A est 10
  	colonne(M,1,ColA),
  	sigma(ColA,10),
  	% les valeurs d'une même ligne sont distinctes
  	(for(I,1,3), param(M) do
  		ligne(M,I,L),
  		alldifferent(L)).
  
  probleme(M) :-
  	% on impose des contraintes
  	contraintes(M),
  	% et on énumère les valeurs possibles des variables
  	variables(M,V),
  	labeling(V).
  

  Pour obtenir les solution, je demande "probleme(M)" à Prolog, et il me répond :

  ?- probleme(M).
  M = []([](1, 3, 2, 4, 9), [](1, 2, 3, 4, 5), [](8, 1, 2, 3, 4))
  Yes (0.00s cpu, solution 1, maybe more)
  M = []([](1, 3, 2, 4, 9), [](1, 2, 3, 4, 5), [](8, 1, 2, 3, 5))
  Yes (0.01s cpu, solution 2, maybe more)

  (et j'arrête là, mais il y a évidemment beaucoup d'autres solutions)

  • [^]Re: Programmation par contraintes

    Posté par Tom Debruyne (page perso, ) le 09/12/2005 à 07:52. (lien). Évalué à 2.

    Merci beaucoup pour cette réponse détaillée.
    Je verrai ce que je peux en faire, mais ça m'aide déjà beaucoup.
    
    J'aurais peut-être dû préciser que la raison pour laquelle je cherche un tel soft, c'est pour m'aider dans des prises de décisions complexes incluant un grand nombre de facteurs dans mon boulot.
    Si c'est réellement du niveau 1er lab de TD, je devrais effectivement pouvoir faire ça moi-même.
    
    Tom

    • [^]Re: Programmation par contraintes

      Posté par tgl () le 09/12/2005 à 08:31. (lien). Évalué à 2.

      c'est pour m'aider dans des prises de décisions complexes incluant un grand nombre de facteurs dans mon boulot.

      C'est vague, mais ça sonne bien comme ce qui est effectivement un domaine de prédilection de la programmation par contraintes. Un aspect dont je n'ai pas parlé, mais qui est lié, c'est que bien souvent le but réel d'un programme par contraintes n'est pas trouver toutes les solutions possibles, mais plutôt une solution optimale selon un certain critère. Par exemple, on aurait pu chercher une solution minimisant la somme de toutes les variables :

      probleme(M,S) :-
      	% on impose des contraintes
      	contraintes(M),
      	% et on cherche une solution minimisant la somme des variables
      	variables(M,V),
      	sigma(V,S),
      	min_max(labeling(V),S).
      

      Qui nous donne :

      ?- probleme(M, S).
      M = []([](1, 3, 2, 4, 9), [](4, 1, 2, 3, 5), [](5, 1, 2, 3, 4))
      S = 49
      Yes (0.71s cpu)
      

      C'est le genre de truc qui est utilisable dans plein de domaines, que ce soit de l'ingénierie, de la finance, de la logistique, etc., souvent avec en tête de minimiser un coût, une durée, etc. Et les problèmes de la vraie vie mettent facilement en jeu des milliers de variables et dix ou cent fois plus de contraintes encore, sans que ce soit forcement une difficulté si le problème s'y prête bien.

      Si c'est réellement du niveau 1er lab de TD, je devrais effectivement pouvoir faire ça moi-même.

      J'en ai peut-être rajouté un tout petit peu : disons que ça peut être un premier TP contraintes pour des gens qui aurait déjà des notions de Prolog. Je dis ça parce que là il n'y a pas d'écueuil, juste des contraintes simples sur des variables ("machin ne vaut pas truc") ou listes de variables ("tous les éléments de cette listes sont différents"). Le plus compliqué dans mon programme vite fait, c'est finalement la manipulation du tableau (récupérer une colonne, etc.), mais ça c'est du Prolog tout court, ça n'est pas spécifique à la programmation par contraintes.

      • [^]Re: Programmation par contraintes

        Posté par Tom Debruyne (page perso, ) le 09/12/2005 à 10:27. (lien). Évalué à 2.

        > C'est vague
        
        Un exemple concret, comment distribuer le travail entre 9 ingénieurs sur une semaine.
        9 ingénieurs
        10 demi journées
        5 domaines à couvrir
        
        contraintes "hard"
        chaque ingénieur peut couvrir 3 domaines définis (selon ses compétences)
        chaque domaine doit être couvert par un ingénieur chaque demi-journée (ça s'appelle un shift)
        les ingénieurs auront chacun un nombre équivallent de shifts (plus ou moins 1). 6 par semaine environ
        un ingénieur peut être absent (1 ou plusieurs jours) et donc ne pas prendre de shifts ces jours-là
        
        contraintes "soft"
        certains ingénieurs préfèrent les shifts du matin, d'autres, l'après-midi
        certains ingénieurs préfèrent regrouper les shifts (couvrir plusieurs domaines sur une matinée), d'autres préfèrent les disperser
        au moins deux jours sans shift par ingénieur
        pas plus de la moitié des shifts d'une semaine pour un ingénieur ne devraient couvrir le même domaine
        
        Toutes les contraintes ne seront pas facile à formuler, mais d'après ce que tu me dis, Prolog serait la voie à explorer
        
        Encore merci,
        Tom

        • [^]Re: Programmation par contraintes

          Posté par norbs () le 09/12/2005 à 22:06. (lien). Évalué à 1.

          Si tu ne veux ou peux pas utiliser prolog, l'excellente bibliothèque lp_solve (lpsolve.sourceforge.net) est très facilement interfaçable avec la plupart des langages.