Programmation par contraintes

Les rationnels

?- use_module(library(clpq)).
% library(clpq) compiled into clpq 0.08 sec, 977,560 bytes
true.

?- {X1>=0,X2>=0,X2=<3,X1+X2=<6}.
{X2>=0, X2=<3, _G4770= -6+X1+X2, X1+X2=<6, X1>=0}.

?- {X1>=0,X2>=0,X2=<3,X1+X2=<6},sup(X1+2*X2,Max).
Max = 9,
{X2>=0, X2=<3, _G10551= -6+X1+X2, X1+X2=<6, X1>=0}.

?- {X1>=0,X2>=0,X2=<3,X1+X2=<6},inf(X1+2*X2,Min).
Min = 0,
{X2>=0, X2=<3, _G15628= -6+X1+X2, X1+X2=<6, X1>=0}.

?-

Découpe de bois

On dispose de planches de Tamarin de 1 m de long et on a une commande de 36 planchettes de 28 cm et 24 planchettes de 45 cm. On souhaite minimiser les chutes de bois lors de la découpe.
Indications : montrer qu'il y a seulement trois configurations de découpe possibles dans une planche d'un mètre de long, raisonner dans les rationnels puis conclure dans les entiers.

Problème de transport

Il s'agit de déterminer l'approvisionnement en glaces Komik de points de vente à partir d'un ensemble d'usines en minimisant les coûts de transport. Les usines se trouvent à Saint Pierre (D1) et Saint Denis (D2). Les points de vente à approvisionner sont Le Port (A1), Saint Louis (A2) et Saint Joseph (A3). La matrice des coûts de transport est :

	A1	A2	A3
D1	5	1	1
D2	2	6	9

Les stocks et la demande sont :

stocks : 	D1=4	D2=6
demande :	A1=3	A2=5	A3=2

Indications : introduire 6 variables Xij représentant la quantité à transporter entre l'usine i et le point de vente j. Exprimer le coût du transport en fonction des Xij. Exprimer la contrainte sur les stocks : la quantité au départ d'une usine doit être inférieure au stock de cette usine. Exprimer que la demande doit être satisfaite. Résoudre dans les rationnels.

Gestion de production

La structure de production de l'entreprise TouzourPlisFré-TouzourPlisSer, lauréate du label Produit Réunion, est caractérisée par la confection de 3 produits P1, P2 et P3 tels que, pour une période de temps donnée (120 unités de travail au maximum) :

Produits                                                      P1        P2      P3
Volume maximal de la demande                                  20        10      30
Unités de travail nécessaire pour une production unitaire      2         3       2
Bénéfice unitaire                                              1         4       2

Le problème consiste à déterminer le programme de fabrication maximisant les gains de l'entreprise.
Indications : introduire 3 variables xi (le nombre d'articles Pi à fabriquer pendant la semaine), exprimer les trois contraintes et maximiser.

Ordonnancement de tâches

Il s'agit de déterminer un agenda des tâches de construction d'une maison de la société Apamoin pour minimiser le temps de construction. Il y a dix tâches à effectuer, chacune d'elle pouvant nécessiter l'achèvement d'une ou plusieurs autres tâches :

Code	Nom	        Durée	Nécessite
a	maçonnerie      7       _
b	charpente       3       a
c 	toit            1       b
d	sanitaire       8       a
e	façade          2       c,d
f	fenêtres        1       c,d
g	jardin          1       c,d
h 	plafond         3       f
j	peinture        2       h
k	finition        1       e,g,j

Indications : à chaque tâche est associée une variable, par exemple son code, dénotant le début de cette tâche. Traduire les contraintes de précédence avec les durées et minimiser la durée totale du projet (i.e., k+1).

Les domaines finis

:- use_module(library(clpfd)).

ONE + TWO + FIVE = EIGHT

Résoudre :

     ONE
 +   TWO
 +  FIVE
 -------
 = EIGHT

sachant qu'à deux lettres distinctes sont associées deux chiffres distincts et qu'aux lettres O, T, F et E sont associées des chiffres non-nuls.
Indications : s'inspirer de l'exemple SEND + MORE = MONEY défini ici. Observer la réduction du domaine des variables avant l'étiquetage. Il y a six solutions.

Le margouillat

Cinq hommes de nationalités distinctes habitent les cinq maisons d'une ruelle et pratiquent cinq activités professionelles différentes. Chaque personne a une préférence pour un animal et une boisson. Les animaux et les boissons sont tous différents. Les maisons sont peintes avec des couleurs toutes distinctes. De plus :

l'Anglais habite la maison rouge,
l'Espagnol possède un chien,
le Japonais est peintre,
l'Italien boit du thé,
le Norvégien habite la première maison à gauche,
le propriétaire de la maison verte boit du café,
la maison verte se trouve juste à droite de la maison blanche,
le sculpteur élève un serpent,
le diplomate habite la maison jaune,
on consomme beaucoup de lait dans la maison du milieu,
la maison du Norvégien se trouve juste à coté de la maison bleue,
la boisson préférée du violoniste est le jus de fruit,
un des voisins du médecin possède un renard et
un des voisins du diplomate possède un cheval.

Faire un plan détaillé de cette ruelle.
Indications : la solution est unique. Numéroter les maisons de 1 à 5. Définir la liste des nationalités, celles-ci sont toutes distinctes et prennent leurs valeurs dans 1 à 5. Idem pour les professions, les animaux, les boissons et les couleurs de maison. Traduire les contraintes puis étiqueter. NB : pour une gestion contrainte des disjonctions, considérer l'exemple suivant :

?- [X,Y] ins 0..1, (X #= Y+1) #\/ (X #= Y-1), label([X,Y]).

X = 0,
Y = 1 ;

X = 1,
Y = 0
?-

Emploi du temps

Les organisateurs du congrès Komen totoch le Chik disposent de 3 salles et de 4 demi-journées durant lesquelles se tiendront onze sessions (A,B, …,K). Les sessions

        AJ, JI, IE, CF, FG, DH, BD, KE, BIHG, AGE, BHK, ABCH, DFJ

ne peuvent se tenir simultanément car il y a au moins un participant inscrit à toutes les sessions de ces ensembles. La session E doit avoir lieu avant la session J, et les sessions D et F avant K.
Déterminer un emploi du temps.
Indications : associer à chaque session une variable (A, B, …) à valeur dans {1,2,3,4}. Traduire les contraintes en utilisant entre autres la relation au_plus/3 définie ci-dessous (à inclure dans le fichier où sont développées les solutions de ces exos) puis étiqueter. Il y a 20 solutions.

Les relations `nb_occ/3` et `au_plus/3`

la relation nb_occ(N,[X1,...,Xk],I) exprime que N variables parmi les Xi prennent la valeur I.

nb_occ(0,[],_).
nb_occ(N,[X|Xs],I) :- 
	( X #= I ) #<==> B,
	N #= M+B,
	nb_occ(M,Xs,I).

Par exemple :

?- L=[X,Y], L ins 0..1, nb_occ(0,[X,Y],1).
L = [0, 0],
X = Y, Y = 0 ;
false.

?-

la relation au_plus(N,[X1,...,Xk],I) exprime qu'au plus N variables parmi les Xi prennent la valeur I.

au_plus(N,Xs,I) :-
	N #>= M, 
	nb_occ(M,Xs,I).

Par exemple :

?- L=[X,Y], L ins 0..1, au_plus(1,L,0), label(L).
L = [0, 1],
X = 0,
Y = 1 ;
L = [1, 0],
X = 1,
Y = 0 ;
L = [1, 1],
X = Y, Y = 1 ;
false.

?-

Location d'entrepôts

Les dirigeants de la société Moinlapeur-Midiaou souhaitent prendre une décision au sujet de la location d'entrepôts pour desservir cinq usines. Trois entrepôts sont disponibles : E1 de coût 18, E2 de coût 10, E3 de coût 28. La matrice des coûts de transports est :

 
	U1	U2	U3	U4	U5
E1	5	4	infini	infini	3
E2	7	infini	2	infini	infini
E3	infini	1	5	4	8

Les coûts infinis correspondent bien sûr au passage de la route en corniche. On suppose de plus que chaque usine est desservie par un unique entrepôt. En minimisant le coût total, décider du choix des entrepôts à louer et pour chaque usine de l'entrepôt la desservant.
Indications : introduire trois variables Ei à valeur dans {0,1} telles que Ei=1 ssi on loue Ei et cinq variables Ui à valeur dans {1,2,3} telles que Ui=j ssi l'usine Ui est desservie par Ej. Exprimer les contraintes puis étiqueter en minimisant le coût. Il y a une unique solution de coût minimum 60.

Suit mazik

Soit S la suite d'entiers naturels [s₀,s₁,…,s_n]. S est dite mazik ssi pour tout i, 0≤i≤n, s_i est le nombre d'apparition du nombre i dans S, i.e., s_i = card({j| 0≤j≤n et j=i}). Par exemple, [1,2,1,0] et [2,0,2,0] sont deux solutions pour n=3, [2,1,2,0,0] est une solution pour n=4.

Justifier que pour tout 0≤i≤n, s_i≤n+1. En déduire une définition suit_mazik(N,L) résolvant le problème.
Que penser de la somme des s_i pour 0≤i≤n ? Inclure cette propriété dans le programme et comparer les temps d'exécution avec la version précédente.
Que penser de la somme i*s_i pour 0≤i≤n ? Inclure cette propriété dans le programme et comparer les temps d'exécution avec les versions précédentes
Conjecturer la forme des solutions pour tout n. Démontrer ce résulat et en déduire un programme de complexité linéaire en fonction de n.

Indications : la définition n'est pas directement exécutable et l'ajout successif de propriétés fait décroître les temps de calcul ; à ce propos, essayer apropos(time). et help(time).

Golomb

Il s'agit de trouver les valeurs entières correspondant aux graduations d'une règle telles que les différences entre deux graduations soient toutes distinctes et que la longueur de la règle soit minimale (applications : positionnement de radiotélescopes, conceptions d'antennes).
Indications : le problème peut être représenté par un ensemble de n variables gi et de n(n-1)/2 variables représentant les différences gi - gj pour i>j (d'où le n(n-1)/2). On peut poser par convention g0=0 et ajouter les contraintes g0 < g1 < ... < gn-1. Par exemple :

pour n=2, une solution est : g0=0, g1=1 et g2=3 ;
pour n=3, une solution est : g0=0, g1=2, g2=5 et g3=6.

Autre solution plus économique en nombre de variables : on utilise n-1 variables de base di=gi+1 -gi. On profite ensuite des propriétés de la distance linéaire pour définir les distances successives (par exemple g3-g1=d2+d1) qui doivent être toutes distinctes. La longueur de la règle, que l'on doit minimiser, est d1+ ... +dn-1.

Fred Mesnard