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.