Podręcznik

Podział domen (branching)
Aby efektywniej prowadzić przeszukiwanie rozwiązań stosuje się metodę podziału zmiennych (ich domen) w sposób podobny do metody podziału i oszacowań dla zadań programowania całowitoliczbowego. Wiąże się z tym problem wyboru zmiennej do podziału oraz problem wyboru sposobu podziału. Dla zmiennej binarnej naturalny jest podział na dwa podproblemy, każdy dla jednej wartości jaką zmienna może przyjąć. Jeżeli domena zmiennej zawiera więcej niż dwa elementy można stosować różne strategie, ale typowo przyjmuje się podział na rozłączne podzbiory, np. dla każdej możliwej wartości z domeny zmiennej lub na podzbiory $\{1,2\}$ i $\{3\}$ dla zmiennej z rozważanego powyżej przykładu. Taki podział może być prowadzony rekurencyjnie w głąb, aż do uzyskania sytuacji, w której podproblem można rozwiązać.

Eliminacja zmiennych
Podejście komplementarne do redukcji domen zmiennych jest redukcja zmiennych. Usunięcie zmiennej pociąga za sobą konieczność dodania nowych ograniczeń zdefiniowanych dla pozostałych zmiennych, które odpowiadają za wpły w zmiennej na pozostałe zmienne. Ograniczenia te zastępują dotychczasowe ograniczenia odnoszące się do eliminowanej zmiennej. Postępowanie jest powtarzanie rekurencyjnie, najlepiej aż do redukcji problemu do pojedynczej zmiennej. Rozważmy przykład wprowadzony powyżej, ale przyjmując, że każda zmienna może przyjmować wartości ze zbioru $\{1,2,3,4\}$. Zauważmy, że możliwa jest eliminacja zmiennej $x_2$, przymując, że pozostałe zmienne mogą przyjąć wartości $(x_1,x_3)\in\{(3,2), (4,2), (4,3)\}$. W ten sposób rozmiar problemu wyjściowego został istotnie zredukowany.