1. Klasy problemów i pakiety optymalizujące

1.2. Modele najważniejszych klas problemów

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}

Dodatkowe ograniczenie zapewnia, że każdy przedmiot i zostanie zapakowany do 1 pojemnika.

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)
Funkcja celu minimalizuje wszystkie koszty: \min\sum_jc_jy_j+\sum_{ij}f_{ij} x_{ij}

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}