Podręcznik: Programowanie w ograniczeniach

1. Programowanie w ograniczeniach

Programowanie w ograniczeniach (Constraint Programming) jest jedną z ogólnych metod rozwiązywania problemów, w których występują zmienne dyskretne. Choć może być wykorzystywane do optymalizacji rozwiązań, to w pierwotnym sformułowaniu bazuje na poszkiwaniu rozwiązania dopuszczalnego dla zadanego zbioru ograniczeń oraz zmiennych wraz z ich domenami (brak funkcji celu).

Problem spełnienia ograniczeń (Constraint satisfaction problem, CSP) jest opisywany przez trójkę

$(X,D,C)$ , gdzie

$X=\{x_1, \ldots, x_n\}$ jest zbiorem zmiennych problemu,
$D=\{D_1, \ldots, D_n\}$ jest zbiorem dziedzin zmiennych,
$C=\{C_1, \ldots, C_m\}$ jest zbiorem ograniczeń.

Ograniczenie

$C_i$ jest definiowane przez zbiór możliwych wartości

$R_i$ podzbioru

$k$ zmiennych

$X_i =\{x_{i_1}, \ldots, x_{i_k}\}$ , a więc

$R_i \subseteq D_{i_1} \times \ldots \times D_{i_k}$ , jakie zmienne

$X_i$ mogą jednocześnie przyjąć.

Domeną zmiennej decyzyjnej

$x$ jest zbiór wartości, które zmienna może przyjąć. Przykładowo, jeżeli

$x$ jest zmienną binarną jej domeną jest zbiór

$\{0,1\}$ . W wyniku działania algorytmów domeny mogą być zawężane. Przykładowo, załóżmy następujące ograniczenie

$16x_1 + 8x_2 + 5x_3 \geq 20$
gdzie

$x_1, x_2, x_3$ są zmiennymi binarnymi. Początkowa domena zmiennej

$x_1$ jest

$\{0,1\}$ . Jedna jak łatwo zauważyć, w przypadku

$x_1=0$ nie jest możliwe spełnienie ograniczenia, a zatem domena dla

$x_1$ może zostać zawężona do zbioru jednoelementowego

$\{1\}$ .

W trakcie rozwiązywania problemu do zmiennych przypisywane są wartości z ich domen. Przypisanie może być częściowe lub całkowite. Przypisanie

$A=(X_A,V_A)$ przypisuje podzbiorowi zmiennych

$X_A\subseteq X$ wartości

$\{v_{A_1}, \ldots, v_{A_n}\} \in \{ D_{A_1}, \ldots, D_{A_n}\}$ . Rozwiązaniem problemu CSP jest kompletne przypisanie

$A$ takie, że zbiór wartości

$V_A$ należy do każdego zbioru

$R_i$ (czyli spełnia wszystkie ograniczenia).

Problem optymalizacji w ograniczeniach (Constraint optimization problem, COP) jest problemem spełnienia ograniczeń wraz z przypisaną funkcją celu. Rozwiązanie optymalne to rozwiązanie skojarzonego problemu CSP, które minimalizuje (maksymalizuję) funkcję celu.
Jednak COP może być używane nie tylko w kontekście poszukiwania rozwiązania najlepszego. Inne możliwe scenariusze to poszukiwanie rozwiązania dopuszczalnego (np. dla problemów, w których znalezienie dopuszczalności jest już zadaniem trudnym), udowodnienie optymalności zadanego rozwiązania lub udowodnienie sprzeczności problemu.