CLP - Beispiele und Anwendungen

Logikprogrammierung  Constraint lösen

CLP

Mathematik  Operations Research

• Logikprogrammierung: deklarativ, relationale Form, nicht determiniert (Suche), Unifikation. Probleme: “generate and test” ineffizient für komplexe Probleme Datenstrukturen: Anwendungsbereich versus Terme Inferenz: Unification und Resolution versus Spezialmethoden

• Constraint lösen: KI, Konsistenztechniken + Heuristic

• Operations Research: spezialisiert vs. allgemein, statisches Problem vs. inkrementelle dynamische Probleme

• Mathematik: wie OR

Constraints

• vollständige Verfahren

– (Pseudo-)Bool: Unifikation, OR-Techniken

– Rational: Simplex, Innere Punkte Methode, Intervalltechniken

– …

• unvollständige Verfahren

– endliche Bereiche (FD): Konsistenztechniken

– Bool:

– Listen:

– …

Boolesche Constraints

Logische Schaltkreise

Halbaddierer:

half adder(X,Y,X ⊕ Y,X ∧ Y).

Addierer:

full adder(X,Y,Cin,S,C1 ∨ C2) :- half adder(X,Y,S1,C1), half adder(S1,Cin,S,C2).

Anfrage und Lösung:

?-full adder(X,Y,Cin,S,Cout).

S = X ⊕ Y ⊕ Cin, Cout = X ∧ Y ⊕ X ∧ Cin ⊕ Y ∧ Cin yes.

?-full adder(X,Y,Cin,1,0). X = A Y = A ∧ B ⊕ B Cin = A ∧ B ⊕ A ⊕ B ⊕ 1 yes.

• Aufbau und Test komplexer Schaltungen

• Verifikation durch Vergleich mit Spezifikation

• Fehlersuche

Pseudo-Boolesche Constraints

0-1 Optimierungsproblem: Zielfunktion und 0-1 Nebenbedingung

Beispiel: Radiobau

• 3 Röhrentypen (T_{1}, T_{2}, T_{3}); genau ein Typ

• Gehäuse entweder aus Holz (H) oder Plastik (P). Falls Plastik Platzmangel: Röhre T_{2} und nicht Transformator (F) sondern Netzteil (S).

• T_{1} arbeitet nur mit F.

• T_{2} und T_{3} arbeiten nur mit S.

Die Preise der Komponenten sind;

T_{1} 28 GE T_{2} 30 GE T_{3} 31 GE
F 25 GE S 23 GE
H 9 GE P 6 GE

Die anderen notwendigen Komponenten des Radios kosten

T_{1} dann 27 GE T_{2} dann 28 GE T_{3} dann 25 GE

Zusammenbau: 10 GE Preis: P dann 110. H dann 105. Problemstellung :

Welches Modell soll gebaut werden, um den Profit zu maximieren ?

assemble(T1, T2, T3, F, S, H, P) :-
                 T1 + T2 + T3 = 1,
                 H + P = 1,
                 F + S = 1,
                 P ≤ T2 * S,      % P = 1 impliziert T2 = S = 1
                 T1 ≤ F,          % T1 = 1 impliziert F = 1
                 T2 ≤ S,          % T2 = 1 impliziert S = 1
                 T3 ≤ S.          % T3 = 1 impliziert S = 1

maximal-profit(T1, T2, T3, F, S, H, M) :-
        max( 110H + 105M - ( 28T1 + 30T2 + 31T3 + 25F + 23S
                            + 9H + 6P + 27T1 + 28T2 + 25T3 + 10),
        assemble(T1, T2, T3, F, S, H, M) ).

     ?- maximal profit(T1, T2, T3, F, S, H, P).
     T1 = 0, T2 = 0, T3 = 1, F = 0, S = 1, H = 1, P = 0.

Anfrage ergibt eindeutige Lösung Der Gewinn beträgt 12 Geldeinheiten.

     ?- assemble(T1, 1, T3, F, S, H, P).
     T1 = 0, T3 = 1, F = 0, S = 1, H + P = 1.

sequence: 0-1 Listen die keine 3 aufeinanderfolgende Nullen enthalten.

   sequence([]).
   sequence([ ]).
   sequence([ , ]).
   sequence([X_{i}, X_{j}, X_{k}|L]) :-

X_{i} + X_{j} + X_{k} ≥ 1,

          sequence([X_{j}, X_{k}|L]).

Queries:

?- sequence([0, 0, 1, 0, 1, 1, 0]).

⇝ yes

?- sequence([0, 1, 0, 0, 0, 1, 0]).

⇝ no

?- sequence([A, B, \overline{A}, \overline{B}, A]).

⇝ yes

?- sequence([A, A, B, B, C, C]).

⇝ B + C ≥ 1, A + B ≥ 1

?- sequence([A · B, \overline{A} · B, C · A, A+B, D+\overline{A}]).

⇝ B + C ≥ 1, A + B ≥ 1

• Constraints werden benützt beim Programmieren und zur Lösungsbeschreibung. d.h. Untersuchen des Problems und Lösungsraums möglich.

• Während der Programmausführung werden Constraints dynamisch generiert und behandelt.

• vollständiger Löser: Regelanwendung nur zulässig wenn Constraintmenge konistent. d.h. Constraints kontrollieren Programmablauf.

Lineare Arithmetik

Beispiel: Fibonacci-Zahlen

fib(0, 1).
fib(1, 1).
fib(N, X1 + X2) :-
        N > 1,
        fib(N - 1, X1),
        fib(N - 2, X2).
2 ?-  fib(14,X).
X = 610
3 ?- fib(X,610).
X = 14

Beispiel: Darlehen

mortgage(D, Laufzeit, Zinssatz, Bal, MZ) :- Laufzeit = 1, Bal = D · (1 + Laufzeit · \frac{Zinssatz}{1200}) - MZ.

mortgage(D, Laufzeit, Zinssatz, Bal, MZ) :- Laufzeit > 1, mortgage(D · (1 + \frac{Zinssatz}{1200}) - MZ, Laufzeit-1, Zinssatz, Bal, MZ).

Darlehen: D, Laufzeit in Monaten: Laufzeit, Jahreszinssatz in %: Zinssatz (monatlich abgerechnet), Monatliche Zahlung: MZ, RestSchuld: Bal.

Finanziere ein Darlehen von 100000 zu 12 Prozent für 15 Jahre.

?-mortgage(100000, 180, 12, 0, MZ).

MZ = 1200.17 yes.

Zusammenhang Darlehen und monatliche Zahlung bei Dauer 180 Monate und 12 % Zinssatz.

?-mortgage(D, 180, 12, Bal, MZ).

D = 0.166783 * Bal + 83.3217 * MZ yes.

Bidirektional und Constraints als Ausgabe kombinatorische Probleme

Beispiel: SEND + MORE = MONEY

solve([S, E, N, D, M, O, R, Y]) :-
constraints([S, E, N, D, M, O, R, Y]),
gen_diff_digits([S, E, N, D, M, O, R, Y]).
constraints([S, E, N, D, M, O, R, Y]) :-
S >= 0, E >= 0, N >= 0, D >= 0, M >= 0, O >= 0, R >= 0, Y >= 0,
S <= 9, E <= 9, N <= 9, D <= 9, M <= 9, O <= 9, R <= 9, Y <= 9,
S >= 1, M >= 1,
C1 >= 0, C2 >= 0, C3 >= 0, C4 >= 0,
C1 <= 1, C2 <= 1, C3 <= 1, C4 <= 1,
M = C1,
C2 + S + M = O + C1 * 10,
C3 + E + O = N + 10 * C2,
C4 + N + R = E + 10 * C3,
D + E = Y + 10*C4,
bit(C1), bit(C2), bit(C3), bit(C4).
bit(0).
bit(1).
gen_diff_digits(L) :-
gen_diff_digits(L, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]).
gen_diff_digits([], _).
gen_diff_digits([H | T], L) :-
select(H, L, L2), gen_diff_digits(T, L2).
select(H, [H | T], T).
select(H, [H2 | T], [H2 | T2]) :-
select(H, T, T2).

Reelle Lösung als Approximation für ganzzahlige Lösung.

Constraints über endliche Bereiche

sendmory([S,E,N,D,M,O,R,Y]) :- generate constraints([S,E,N,D,M,O,R,Y],[C1,C2,C3,C4 ]), enumerate([C1,C2,C3,C4,S,E,N,D,M,O,R,Y]).

generate constraints([S,E,N,D,M,O,R,Y],[C1,C2,C3,C4]) :- [S,E,N,D,M,O,R,Y] :: [0 .. 9], [C1,C2,C3,C4] :: [0 .. 1], alldiff([S,E,N,D,M,O,R,Y], S ≠ 0, M ≠ 0,

C1 = M ,
C2 + S + M = O + 10·C1,
C3 + E + O = N + 10·C2,
C4 + N + R = E + 10·C3,
D + E = Y + 10·C4.

     enumerate([V|Vs]) :-
             indomain(V),
             enumerate(Vs).

?- sendmory([S,E,N,D,M,O,R,Y]).

S = 9, E = 5, N = 6, D = 7, M = 1, O = 0, R = 8, Y = 2 .

Lokale Konsistenz: Eliminieren unmöglicher Werte aus der Domain der Variablen. Bsp: SMM Da M ≠ 0, C1 = M, und C1 entweder 0 oder 1 ist, ist M = C1 = 1. Der Wert 1 wird aus der Domain aller Variablen {S,E,N,D,O,R,Y} eliminiert wegen dem alldiff-Constraint. Da M = C1 = 1 reduziert

C2 + S + M = O + 10·C1

zu

C2 + S = O + 9 .

Da O + 9 ≥ 9 muss S ≥ 8 sein, da C2 ≤ 1. Die Domain von S ist reduziert auf {8,9}. Die Domain von O ist reduziert zu {0}, da C2 + S ≤ 10. O muss kleiner als 2 sein aber 1 fehlt schon. Endzustand:

S=9, M=1, O=0, C1=1, C2=0, and E,N,D,R,Y ∈ {2,…,8}

Beim Aufzählen wählen wir einen möglichen Wert einer Variablen mit Wertebereich mehr als einem Element und Fixieren diese Variable auf den gewählten Wert. Mit dieser Information werden die Domains der anderen Variablen weiter reduziert bis entweder einer Lösung gefunden wird oder Inkonsistenz erkannt wird (Backtracking).

     alldiff([]).
     alldiff([X|Y]) :-

outof(X,Y),

             alldiff(Y).
     outof(X,[]).
     outof(X,[F|T]) :-

X ≠ F, outof(X,T).

Quadratische Anzahl an Constraints!!! Algorithmische Behandlung: Sobald eine Variable einen Wert hat entferne diesen Wert aus der Domain der anderen (dieselbe Pruningeigenschaft, keine quadratische Anzahl an Constraints). Bessere Pruningmöglichkeit durch bessere Algorithmen...

Globale Constraints

für Probleme die in der Praxis häufig auftreten.

• cumulative Resourcen-Constraints in Schedulingproblemen

• among Generalisierung von atleast und atmost Constraints. In einer Liste von Constraints müssen mindestens (dürfen höchstens) n Constraints wahr sein.

• diffn Generalisierung von alldiff

   • cycle . . .

Vorteile

• Algorithmen (OR) für spezielle Probleme. Effizienz erhöht, trotzdem deklarativ.

• Durch Integration in Sprache Kombination möglich. Komplexe Probleme mit diversen Teilproblemen können effizient behandelt werden.

Propagierungsbasierter Ansatz bedingt Wissen über Problembereich und über Lösungsverfahren zur Modellierung. Anwendungsbereiche: car sequencing, Scheduling, Verschnittprobleme, Testpatterngenerierung, Färben von Graphen, microcode label assignment, Finanzentscheidungen, Planung, …

Problemlösen mit Konsistenztechniken in CLP

Generelles Schema

     problem(<Variablen>) :-
             <Constraintgenerierung>, % test
             <Aufzählen>. % generate

Constraintgenerierung

  disjunct(Si,Di,Sj,Dj) :- Sj >= Si + Di.
  disjunct(Si,Di,Sj,Dj) :- Si >= Sj + Dj.

fruehe Wahl (sehr wahrscheinlich falsch), nicht deterministisch

  disjunct(Si,Di,Sj,Dj) :- among(1,[Sj >= Si + Di,Si >= Sj + Dj],1)

Redundante Constraints: Einbringen von zusätzlicher Information die mehr Pruning bewirkt.

Aufzählen

labeling([]).
labeling([X|Y]) :-
        indomain(X),        % deleteff(Var,[X|Y],Rest),
                           % indomain(Var)
        labeling(Y).        % labeling(Rest).

• Basisaufzähler

• mit generellen Heuristiken

• mit speziellen Heuristiken

Optimieren

Nur durch “branch and bound”. 1.) Berechne Lösung (Aufzählen) 2.) Verbiete Lösungen mit schlechteren oder gleichen Zielfunktionswerten.

solange bis Problem inkonsistent. Letzte Lösung war Optimallösung.

2-dimensionales Verschnittproblem

Schneidemaschine: Holzplatte in Bretter N verschiedene Arten von Brettern: M Konfigurationen: bestimmt Anzahl und Art von Brettern aus Platte.

S_{i_{j}}, 1 ≤ i ≤ M, 1 ≤ j ≤ N: Anzahl der Bretter j aus Konfiguration i. R_{j}, 1 ≤ j ≤ N: benötigte Anzahl von Brettern j. W_{i}, 1 ≤ i ≤ M: Abfall in Konfiguration i. Problem: Schneide benötigte Bretter, minimiere Abfall. Bsp: 6 Arten von Brettern, 72 Konfigurationen, 4 Platten. Bemerkung: Konfugrationen mussten auch berechnet werden. Andere Aspekte eines Problems mit logischer Programmiersprache lösen.

Lösung 1 : X_{i} : 1 ≤ i ≤ M = 72 : Anzahl der Platten geschnitten nach Konfiguration i.

4 Platten:

X_{1} + ⋯ + X_{72} = 4

Alle Bretter:

X1 ∗ S_{1_{j}} + ⋯ + X_{72} ∗ S_{72_{j}} ≥ R_{j} 1 ≤ j ≤ N = 6

Abfall:

min(X_{1} ∗ W_{1} + ⋯ + X_{72} ∗ W_{72})

  solve([X1,...,X72],Abfall) :-
    X1 + ... + X72 = 4,
    X1*S1,1 + ... + X72*S72,1 >= R1,
    ...
    X1*S1,6 + ... + X72*S72,6 >= R6,
    Abfall = X1*W1 + .... + X72*W72,
    labeling([X1,...,X72]).

Lösung 2 : X_{i} : 1 ≤ i ≤ 4 : Konfiguration von Platte i.

1 ≤ X_{i} ≤ 72

T_{i_{j}} : 1 ≤ i ≤ 4, 1 ≤ j ≤ 6: Anzahl von Brettern j aus Platte i A_{i} : 1 ≤ i ≤ 4: Abfall aus Platte i.

element-Constraint: element(X,List,E)

Das X-te elemnt von List ist E.

Berechne T_{i_{j}}:

element(X_{i}, [S_{1_{j}}, …, S_{72_{j}}], T_{i,j}) 1 ≤ i ≤ 4, 1 ≤ j ≤ 6

Berechne A_{i}:

element(X_{i}, [W_{1}, …, W_{7}2], A_{i}) 1 ≤ i ≤ 4
Abfall = A_{1} + A_{2} + A_{3} + A_{4}.

Alle Platten:

T_{1_{j}} + T_{2_{j}} + T_{3_{j}} + T_{4_{j}} ≥ R_{j} 1 ≤ j ≤ 6

Keine symmetrischen Lösungen (Trick!):

X_{1} ≤ X_{2}, X_{2} ≤ X_{3}, X_{3} ≤ X_{4}

  solve([X1,...,X4],Abfall) :-
    ....
    labeling([X1,...,X4]).

Suchraum von ca. 10^{43} auf 10^{7} keine symmetrischen Lösungen

6 min Lösung 1 versus 1.5 min Lösung 2 versus 3 sek Lösung 2 + Domainsplitting