Podręcznik

Wyróżniamy następujące reguły podziału podproblemów.

Podział na 2 części (dytochomiczny)

• przy stosowaniu relaksacji liniowej wprowadzane są dwa ograniczenia na zmienną $x_i$, której wartość nie jest całkowitoliczbowa: jeśli zapiszemy wartość $x_i=n+d$, gdzie $d$ jest częścią ułamkową, to warunki podziału mają postać:
  • $x_i \leq n$
  • $x_i \geq n+1$
• generalizacja podziału, tzw. ograniczenie GUB (generalized upper bound): w zadaniach przydziału, w których wymagamy aby tylko jedna zmienna miała wartość niezerową, czyli z ograniczeniami postaci $\sum_i x_i = 1$ można dzielić węzeł, ze względu na sumaryczną wartość zmiennych, których wartości są zbliżone, czyli dzielimy $S = S_1 \cup S_2$ i wymagamy aby $\sum_{i\in S_1} x_i =0$ lub $\sum_{i\in S_2} x_i =0$ (w orginalnym zbiorze $S$ te dwie sumy są ułamkowe i mają zbliżone wartości)

• wg największej/najmniejszej niedopuszczalności - wybierana zmienna, której wartość jest najdalej/najbliżej od jej wartości zaokrąglenia
• na podstawie szacowanej wartości zmiennej: różne sposoby szacowania pogorszenia funkcji celu, aby ocenić opłacalność wymuszenia ograniczenia danej zmiennej
• wyliczanie kar (penalty) na podstawie kosztów zredukowanych zmiennej, dla której sprawdzamy koszty wyjścia z bazy (w metodzie dual simplex),
• szacowanie pseudokosztów zredukowanych na podstawie wartości f. celu, w której zmienna wymuszona na wartość całkowitoliczbową,
• szacowanie pseudocen dualnych - j.w. tylko w odniesieniu do cen dualnych, a nie kosztów zredukowanych,
• silny podział (strong branching) - wyliczenie wartości f. celu w kilku iteracjach algorytmu simplex, przy ustalonej (całkowitoliczbowej) wartości zmiennej;
• użycie priorytetów podanych przez użytkownika.

Użycie hiperpłaszczyzn (branch and cut)

• Na podstawie znajomości struktury problemu dodajemy odcięcia angażujące większą liczbę zmiennych, uzyskane np. poprzez agregację niektórych ograniczeń.

Podział na wiele części (politochomiczny)

• Przykładowo, w problemie komiwojażera (TSP), dla relaksacji opartej na drzewie rozpinającym możemy wybierać wiele restrykcji dla konkretnego podproblemu, gdyż sprowadzają się one do usunięcia konkretnych krawędzi z aktualnej drogi TSP; przykład można znaleźć w książce W. L. Winstona „Operations research - Applications and Algorithms" Thomson Learning (2004);
• priorytet zmiennej do wyboru na podst. znajomości problemu: w najprostszym przypadku wg wektora cen.