2. Metoda płaszczyzn tnących

2.3. Rodzaje cięć

Różne pakiety optymalizacyjne umożliwiają zastosowanie różnych cięć. Przykładowo IBM ILOG Cplex zawiera m.in. następujące cięcia:

  • Clique Cuts (co najwyżej jedna zmienna binarna równa 1)
  • Cover Cuts (dla ograniczeń plecakowych)
  • Disjunctive Cuts (cięcia zgodne dla jednego podproblemu drzewa podziału i niezgodne dla drugiego)
  • Flow Cover Cuts (wielkość przepływu uzależniona od zmiennej binarnej, podobne do plecaka)
  • Flow Path Cuts
  • Gomory Fractional Cuts
  • Generalized Upper Bound (GUB) Cover Cuts
  • Implied Bound Cuts
  • Mixed Integer Rounding (MIR) Cuts
  • Zero Half Cuts

Warto,wiedzieć jakie cięcia są wykorzystywane, aby świadomie sterować procesem. W szczególności zazwyczaj można odczytać liczbę dodanych cięć lub dla każdego typu cięcia można ustawiać parametry takie jak częstość danego rodzaju cięć, zakaz cięć, strategia (np. umiarkowana lub agresywana) stosowania cięć danego rodzaju.


Cięcia Cover cuts

Rozważamy ograniczenie typu (\(x_j\) -- zmienna binarna)

\(\sum_{j=1}^n a_jx_j \leq b\)

Zbiór \(C \subseteq N =\{1, \ldots, n\}\) jest pokryciem jeżeli

\(\sum_{j\in C} a_j > b\)

Pokrycie jest minimalne jeżeli \(C \setminus \{j\}\) nie jest pokryciem dla dowolnego \(j \in C\).

Zauważmy, że cięcie 

\(\sum_{j\in C} x_j \leq |C|-1\)

jest zgodne. Pytanie, czy można wygenerować lepsze cięcia? Rozważmy następujący przykład.

\(11x_1+6x_2+6x_3+5x_4+5x_5+4x_6+x_7 \leq 19\)
Przykładowe cięcia jakie możemy dodać:
\(x_1+x_2+x_3 \leq 2\)
\(x_3+x_4+x_5+x_6 \leq 3\)

Ogólnie, cover cut można poszerzyć

\(\sum_{j\in E(C)} x_j \leq |C|-1\)

gdzie

\(E(C)=C \cup \{j: \forall i \in C, a_j \geq a_i \}\)

Kontynuując poprzedni przykład
\(11x_1+6x_2+6x_3+5x_4+5x_5+4x_6+x_7 \leq 19\)
cięcie
\(x_3+x_4+x_5+x_6 \leq 3\)
możemy poszerzyć do
\(x_1+x_2+x_3+x_4+x_5+x_6 \leq 3\)


Cięcia Chvatala-Gomory'ego

Niech \(a=[a]+\{a\}\) przy czym \([a]\) jest największą liczbą całkowitą nie większa od \(a\), zaś \(\{a\}\) odpowiednią liczbą ułamkową.

  • Gdy \(a=\frac{5}{4}\), to \([a]=1\) i \(\{a\}=\frac{1}{4}\)
  • Gdy \(a=-\frac{1}{4}\), to \([a]=-1\) i \(\{a\}=\frac{3}{4}\)

Niech \(u \in \mathbb{R}^m_+\). Wówczas nierówność skalarna

\(\sum_{j=1}^n ua_jx_j \leq ub_j\)

jest zgodna z \(P\), gdyż \(u\geq 0\) oraz \(\sum_{j=1}^n a_jx_j \leq b_j\).

Nierówność

\(\sum_{j=1}^n [ua_j]x_j \leq ub_j\)

jest zgodna z \(P\), gdyż \(x\geq 0\).

Nierówność

\(\sum_{j=1}^n [ua_j]x_j \leq [ub_j]\)

jest zgodna z \(P\), gdyż \(x\) jest całkowite i \(\sum_{j=1}^n [ua_j]x_j\) jest całkowite

Chvatal pokazał, że w ten sposób można generować dowolne cięcia.