LAB: Wprowadzenie do środowiska ECLiPSe

ECLiPSe jest jednym ze środowisk do programowania z ograniczeniami. Zapewnia ono szerokie możliwości tworzenia własnych ograniczeń oraz doboru właściwego sposobu poszukiwania rozwiązania. Składnia języka ECLiPSe jest oparta o Prolog. Istotne różnice opisane są w następującym przewodniku: http://eclipseclp.org/doc/tutorial/tutorial023.html.

1. Przed laboratorium

Zapoznać się z ideą algorytmów branch and bound.

2. Podstawy środowiska

Proszę utworzyć plik o poniższej zawartości (tradycyjnie pliki z kodem ECLiPSe mają rozszerzenie .ecl):

:- lib(ic).
 
sendmore(Digits) :-
        % zmienne 
        Digits = [S,E,N,D,M,O,R,Y],
 
        % przypisanie dziedziny
        Digits :: [0..9],
 
        % Ograniczenia
        alldifferent(Digits),
        S #\= 0,
        M #\= 0,
                     1000*S + 100*E + 10*N + D
                   + 1000*M + 100*O + 10*R + E
        #= 10000*M + 1000*O + 100*N + 10*E + Y,
 
        % szukanie rozwiązania
        labeling(Digits).

Opis programu

Jest to program rozwiązujący zagadkę SEND+MORE=MONEY.

Przed uruchomieniem przeanalizuj działanie programu. Pierwsza linijka informuje, że będziemy korzystać ze standardowej biblioteki dla dziedzin skończonych. Predykat sendmore Najpierw unifikuje Digits z listą zmiennych wykorzystywanych do opisu problemu. Następnie zmiennym przypisywana jest dziedzina (liczby całkowite od 0 do 9).

Kolejnym etapem jest określenie ograniczeń. Predykat alldifferent zapewnia, że wszystkie zmienne będą różne. Następnie wykorzystywane są operatory #\= oraz #= określające odpowiednio relację różności i równości. Istnieją również analogiczne operatory większości i mniejszości, należy jednak pamiętać o znaku # na początku operatora.

Ostatnia linijka powoduje rozpoczęcie wyszukiwania rozwiązania.

Uruchamianie programu

Wpisz w powłoce:

export PATH=$PATH:/usr/local/eclipse-clp/bin/

Następnie uruchom ECLiPSe poleceniem tkeclipse.

Wybierz File>Compile i wskaż utworzony plik.

Wywołaj w Query entry predykat sendmore:

sendmore(Digits)

Zwróć uwagę, aby na liście rozwijanej z lewej strony wybrany był moduł eclipse.

Aby sprawdzić, czy nie istnieje więcej rozwiązań, wciśnij przycisk more.

Alternatywna wersja

Problem SEND + MORE = MONEY można też opisać w alternatywny sposób wprowadzając przeniesienia. Dodaj je do modelu

        Carries = [C1,C2,C3,C4],
        Carries :: [0..1],

i przepisz ograniczenia tak, aby je wykorzystywały. Sprawdź poprawność porównując z poprzednią wersją.

Kolorowanie mapy

Na podstawie ostatniego programu napisz predykat rozwiązujący problem kolorowania mapy Australii. Dwa sąsiednie stany muszą mieć różne kolory. Czy trzy kolory wystarczą do pokolorowania mapy?

Przydział zasobów

Ważną klasą problemów rozwiązywaną przez programowanie z ograniczeniami jest przydział zasobów. Przykładowy problem można znaleźć na tej stronie. Poniżej znajduje się zaczerpnięty z niej kod:

:- lib(ic).
:- lib(ic_cumulative).
:- lib(branch_and_bound).
:- lib(lists).
 
schedule(Ss, End,Capacity) :-
        length(Ss, 7),
        Ds = [16, 6,13, 7, 5,18, 4],
        Ss :: 1..30,
 
        Rs = [ 2, 9, 3, 7,10, 1,11],
        End :: 1..50,
 
        after(Ss, Ds, End),
        cumulative(Ss, Ds, Rs, Capacity),
        append(Ss, [End], Vars),
 
        minimize(labeling(Vars),End).
 
after([], [], _).
after([S|Ss], [D|Ds], E) :- E #>= S+D, after(Ss, Ds, E).

Dany jest zbiór zadań do wykonania (ich czasów oraz potrzebnych zasobów) oraz ograniczona liczba zasobów. zasoby są niewyczerpywalne – jest to np. liczba sal w budynku albo maszyn w fabryce. Zadaniem jest tak ustalić początki wykonania, żeby zadanie skończyło się możliwie jak najszybciej.

Sprawdź wynik działania programu dla ograniczenia wynoszącego 13. Dodaj nowy zasób (procesy potrzebują go odpowiednio 1, 2, 3, 4, 5, 6, 7) z ograniczeniem 8. Jakie jest wyjście programu?

Co należałoby zmienić w programie, jeśli maszyny wymagałyby przerwy technologicznej o zadanej długości pomiędzy zadaniami? Nanieś odpowiednie zmiany i sprawdź wyniki.

W tym momencie wszystkie predykaty użyte w programie (prawdopodobnie z wyjątkiem minimize) powinny być zrozumiałe. Predykat minimize pochodzi z biblioteki branch_and_bound i minimalizuje cel zadany pierwszym argumentem ze względu na zmienną podaną jako drugi argument. Używaną techniką jest metoda branch and bound – po każdym znalezieniu rozwiązania do ograniczeń jest dodawane nowe ograniczenie na minimalizowaną zmienną. Szczegóły opisane są na tej stronie.

3. Problem n hetmanów

Trochę bardziej zaawansowane możliwości systemu ECLiPSe prezentuje program rozwiązujący problem n hetmanów.

:- lib(ic).
 
queens(N, Board) :-
	length(Board, N),
	Board :: 1..N,
	( fromto(Board, [Q1|Cols], Cols, []) do
	    ( foreach(Q2, Cols), count(Dist,1,_), param(Q1) do
		noattack(Q1, Q2, Dist)
	    )
	).
 
noattack(Q1,Q2,Dist) :-
	Q2 #\= Q1,
	Q2 - Q1 #\= Dist,
	Q1 - Q2 #\= Dist.

Opis programu

Po pierwsze, model zawiera pętle (fromto, foreach, count, param). Umożliwiają one bardziej zwarty zapis ograniczeń. Po drugie, brakuje użycia predykatu labeling, przez co nie zostanie znalezione żadne rozwiązanie.

Ćwiczenie

Proszę zapisać do pliku i wykonać powyższy kod. Co pojawia się w oknie wyników?

Okazuje się, że propagacja ograniczeń przy określaniu modelu nie jest wystarczająca i potrzebne jest przeszukiwanie. Najprostsze przeszukiwanie realizowane jest przez predykat labeling. Przeszukuje ono zmienne od początku listy do końca i próbuje przypisać kolejne liczby począwszy od najmniejszej. Spróbuj zastosować to przeszukiwanie (było używane we wcześniejszych przykładach). Ile czasu potrzeba, aby wyszukać rozwiązanie dla planszy 24×24?

Jedną z heurystyk, jakie można zastosować jest wybór najbardziej ograniczonej zmiennej (mającej najmniej liczną dziedzinę). Opis kluczowego predykatu delete znajduje się tutaj.

:- lib(ic_search).
labeling_b(AllVars) :-
        ( fromto(AllVars, Vars, VarsRem, []) do
            delete(Var, Vars, VarsRem, 0, first_fail), % wybór zmiennej
            indomain(Var)                              % wybór wartości
        ).

Porówanaj czasy działania dla różnych wielkości planszy. Czy druga metoda przeszukiwania jest zawsze lepsza od pierwszej?

Trzecia metoda to wybór środkowych zmiennych w pierwszej kolejności. Hetman na środku planszy atakuje więcej pól, przez co szybciej możliwe będzie wykrycie niepoprawnego rozstawienia. Skompiluj poniższy kod:

:- lib(lists).
 
middle_first(List, Ordered) :-
        halve(List, Front, Back),
        reverse(Front, RevFront),
        splice(Back, RevFront, Ordered).
 
labeling_c(AllVars) :-
        middle_first(AllVars, AllVarsPreOrdered), % static var-select
        ( foreach(Var, AllVarsPreOrdered) do
            indomain(Var)                         % select value
        ).

Przeanalizuj działanie predykatu middle_first. Jak zachowywałby się predykat labeling_c, gdyby pętla przebiegała po AllVars?

Zanim przetestujemy szybkość działania z nowym wyborem zmiennych, zmodyfikujmy predykat queens tak, aby mógł obsługiwać dowolną metodę wyszukiwania. Dodaj w tym celu dodatkową zmienną Labeling oraz zmodyfikuj wywołanie szukania tak, aby korzystało z nazwy predykatu podanej w tej zmiennej. Podpowiedź: użyj predykatu apply/2.

Sprawdź, po zmianach kod dalej działa, wywołując zmodyfikowany predykat. Następnie użyj predykatu benchmark do sprawdzenia szybkości działania:

:- lib(util).
 
benchmark :-
        ( for(I, 4, 26, 2) do
            write(I),
            util:time(queens(I, _, labeling)),
            util:time(queens(I, _, labeling_b))
            util:time(queens(I, _, labeling_c))
        ).

Czwarta metoda polega na połączeniu metod drugiej i trzeciej – wybierane są zmienne najbardziej ograniczone, lecz jeśli dwie zmienne mają tak samo liczną dziedzinę, pierwsza wybierana jest ta leżąca bliżej środka. Zmodyfikuj predykat labeling_b tak, aby wykorzystywał kolejność zmiennych z labeling_c. Która zmienna (predykatu) odpowiada za kolejność i dlaczego AllVars? Sprawdź czasy działania tej metody.

Ostatnia z proponowanych metod to niewielka modyfikacja poprzedniej. Oprócz preferowania środkowych zmiennych, rozpatruje się też środkowe wartości w pierwszej kolejności. Wymaga to tylko modyfikacji użycia predykatu indomain poprzez zastąpienie go wersją dwuargumentową: indomain(Vars, middle).

Limity dla metod (największa, do której szybko liczą się wszystkie o rozmiarze parzystym/największa, dla której szybko się liczy):

  • naiwna: 26 / 26
  • najbardziej ograniczona zmienna: 86 / 170
  • najpierw środkowe: 28 / 28
  • najbardziej ograniczona, możliwie najbliższa środkowi zmienna: 82 / 290
  • jw, z wyborem środkowych wartości zmiennej 92 / 300

Druga liczba w powyższych ograniczeniach jest tylko dolnym limitem na opisaną wielkość.

Celem tych rozważań jest pokazanie, że właściwy dobór metody przeszukiwania może mieć ogromny wpływ na szybkość uzyskania wyniku. Platforma ECLiPSe zostawia szerokie pole do optymalizacji wysokopoziomowych zostawiając jednocześnie możliwość szybkiego, deklaratywnego napisania prototypu dla niewielkich problemów.

Zadania fakultatywne

  1. Wypróbuj swoje własne heurystyki dla problemu n hetmanów. Porównaj ich szybkość działania z tymi zaproponowanymi w ćwiczeniu.
  2. Spróbuj znaleźć możliwie duże plansze, na których szybko działają heurystyki z ćwiczenia. Możesz do tego celu wykorzystać (odpowiednio zmodyfikowany) poniższy predykat:
fll :- writeln('NOT OK'), !.
 
time_is_acceptable :-
        ( for(I, 4, 120, 2) do
            writeln(I),
            timeout:timeout(
                     (!, queens(I, _, labeling), writeln('OK')),
                     2,
                     fll)
        ).

4. Fabryka słodyczy, część 1.

Na wieść o dużych możliwościach programowania z ograniczeniami zgłosił się właściciel fabryki słodyczy. Chce, aby pomóc mu zoptymalizować produkcję poznawanymi na laboratoriach metodami. Pierwszy problem jest dość łatwy i rozwiązywalny na inne sposoby, jednak na kolejnych laboratoriach będzie rozbudowywany o kolejne elementy i już nie będzie można przeliczyć go ręcznie.

Otóż na nowy dział produkcji czekolad zamierza przeznaczyć 500.0 złotych (oczywiście nie polskich). Ceną sprzedaży będzie 5.0 złotych za litr. Do wyboru ma trzy procesy produkcyjne, w których koszt wyprodukowania litra czekolady wynosi odpowiednio 1.0, 2.0 i 1.5 złotego. Który proces powinien wybrać i ile wtedy zarobi?

Przełożenie problemu na język programowania z ograniczeniami wymaga zastosowania ograniczeń zmiennoprzecinkowych oraz napisania własnego ograniczenia (więcej o pisaniu własnych ograniczeń w kolejnym ćwiczeniu).

:- lib(ic).
:- lib(branch_and_bound).
:- lib(listut).
 
delay constr_nth(Domain, Which, Value) if (var(Which); var(Domain)).
constr_nth(Domain, Which, Value) :- nth1(Which, Domain, Value).
 
% który z CostPerLiter daje największy zysk?
problem(CPLS, PricePerLiter, Money, Income, Which) :-
        length(CPLS, N),
        Which :: 1 .. N,
        nth_value(CPLS, Which, CPL),
        Liters $= Money / CPL,
        Income $= Liters * PricePerLiter - Money,
        Loss $= -1.0 * Income,
        minimize(labeling([Which]), Loss).

Opiszmy nowe elementy po kolei:

  1. constr_nth jest predykatem nth1 zamienionym w ograniczenie. Jak dokładnie działa i co oznacza linijka powyżej będzie wyjaśnione na kolejnym laboratorium.
  2. Predykaty zaczynające się dolarem definiują ograniczenia zmiennoprzecinkowe. Używana jest przy tym arytmetyka przedziałów – zmienne reprezentowane są jako zakres wartości, które mogą przyjmować. Zakresy te są odpowiednio dostosowywane w zależności od stosowanych funkcji czy działań arytmetycznych.
  3. Predykat minimize działa tak jak wcześniej, przy czym tym razem optymalizuje zmienną zmiennoprzecinkową.

Uruchom program w ECLiPSe i sprawdź działanie. Czy wyniki się zgadzają z oczekiwaniami?

LAB: Ograniczenia i ich implementowanie w środowisku ECLiPSe

Właściwe określenie i implementacja ograniczeń jest drugim, obok metody przeszukiwania, kluczowym elementem rozwiązywania problemów w programowaniu z ograniczeniami. Najprostszą ich realizacją jest napisanie odpowiednich predykatów je określających, co było robione w laboratorium wprowadzającym. Czasami jednak istnieje wiele metod określania ograniczeń, bądź osiągnięcie dobrej szybkości rozwiązywania problemu wymaga podania pewnych metainformacji o ograniczeniu.

5. Przed laboratorium

Zapoznać się z metodami propagacji ograniczeń http://eclipseclp.org/doc/tutorial/tutorial100.html. Przeczytać czym są problemy programowania liniowego http://en.wikipedia.org/wiki/Linear_programming.

6. Jak działają ograniczenia

Deklaratywnie normalny predykat (na przykład ) ma takie samo znaczenie jak jego wersja będąca ograniczeniem. Podstawową różnicą jest to, że normalny predykat jest wykonywany od razu, zaś wykonanie ograniczenia jest opóźniane. To, jak bardzo sprawdzanie ograniczeń jest opóźniane, zależy od programisty. W przypadku sprawdzania spójności sprawdzenie odwleka się, dopóki wszystkie zmienne ograniczenia nie będą termami bazowymi.

Otwórz środowisko tkeclipse i wpisz w polu Query entry poniższe zapytania. Używane ograniczenia pochodzą z biblioteki suspend, stąd nazwa modułu i dwukropek przed użyciem predykatu (nie było potrzeby stosowania tej notacji wcześniej, gdyż wykorzystywaliśmy konstrukcję :- lib(nazwa_biblioteki).).

?- X > 0
?- X > 0, X is 2
?- X is 2, X > 0
?- suspend : (X > 0)
?- suspend : (X > 0), X is 42
?- suspend : (X > 0), X is -42

Nie jest to jedyne, i nie zawsze najlepsze, zachowanie. Weźmy na przykład predykat #\= ze znanego nam modułu ic. Jak pamiętamy, w tym module mogliśmy określać dziedziny zmiennych. Zatem jeśli jedna ze zmiennych w predykacie ma już określoną wartość, możemy ją wyrzucić z dziedziny drugiej zmiennej. Zachowanie takie nazywa się sprawdzaniem wprzód. Wpisz w tkeclipse:

?- ic : (X :: 1 .. 5), ic : (X #\= 2)
?- ic : (X :: 1 .. 5), ic : (X #\= 2), X is 2
?- ic : (X :: 1 .. 5), ic : (X #\= 2), X is 3
?- ic : (X :: 1 .. 5), suspend : (X > 2)
?- ic : (X :: 1 .. 5), suspend : (X > 2), X is 3
?- ic : (X :: 1 .. 5), suspend : (X > 2), X is 2
?- ic : (X :: 1 .. 5), ic : (X > 2)

Jak widać, predykat ic:#\= działa zgodnie z opisem, dziedzina się zmniejsza, zaś podstawianie wartości za X jest należycie sprawdzane. Mimo, że użycie predykatu suspend:> również mogłoby zmniejszyć dziedzinę, nie dzieje się tak, gdyż realizuje on inny schemat zachowania. Dziedzinę zmniejsza analogiczny predykat z modułu ic, jednak robi to w jeszcze dalej idący sposób.

Wspomniany predykat ic:> realizuje tak zwaną spójność łukową. Poza opisanym już ograniczaniem dziedzi, gdy tylko jedna zmienna jest podstawiona, analogiczny proces odbywa się, gdy obie zmienne nie są podstawione. Najlepiej ilustrują to poniższe przykłady:

ic : ([X,Y] :: 1 .. 5), ic : (X > Y)
ic : ([X,Y] :: 1 .. 5), ic : (X > Y), ic : (Y > 2)

Zauważ, co się stało w drugim przypadku. Dołożenie ograniczenia na zmienną Y spowodowało dalsze ograniczenie zmiennej X. Zachowanie takie jest istotą omawianej propagacji ograniczeń i jednocześnie powodem rozróżniania tylu ich rodzajów – im więcej informacji staramy się wyciągnąć z ograniczenia, tym drożej to kosztuje. Z tego powodu również na przykład predykat ic:#= propaguje tylko ograniczenia na zakres dziedziny, a nie na jej poszczególne elementy w środku.

7. Fabryka słodyczy, część 2.

Na początek wróćmy do ograniczenia constr_nth z poprzedniej części.

delay constr_nth(Domain, Which, Value) if (var(Which); var(Domain)).
constr_nth(Domain, Which, Value) :- nth1(Which, Domain, Value).

Pierwsza linijka powyższego fragmentu kodu określa, że sprawdzanie poniższego predykatu należy opóźnić, dopóki zmienne Which oraz Domain nie zostaną ustalone. Jest to typowy przykład tworzenia własnego ograniczenia – poza predykatem, co ograniczenie oznacza, określamy, kiedy ma zostać sprawdzane. Sprawdź, co się stanie, jeśli usuniesz linijkę określającą opóźnienie. Wypróbuj różne tablice z optymalnymi wyborami na różnych pozycjach. Przemyśl, dlaczego tak się dzieje. Dlaczego ograniczenie constr_nth nie może po prostu sprawdzać spójności?

Zadanie dla chętnych: Zmodyfikuj warunek opóźnienia tak, aby ograniczenie obliczało pozycję elementu na liście, o ile występuje on na niej dokładnie raz, i było niespełnione, gdy na niej nie występuje. Sprawdź poprawność swojego kodu.

Drugi problem fabryki

Po ostatniej próbie przyszedł w końcu czas na trudniejsze zadanie. Będziemy je rozwiązywać etapami. Najpierw jednak przedstawmy na czym polega sam problem:

Fabryka słodyczy może produkować dwa rodzaje czekolady bądź czekoladki z orzechami. Do każdego z tych wyrobów potrzebuje odpowiednią ilość składników: kakao oraz orzechów. Towary te są oferowane przez dwóch dostawców po różnych cenach. Z powodu ustawy antykorupcyjnej, która niedawno weszła w życie nie można jednak zamówić obydwu towarów u tego samego dostawcy. Fabryka ma określoną ilość pieniędzy, które może przeznaczyć na produkcję oraz zadane ceny, po których sprzedaje każdy ze swoich wyrobów. Fabryka może sprzedać maksymalnie 200 jednostek każdego z wyrobów. Celem jest maksymalizacja zysku fabryki.

Zanim przejdziemy do kodu, zastanówmy się chwilę nad zadaniem. Jego główna część jest zadaniem programowania liniowego (maksymalizacja zysku przy ograniczeniu pieniędzy), jednak stawiane są dodatkowe wymogi, w związku z czym nie można po prostu zastosować znanych procedur rozwiązujących zadania PL. Zostanie jednak pokazane jak można z nich skorzystać w celu poprawy efektywności rozwiązania.

Pierwsza wersja rozwiązania będzie zawierała drobne oszustwo – zmienne decyzyjne odpowiedzialne za określenie wielkości dostaw będą dyskretne. Tak uproszczoną wersję każdy powinien móc rozwiązać w tym momencie i próba rozwiązania jest zalecana.

Predykat testujący:

callP3(Income, W, Q) :- problem3([[1.5, 1], [3, 2]], [2, 3, 4],
                                     500, Income, W, [[1.0, 0],
                                                             [0.7, 0],
                                                             [0.5, 1]],
                                 Q).

Kolejnymi argumentami predykatu problem3 rozwiązującego zadanie są koszty towarów u poszczególnych dostawców, ceny sprzedaży produktów, pieniądze przeznaczone na produkcję, zysk, wybrani dostawcy poszczególnych towarów, lista ilości towarów potrzebnych do wyprodukowania produktów oraz wielkości produkcji poszczególnych produktów.

Poniżej znajduje się przykładowe rozwiązanie dla porównania:

problem3([CPLS, CPIS], [P1, P2, P3],
         Money, Income, [W1, W2], [[R11, R12], [R21, R22], [R31, R32]],
         [Q1, Q2, Q3]) :-
        length(CPLS, N),
        length(CPIS, M),
        W1 :: 1 .. N, % który dostawca dostarcza zasób 1
        W2 :: 1 .. M, % który dostawca dostarcza zasób 2
        constr_nth(CPLS, W1, C1),
        constr_nth(CPIS, W2, C2),
        W2 #\= W1, % muszą być różni dostawcy
        Q1 :: 0 .. 200, % ile produkujemy czekolady 1
        Q2 :: 0 .. 200, % ile produkujemy czekolady 2
        Q3 :: 0 .. 200, % ile produkujemy czekoladek
        R1 $= Q1 * R11 + Q2 * R21 + Q3 * R31, % ile potrzeba zasobu 1
        R2 $= Q1 * R12 + Q2 * R22 + Q3 * R32, % ile potrzeba zasobu 2
        Cost $= C1 * R1 + C2 * R2,
        Cost $=< Money,
        Income $= P1*Q1 + P2*Q2 + P3*Q3 - Cost,
        Loss $= -1.0 * Income,
        minimize(labeling([W1, W2, Q1, Q2, Q3]), Loss).

Wykonanie powyższego kodu zostawia 3 opóźnione cele. Jeśli jakaś zmienna decyzyjna nie zostałaby znaleziona, mogłoby to wskazywać na przyczynę. Jednak często jest to wyłącznie efekt wykorzystywania arytmetyki przedziałów (zmienne rzeczywiste). Można to potwierdzić otwierając okno Tools>Delayed Goals w ECLiPSe.

Można również zauważyć, że kod wykonuje się bardzo wolno – kilka sekund. Jest to spowodowane koniecznością przejrzenia dużej przestrzeni rozwiązań (zmienne Q1, Q2, Q3), która nie jest zmniejszana przez wprowadzane ograniczenia (na całkowity koszt). Nie jest wykorzystywana również struktura przestrzeni rozwiązań. Informatyk może tu jednak dostrzec problem programowania liniowego i wykorzystać to spostrzeżenie do optymalizacji programu.

Eplex -- programowanie liniowe w ECLiPSe

Eplex jest biblioteką ECLiPSe będącą interfejsem do zewnętrznych programów rozwiązujących problemy programowania liniowego (ciągłe, całkowitoliczbowe oraz mieszane). Pełna dokumentacja znajduje się pod adresem http://www.eclipseclp.org/doc/libman/libman052.html. Poniżej omówione zostaną najważniejsze elementy biblioteki, co umożliwi jej wykorzystanie do sprawnego rozwiązania problemu fabryki.

Na początek skompiluj i uruchom poniższy kod:

:- lib(eplex).
:- eplex_instance(my_instance). % tworzy instancję biblioteki
 
lp_example(Cost) :-
     my_instance: eplex_solver_setup(min(X)),
     my_instance: (X+Y $>= 3),
     my_instance: (X-Y $= 0),
     my_instance: eplex_solve(Cost).

Druga linia kodu tworzy instację my_instance. Jest to jakby kontener na zmienne i ograniczenia – każda instancja ma osobne ich zbiory. Istnieje również domyślna instancja o nazwie eplex. Predykat lp_solve działa na instancji my_instance, co widać po składni – korzysta on z predykatów z modułu o takiej właśnie nazwie.

Predykat eplex_solver_setup ustawia cel optymalizacji. Może to być minimalizacja (jak w przykładzie) lub maksymalizacja (wtedy zamiast min jest max). X jest celem optymalizacji – w przykładzie szukamy rozwiązania dopuszczalnego z najmniejszą wartością X. Zamiast X możemy wpisać dowolne wyrażenie liniowe od zmiennych decyzyjnych (dla problemu programowania liniowego), np. 2*X+Y. Sprawdź i zobacz, co się stanie.

Kolejne dwie linie po prostu określają ograniczenia liniowe na zmienne. W przeciwieństwie do biblioteki ic, nie ma tu potrzeby wcześniejszego definiowania zmiennych, choć jest to możliwe (również za pomocą operatorów :: oraz $::). Ostatnia linijka wywołuje samą procedurę optymalizacji, unifikując znalezioną wartość celu ze zmienną Cost.

Przed pracą z biblioteką należy uczynić jeszcze trzy uwagi:

  1. Wprowadzane ograniczenia akumulują się cały czas. Jedynym sposobem ich usunięcia jest skorzystanie z predykatu my_instance: eplex_cleanup czyszczącego daną instancję.
  2. Czasami przydatna jest wiedza dla jakich wartości zmiennych osiągana jest optymalna wartość celu. Używa się do tego predykatu eplex_var_get jak w przykładzie poniżej. Dla jasności zmienna w instancji eplex i w środowisku ECLiPSe mają różne nazwy. Co się stanie, jeśli nazwy będą takie same? A co, jeśli zmienna X miałaby określoną wartość (np. 5.0) przed określeniem ograniczeń?
  3. Sprawdź, co robi predykat my_instance: integers([X]) (przyjmuje on listę zmiennych).
lp_example(Cost, XX) :-
     my_instance: eplex_solver_setup(min(2*X+Y)),
     my_instance: (X+Y $>= 3),
     my_instance: (X-Y $= 0),
     my_instance: eplex_solve(Cost),
     my_instance: eplex_var_get(X, typed_solution, XX).

Przetestuj, jak eplex reaguje na problemy PL różnych typów (posiada rozwiązanie, jest sprzeczny, jest nieograniczony). Sam skonstruuj odpowiednie problemy.

Powrót do fabryki

W tym momencie wiemy już wszystko, co jest potrzebne do zastosowania biblioteki eplex w drugim problemie fabryki. Jest jednak pewien haczyk. Nie mamy pojedynczego problemu programowania liniowego, lecz jego postać zależy od wartości zmiennych W1 i W2. Nie jest to oczywiście duży problem, jednak wymaga zmiany dotychczasowego schematu zmienne → ograniczenia → przeszukiwanie. Poszukiwanie rozwiązania musi być tu dwustopniowe: zewnętrzne przeszukiwanie przeszukuje przestrzeń wartości zmiennych W1 i W2, zaś wewnętrzne jest już samym problemem programowania liniowego. Poniżej znajduje się pomocniczy predykat, który go rozwiązuje. Zawiera on jednak kilka dziur (trzykropki) do samodzielnego uzupełnienia. Nazwy argumentów zgadzają się z wcześniej stosowanymi nazwami zmiennych.

solve3_lp([C1, C2], [P1, P2, P3],
         Money, Income, [[R11, R12], [R21, R22], [R31, R32]],
         [Q1, Q2, Q3], Loss) :-
        my_instance: ([Q1, Q2, Q3] $:: 0.0..200.0), % ograniczenie na
                                                    % wielkość produkcji
        my_instance: integers([Q3]), % możemy produkować tylko
                                     % całkowitą liczbę czekoladek
        my_instance: (R1 $= ...),
        my_instance: (R2 $= ...),
        my_instance: (Cost $= ...),
        my_instance: ..., % ograniczenie na koszt
        my_instance: (Income $= ...), % zysk
        my_instance: eplex_solver_setup(max(Income)),
        my_instance: eplex_solve(Income),
        ...% pobranie wartości zmiennych Q1, Q2, Q3
        ...% czyszczenie instancji
        Loss $= -1.0 * Income.

W tym momencie większość pracy już za nami. Wystarczy wprowadzić kilka zmian do samego predykatu znajdującego rozwiązanie problemu fabryki (opis dla predykatu przykładowego; jeśli zrobiłeś własny, konieczne zmiany mogą wyglądać nieco inaczej). Przede wszystkim należy usunąć wszystkie linie, które rozwiązywały podzadanie programowania liniowego. Druga zmiana jest już bardzo drobna: cel minimalizacji strat (użycie predykatu minimize) rozszerzamy o wywołanie pomocniczego predykatu solve3_lp (dla ułatwienia wszystkie nazwy zmiennych się zgadzają) oraz usuwamy zmienne Q1, Q2 i Q3 z listy dla predykatu labeling (dlaczego?).

Sprawdź, czy otrzymujesz poprawne wyniki (porównując z poprzednim programem nie korzystającym z biblioteki eplex. Proszę pamiętać o załączeniu biblioteki eplex w kodzie i stworzeniu instancji o nazwie my_instance.

Rabaty od dostawców

Sytuacja może być jednak jeszcze bardziej skomplikowana. Na przykład, sprzedający mogą oferować rabaty przy zamawianiu dużej ilości towaru. Co należy zmodyfikować, aby program poprawnie obsługiwał takie sytuacje? Przyjrzymy się obywdu przypadkom: z wykorzystaniem biblioteki eplex i bez.

Podstawową zmianą, wspólną w obu scenariuszach jest konieczność obsługi wielu przypadków dostarczania jednego towaru przez danego dostawcę.

problem4([CPLS, CPIS], [P1, P2, P3],
         Money, Income, [W1, W2, WW1, WW2], [[R11, R12], [R21, R22], [R31, R32]],
         [Q1, Q2, Q3]) :-
        length(CPLS, N),
        length(CPIS, M),
        W1 :: 1 .. N,
        W2 :: 1 .. M,
        constr_nth(CPLS, W1, CC1), % wybór dostawcy
        constr_nth(CPIS, W2, CC2), % wybór dostawcy
        W2 #\= W1, % dostawcy muszą być różni
        constr_length(CC1, NC1), % nie znamy CC1 i CC2 w tym momencie!
        constr_length(CC2, NC2),
        WW1 :: 1 .. 10, %dlaczego nie NC1? jak to uogólnić?
        WW2 :: 1 .. 10,
        ic: (WW1 #=< NC1),
        ic: (WW2 #=< NC2),
        constr_nth(CC1, WW1, C1), % wybór oferty dostawcy
        constr_nth(CC2, WW2, C2), % wybór oferty dostawcy

Powyżej znajduje się zmodyfikowany kod, w którym CPLS i CPIS zamieniły się w listy list – zamiast pojedynczej oferty, jest lista ofert. Każda z pozycji oznacza cenę. W tym przypadku wybór dostawców jest oznaczany czterema zmiennymi – W1, W2, WW1 i WW2. Pierwsze dwie oznaczają dostawcę odpowiedniego towaru, a drugie numer oferty. Proszę przyjrzeć się kodowi i zrozumieć jak działa. Ciekawym ćwiczeniem może być próba dokładnego zdefiniowania zakresu dla zmiennych WW1 i WW2 – proszę pamiętać, że na każdej liście może być różna liczba ofert. Predykat constr_length jest analogiczny do constr_nth, tyle, że opiera się na predykacie length. Jego napisanie jest pozostawione jako ćwiczenie.

Eplex

Jak już było wspomniane, w tym miejscu mamy już określone ceny produktów, brakuje jednak ograniczeń wynikających z ofert. Ponieważ w tym punkcie korzystamy z eplex, należy je wyrazić w sposób liniowy w solve4_lp – analogu solve3_lp. Jedyne wymagane zmiany to rozszerzenie listy argumentów o listę wyborów W = [W1, W2, WW1, WW2] i użycie predykatu ustanawiającego dodatkowe warunki w zależności od oferty.

eplex_offer([_, 1, _, 2], R1, R2) :-
        my_instance: (R1 $>= 4000),
        !. % uwaga na cut -- dzięki temu nie natrafiamy
           % na zawsze działający przypadek poniżej, gdy
           % dopasujemy się tutaj
eplex_offer(_, _, _).

Ten przykładowy predykat ustalający ograniczenia ofert działa dla drugiej oferty pierwszego dostawcy drugiego towaru. Ustala minimalną wielkość zamówienia. Istotną rzeczą jest ucięcie backtrackingu na końcu – domyślnym stanem oferty jest brak wymagań (druga definicja predykatu) i nie jest wskazane, aby oferty pasujące do przypadku szczególnego były rozważane też bez wymagań. Jest jednak pewien problem z tym predykatem – jeśli wybierzemy dwie oferty z ograniczeniami, to zostaną nałożone warunki tylko jednej z nich. Jak sobie z tym poradzić?




Komentarz:

Powyższy problem jest nietrywialny. Kilka godzin nad nim siedziałem, choć na pierwszy rzut oka wydaje się dość prosty. Okazało się, że backtracking powoduje wycofanie naniesionych ograniczeń, co dość istotnie utrudnia stworzenie poprawnej implementacji. W tej chwili moje rozwiązanie wygląda tak:

eplex_offer(W, R1, R2, 1) :-
        W = [_, 1, _, 2],
        writeln('bb'),
        my_instance: (R1 $= 400000),
        writeln('bb'),!, member(X, [2,3]), eplex_offer(W, R1, R2, X).
                         % uwaga na cut -- dzięki temu nie natrafiamy
                         % na zawsze działający przypadek poniżej, gdy
                         % dopasujemy się tutaj
eplex_offer(_, _, _, 2) :- writeln('fail'), fail.
eplex_offer(_, _, _, 3) :- writeln('vc'), !.

member na końcu pierwszej definicji pozwala przechodzić do kolejnych. fail w drugiej obrazuje niespełnienie warunków koniecznych do wprowadzenia ograniczenia. Ostatnia definicja ma na końcu cut, aby predykat był deterministyczny (jeden z warunków poprawnego działania). Ostatni argument predykatu po prostu numeruje definicje i umożliwia przechodzenie do następnych.

Dałoby się to zrobić bardziej ogólnie metaprogramowaniem (lista predykatów warunek+ograniczenie, które po kolei są callowane), ale nie jestem pewien, czy to dobry pomysł – może odstraszyć studentów.

call_all([], _,  _, _).
call_all([P|T], W, R1, R2) :-
        CC =.. [P, W, R1, R2],
        writeln('f'),
        (call(CC); true), !,
        writeln('m'),
        call_all(T, W, R1, R2).
offer1(W, R1, R2) :- W = [_, 1, _, 2], my_instance: (R1 $= 400000), writeln('bb').
offer2(W, R1, R2) :- fail.
meta_offer(W, R1, R2) :-
        call_all([offer1, offer2], W, R1, R2).



Bez Eplex

Z uwagi na brak konieczości wyrażania ograniczeń w eplex i jednopoziomowość metody, dodanie odpowiednich ograniczeń nie powinno stanowić problemu – wszystkie potrzebne elementy zostały już pokazane i powinieneś móc sam zaimplementować odpowiednie zmiany.

8. Wizualizacja przeszukiwania w ECLiPSe

Środowisko ECLiPSe umożliwia przyglądanie się przeszukiwaniu przestrzeni rozwiazań. Robi się to za pomocą specjalnych adnotacji w programie oraz klienta wizualizacji. Poniższy kod rozwiązuje zagadkę SEND+MORE=MONEY. Ma przy tym wywołanie predykatu umożliwiające śledzenie pracy predykatu przeszukującego.

:- lib(ic).
:- lib(viewable).
 
sendmore(Digits) :-
    Digits = [S,E,N,D,M,O,R,Y],
    Digits :: [0..9],
    viewable_create(digits, Digits),
    Carries = [C1,C2,C3,C4],
    Carries :: [0..1],
    alldifferent(Digits),
    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,
    labeling(Carries),
    labeling(Digits).

Normalne uruchomienie tego tego programu spowoduje po prostu uzyskanie rozwiązania zagadki. Wybierz polecenie Options > Visualization Client i wróć do okna programu ECLiPSe. Uruchom ponownie predykat sendmore. Klient wizualizacji zapyta o metody, jakimi chcemy wizualizować problem. Należy wybrać TextTable. Wybranie więcej niż jednej może spowodować nieoczekiwane problemy w dalszej części ćwiczenia.

Rozciągając okno, skalując widok (View > Zoom …) i rozszerzając kolumnę dostosuj tabelkę tak, aby dobrze widzieć jej zawartość. Są to kolejne zmienne z opisywanego problemu. Wciśnięcie przycisku Resume spowoduje zobrazowanie rozwiązywania – sprawdź. Pola tabeli aktualizowały się jednak zbyt często. Aby to zmienić, należy zaznaczyć wszystkie pola (View > Select all viewlets) i wybrać z menu kontekstowego Hold on updates. Spowoduje to, jak wskazuje nazwa, zatrzymanie po każdej aktualizacji. Można wznawiać ręcznie lub wybrać Options > Auto resume (sprawdź oba rozwiązania).

Poprawianie widoku

Omówiony mechanizm jest już stosunkowo przydatny, jednak można go znacznie ulepszyć konstruując widok rozwiązania lepiej oddający problem. Sumowanie może być w naturalny sposób przedstawione w postaci tablicy:

[ 0 S E N D ]
[ 0 M O R E ]
[ M O N E Y ]

Taką strukturę widoku można uzyskać zmieniając polecenie viewable_create w następujący sposób:

viewable_create(equation,[[0, S, E, N, D],[0, M, O, R, E],[M, O, N, E, Y]])

Jeśli w trakcie już po stworzeniu widoku chcielibyśmy modyfikować rozmiary wyświetlanej tablicy, należy to odpowiednio zaznaczyć w wywołaniu viewable_create. Można to osiągnąć w trójargumentowej wersji tego predykatu:

viewable_create(equation,
                [[0, S, E, N, D],
                 [0, M, O, R, E],
                 [M, O, N, E, Y]],
                array([flexible,fixed], any)),

Pierwszym argumentem termu array jest lista określająca, czy dany wymiar jest stały, czy nie. W podanym przykładzie tylko pierwszy wymiar (ten zewnętrzny) może się zmieniać. drugi argument określa rodzaj danych, jakie będą wizualizowane.

Aby przetestować działanie opisanej funkcjonalności, należy na końcu programu umieścić polecenie wyświetlające wartosci przeniesień:

    labeling(Carries),
    labeling(Digits),
    viewable_expand(equation, 1, [C1, C2, C3, C4, 0]).

Możliwe jest też nazwanie poszczególnych kolumn i wierszy:

viewable_create(equation,
                [[0, S, E, N, D],
                 [0, M, O, R, E],
                 [M, O, N, E, Y]],
                array([flexible,fixed], numeric_bounds),
                    [["send", "more", "money"],
                     ["ten thousands", "thousands",
                      "hundreds", "tens", "units"]]),

Widok problemu grafowego

ECLiPSe umożliwia także wizualizację problemów grafowych. Dla przykładu przedstawiony jest problem szukania przepływów w sieci – mamy zadany wypływ ze źródła (i zarazem wpływ do ujścia) i zadaniem jest ustalenie wartości przepływów na krawędziach tak, aby z każdego węzła wychodziło tyle, ile do niego wchodzi.

Przeanalizuj krótko działanie poniższego programu. Skompiluj go i uruchom. Porównaj różne metody wizualizacji grafu.

UWAGA: Początkowo wszystkie węzły są umieszczane w tym samym miejscu. Można je poprzesuwać ręcznie lub skorzystać z automatycznego rozmieszczania (opcja graph > layout graph …).

:-lib(graph_algorithms).
:-lib(viewable).
:-lib(ic).
 
test:-
    make_graph(7,
               [e(1,2,F12), e(2,3,F23), e(2,4,F24), e(3,5,F35),
                e(4,5,F45), e(4,6,F46), e(5,6,F56), e(6,3,F63),
                e(6,7,F67)],
               Graph),
    Flows = [F23,F24,F35,F45,F46,F56,F63],
    Flows :: 0..5,
    (for(Node, 2, 6), param(Graph) do
        graph_get_incoming_edges(Graph, Node, InEdges),
        graph_get_adjacent_edges(Graph, Node, OutEdges),
        (foreach(e(_From, _To, Flow), InEdges),
         foreach(Flow, InFlow) do true),
        (foreach(e(_From, _To, Flow), OutEdges),
         foreach(Flow, OutFlow) do true),
        sum(InFlow) #= sum(OutFlow)
    ),
    F12 #= 9,
    viewable_create(flow_viewable, Graph, graph(fixed),
                    [node_property([0->[name(nodes), label]]),
                     edge_property([0->[name(edges), label]])
                    ]),
    labeling(Flows).
pl/prolog/prolog_lab/csp_eclipse.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0