1. Programowanie w ograniczeniach

1.4. Rodzaje ograniczeń

Rodzaje ograniczeń
Można zauważyć, że rozważając różne problemy pewne rodzaje ograniczeń występują częściej. Dlatego często wyróżnia się specjalne typy ograniczeń, szczególnie jeżeli dla nich można dostarczyć specjalne, bardzie efektywne, metody obsługi, w szczególności redukcji domen i eliminacji zmiennych. Przytoczymy teraz często występujące ograniczenia:

  • ograniczenia logiczne np. wynikanie, np. jeżeli x=1 => y=0
  • alldifferent (x,y,z)  (w skrócie alldiff) - każda zmienna musi przyjąć inną wartość
  • circuit(succ) - wartości w succ muszą tworzyć cykla Hamiltona, czyli sekwencja 1, succ[1], succ[succ[1]], ... tworzy pętlę 1,...,n
  • distribute(car, value, base) - liczba wystąpień value[i] w base musi wynieść card[i]
  • pack - upakowuje elementy w pojemniki o ograniczonych pojemnościach
  • lexicographic - wymusa leksykograficzny porządek pomiędzy podzbiorami zmiennych decyzyjnych
  • ograniczenia dotyczące sekwencji, np. before, prev, first/last, noOverlap

Przykład modelowania
Jako przykład rozważym problem komiwojażera. Niech \(c_{ij}\) będzie odległością pomiędzy miastami \(i\) oraz \(j\). Zadanie polega na znalezieniu najkrótszej drogi, która odwiedza wszystkie miasta dkoładnie jeden raz. Jedno ze standardowych sformułowań programowania całkowitoliczbowego przyjmuje następującą postać:
\(\min \sum_{ij} c_{ij}x_{ij}\)
przy ograniczeniach
\(\sum_ix_{ij}=1 \quad \forall j\)
\(\sum_jx_{ij}=1 \quad \forall i\)
\(\sum_{i\in V}\sum_{j\in W}x_{ij} \geq 1, \quad \forall V,W\subset\{1,\ldots,n\}, V\cap W=\emptyset\)
\(x_{ij} \in \{0,1\}\)
gdzie, \(x_{ij}\) przyjmuje wartość 1, jeżeli miasto \(j\) jest odwiedzane bezpośrednio po mieście \(i\).
Trzecie ograniczenie odpowiada za eliminację podcykli.
Przykładowe sformułowanie problemu jako zadnia programowania w ograniczeniach może być następujące:
\(\min \sum_k c_{y_k,y_{k+1}}\)
przy ograniczeniach
\(alldiff(y_1, \ldots, y_n)\)
\(y_k \in \{1,\ldots, n\}\)
gdzie \(y_k\) przyjmuje wartość równą numerowi miasta odwiedzanego w \(k\)-tej kolejności. Pierwsze ograniczenie \(alldiff\) oznacza, iż każda zmienna musi przyjąć inną wartość.