Podręcznik

3. Techniki restrykcyjne i relaksacyjne

Wiele trudnych obliczeniowo problemów optymalizacji dyskretnej ma strukturę, która poddaje się dekompozycji, czyli może być rozbita na stosunkowo łatwe do rozwiązania podproblemy. Podproblemy te można wydzielać dla grupy ograniczeń, bądź zmiennych. Pozwala to na pominięcie pewnych sprawiających trudność ograniczeń lub zmiennych całkowitoliczbowych, które są następnie ujmowane w procesie poszukiwania rozwiązywania, najczęściej w iteracyjny sposób.  W pierwszym przypadku, tj. wydzielania trudnych ograniczeń, szczególnie użyteczne są metody relaksacji Lagrange‘a, w drugim zaś techniki restrykcyjne, np. metoda dekompozycji Bendersa.