Programowanie z ograniczeniami (ang. Constraint Programming, dalej nazywane CSP) jest deklaratywnym paradygmatem programowania, skupionym na modelowaniu problemu i wskazaniu wymagań (ograniczeń) stawianych jego rozwiązaniom. Do obowiązków programisty należy:

• zamodelowanie problemu poprzez zdefiniowanie zmiennych o odpowiedniych dziedzinach,
• zdefiniowanie ograniczenia, które określają dozwolone wartości zmiennych w rozwiązaniu
• [opcjonalne] podanie kryterium oceny rozwiązania, np. minimalizacja długości trasy w problemie komiwojażera
• [opcjonalne] sprecyzowanie procesu przeszukiwania przestrzeni możliwych rozwiązań.

Poniższe laboratoria mają za zadanie przedstawić motywacje oraz podstawowe techniki programowania CSP.

Przypuścmy, że pracujemy jako kelner w restauracji, która leży w pobliżu trwającej akurat konferencji informatyków zajmujących się optymalizacją dyskretną. Jest to bardzo niewdzięczna praca – przydarzają nam się różne nieprzyjemne przygody, takie jak ta opisana w poniższym komiksie:

Sytuacja byłaby beznadziejna, ale na szczęście jest CSP. W dalszej części laboratorium będziemy modelować i rozwiązywać problem przedstawiony w komiksie.

• MiniZinc (CSP solver)
• MiniZinc IDE

Ściągnięte archiwa zawierają skompilowane już pliki binarne. Instalacja sprowadza się do rozpakowania plików. W przypadku paczki zawierającej solver rozsądne jest wywołanie skryptu SETUP, który przygotowuje środowisko do działania. W przypadku paczki zawierającej IDE, uruchamia się ono poprzez uruchomienie skryptu MiniZincIDE.sh. Po pierwszym uruchomieniu może być konieczne wskazanie ściezki do katalogu z solverem.

Napisanie prostego programu w języku MiniZinc sprowadza się do czterech kroków.

Chcemy ustalić z czego ma składać się zamówienie, zatem potrzebujemy wiedzieć, ile razy ma zostać zamówione każde danie z osobna. Każda zmienna ma opisywać ile egzemplarzy danego dania zamówiono, powinna być więc typu liczby całkowitej (zakładamy, że nie można zamówić połowy dania). W MiniZinc zapiszemy to następująco:

var int: fruit;
var int: fries;
var int: salad;
var int: wings;
var int: sticks;
var int: sampler;

Jesteśmy przekonani, że nie da się zamówić ujemnej liczby dań, zatem wprowadzamy odpowiednie ograniczenia korzystając ze słowa kluczowego constraint:

constraint fruit >= 0;
constraint fries >= 0;
constraint salad >= 0;
constraint wings >= 0;
constraint sticks >= 0;
constraint sampler >= 0;

Ponadto wiemy, że suma kosztów zamówień ma być równa pewnej liczbie. Na razie będziemy używać jedynie liczb całkowitych i po prostu wszystkie ceny pomnożymy przez 100.

constraint fruit*215 + fries*275 + salad*335 + wings*355 + sticks*420 + sampler*580 == 1505;

Szukamy takiego zamówienie, które spełnia (ang. satisfies) zadane ograniczenia. Słowo kluczowe solve oznacza moment, w których wybierany jest cel programu.

solve satisfy;

Na koniec definiujemy, jak ma wyglądać wynik działania programu - służy do tego słowo kluczowe output:

output ["fruit:", show(fruit), "\t fries:", show(fries), 
        "\t salad:", show(salad), "\t wings:", show(wings),
        "\t sticks:", show(sticks), "\t sampler:", show(sampler)];

Wszystkie powyższe linijki należy skopiować w danej kolejności do pliku z rozszerzeniem .mzn. Następnie w katalogu z plikiem, należy wykonać:

mzn-g12fd <nazwa_pliku>

lub

mzn-g12fd --all-solutions <nazwa_pliku>

jeżeli nie chcemy, by solver zatrzymał się pierwszym możliwym rozwiązaniu. W IDE można to wszystko „wyklikać” we względnie intuicyjny sposób.

Komiks twierdzi, że dostaniemy napiwek, jeżeli zdołamy stworzyć rozwiązanie ogólne. Napiwki są przydatne, zatem bierzemy się do roboty i parametryzujemy nasz problem.

Najpierw ustalamy, ile pozycji zawiera menu i do jakiej liczby ma się równać koszt zamówienia. Brak słówka var sugeruje, że te wartości są niezmienne.

int: menu_length = 6;
int: money_limit = 1505;

Następnie posłużymy się tablicami w celu opisania zawartości menu. Każda tablica ma ustalony zakres indeksów i typ swoich elementów.

array[1..menu_length] of int: menu_prices = [215, 275, 335, 355, 420, 580];
array[1..menu_length] of string: menu_names = ["fruit", "fries", "salad", "wings", "sticks", "sampler"];

W wersji za napiwek liczba zmiennych również jest sparametryzowana – jest ich tyle samo, ile pozycji w menu.

array[1..menu_length] of var int: order;

Liczba ograniczeń również zależy od rozmiarów menu. Aby je zdefiniować, posłużymy się funkcjami agregującymi: forall — dołącza wszystkie ograniczenia w tablicy, sum — sumuje liczby zawarte w tablicy. Notacja [array[i]*2 | i in 1..array_length] jest nazywana array comprehension i należy ją rozumieć jako wyrażenie przetwarzające elementy z jednej tablicy (1..array_length) na nową tablicę zawierającą elementy po lewej stronie |.

constraint forall([order[i] >= 0 | i in 1..menu_length]);
constraint sum([order[i] * menu_prices[i] | i in 1..menu_length]) == money_limit;

Cel nie ulega zmianie.

Aby wypisać wynik, również posłużymy się notacją array comprehension. Operator '++' łączy napisy, funkcja show przekształca liczbę w napis.

output [menu_names[i] ++ ": " ++ show(order[i]) ++ "\n" | i in 1..menu_length];

Przebiega bez zmian. Proszę uruchomić program i zainkasować 50% z wyimaginowanej sumy pieniędzy.