Podręcznik

Różnorodność problemów dyskretnych jest w zasadzie nieskończona. Wynika ona m.in. z niezwykle szerokiej gamy dziedzin, w której problemy optymalizacji dyskretnej mają zastosowanie. Jednocześnie, na najbardziej ogólnym poziomie problemy te łączy podobny cel: zwiększenie efektywności przy zachowaniu wymagań i ograniczeń na zasoby. Co więcej, często okazuje się, że problemy z różnych dziedzin wykorzystują podobne zestawy zmiennych decyzyjnych i ograniczeń, czyli dzielą podobną strukturę. Pomocne jest  zatem przestudiowanie reprezentatywnych przykładów, które mogą służyć jako paradygmaty podczas modelowania i rozwiązywania innych problemów o podobnej strukturze.

Przypomnijmy przy tym, że w przypadku rozwiązywania problemów dyskretnych gotowymi solwerami duże znaczenie może mieć sformułowanie modelu, w szczególności nierzadkie są przypadki niepotrzebnie złożonego sformułowania, wprowadzającego np. nieliniowości do modelu. Tym samym, zapoznanie się z klasycznymi problemami pomoże wypracować dobre praktyki tworzenia modeli optymalizacyjnych programowania matematycznego.

Klasy problemów

Wiele problemów dyskretnych może być przedstawianych jako zadania wyznaczania przepływów w sieci, należą do nich klasyczne problemy grafowe, takie jak:

•  Najkrótsze i najtańsze ścieżki, przepływy w grafach,
• Cykl komiwojażera: Traveling Salesperson Problem (TSP),
• Przydziały i skojarzenia: Assignment Problem,
• Minimalne drzewo rozpinające: Minimum spanning tree.

W tym rozdziale przedstawiamy jedynie kilka wybranych, klasycznych problemów alokacji zasobów.

Problem plecakowy: Knapsack problem

Problem plecakowy/ zadanie załadunku polega na jak najlepszym wykorzystaniu zasobu (plecaka), w którym należy upakować jak najwięcej przedmiotów. 

Oznaczenia:

• $i\in N$ zbiór typów przedmiotów o wartości $w_i$ i wielkości $a_i$,

• $p$ pojemność plecaka (zasobu)
  

• $x_i$ zmienna decyzyjna ile przedmiotów typu $i$ zapakować.

Funkcja celu: $\max\sum_i w_i x_i$

Ograniczenia dotyczą dostępności zasobu, oraz przedmiotów:

$\begin{matrix} &&\sum_i a_i x_i\leq p,\\ && x_i \subset C,\; \forall i\end{matrix}$

Warianty problemu plecakowego

Problem typu plecakowego ma szerokie zastosowania w różnych dziedzinach, np. do tej kategorii zaliczamy problemy inwestycyjne i zadania alokacjai budżetu. Dodatkowe uwarunkowania prowadzą do wariantów podstawowego problemu, wyróżniamy np.:

•  0-1 Knapsack - tylko po jednej sztuce każdego towaru jest dostępne,
• Bounded knapsack - dostępna jest ograniczona liczba sztuk każdego towaru,
• Change-making - pojemność plecaka musi być w pełni wykorzystana (czyli ograniczenia na zasób w postaci równości),
• Multiple Knapsack - wiele różnych plecaków, inaczej problemy typu bin-packing, które dalej mogą być rozważane wraz z ograniczeniami kolejnościowymi, oknami czasowymi, itd.

Problem bin-packing

Problemy pakowania  (i rozkroju, czyli w wariancie Cutting stock problem) najczęściej skupiają się na wykorzystaniu jak najmniejszej liczby zasobów.

Oznaczenia:

• $p_j$ pojemność pojemnika $j\in M$,

• $x_{ij}$ zmienna decyzyjna ile przedmiotów typu $i$ zapakować do pojemnika $j$,

• $y_{j}$ zmienna decyzyjna czy wykorzystać pojemnik  $j$.
  

Funkcja celu: $\min\sum_j y_j$

Ograniczenia:

$\begin{matrix} &&\sum_i a_i x_{ij}\leq p_jy_j\;\;\;\forall j\in M,\\ && \sum_jx_{ij}=1\;\forall i\in N\\ && x_{ij} \subset C,\; \forall i,j\end{matrix}$

Przydział zadań do procesorów/dostawców do odbiorców

Szeroka klasa problemów przydziału może być postrzegana jako wariant bin-packingu.  W problemie takim zasoby $j\in M$ to np. maszyny, dostawcy, itp. Natomiast zbiór $i\in N$ reprezentuje zbiór zdań do realizacji/obsłużenia.

Oznaczenia:

• $a_{i}$ jest zapotrzebowaniem zadania $i$, w wersji $a_{ij}$ zróżnicowanym ze względu na zasoby, np. odpowiada czasowi wykonania zadania $i$ na maszynie $j$,
• $f_{ij}$ jest kosztem wykonania zadania $i$ na maszynie $j$.
  

Funkcja celu minimalizuje koszty: $\min\sum_{ij}f_{ij} x_{ij}$

Przy ograniczeniach jak w zadaniu bin-packingu, przy czym o ile w zadaniu nie ma kosztów stałych powiązanych z wykorzystaniem maszyny to nie podrzebujemy zmiennej binarnej $y_j$:

$\begin{matrix} &&\sum_{ij} a_{ij} x_{ij}\leq p_j\;\;\;\forall j\in M,\\ && \sum_jx_{ij}=1\;\forall i\in N\\ && x_{ij} \subset \{0,1\},\; \forall i,j\end{matrix}$

Problemy lokalizacyjne/dystrybucyjne

Klasycznym rozszerzenime problemu przydziału zadań do procesorów jest dodatkowe uwzględnie stałego kosztu użycia procesora. Problem tego typu jest określany jako problem lokalizacyjny, gdyż ma naturalne odzwierciedlenie w sytuacji wyboru punktów obsługi (klientów, pacjentów, mieszkańców, etc.). Problem ten posłuży nam do omówienia sposobu implementacji modeli w środowisku IBM Ilog Cplex w kolejnych rozdziałach.

Oznaczenia dodatkowe:

• $c_{j}$ jest stałym kosztem wykorzystania zasobu $j$ (ustanowienia zasobu w lokalizacji  $j$)

Przy ograniczeniach jak w zadaniu bin-packingu:

$\begin{matrix} &&\sum_{ij} a_{ij} x_{ij}\leq p_jy_j\;\;\;\forall j\in M,\\ && \sum_jx_{ij}=1\;\forall i\in N\\ && x_{ij} \subset \{0,1\},\; \forall i,j\end{matrix}$