1. Klasy problemów i pakiety optymalizujące

1.5. Implementacja modelu

OPL to język modelowania problemów optymalizacyjnych, która ułatwia implementację modeli matematycznych w pakiecie ILOG CPLEX Optimization Studio. W tym rozdziale podajemy najważniejsze informacje, podczas pracy warto korzystać z udostępnionych narzędzi pomocy, czyli poprzez ”Help->Search”, np. dla przejrzenia słów kluczowych należy wpisać 'OPLkeywords', a do wglądu w dostępne funkcje należy wpisać 'OPLfunctions'.

Projekt

W Cplex Studio operuje się na projektach, odpowiadających konkretnym problemom. Każdy projekt musi zawierać przynajmniej jeden plik z modelem, jak też przynajmniej jedną specyfikację konfiguracji. Elementów tych może być więcej w projekcie, a formalnie można w nim definiować następujące składowe:

  • plik z modelem ( .mod)
  • plik z danymi ( .dat)
  • konfiguracja uruchomienia "run configuration" wiążąca model z danymi
  • plik z ustawieniami (.ops) 

Wbudowane typy danych

Opl posługuje się standardowymi podstawowymi typami danych, które mogą być typu:

  • int
  • float
  • string (napisy "w cudzysłowie")
Ponadto, można używać złożonych struktur danych, zbudowanych na typach podstawowych, oraz na innych strukturach.

Struktury danych

  • zbiory (set): nawiasy klamrowe, w nich typ elementów zbioru np. {string} Warehouses = ...;
  • tablice (array) 1- i wielowymiarowe: nawiasy kwadratowe, w nich rozmiar tablicy lub po prostu nazwy zbiorów - dla elementów tych zbiorów przechowywane są wartości w tablicy; typ wartości w tablicy trzeba podać, np. int SupplyCost[Stores][Warehouses] = ...;
  • skalary: po prostu wartości danego typu wbudowanego, np. int Fixed = ...;
  • zakres range: liczby całkowite (int) w pewnym zakresie podanym w definicji typu, np. range Stores = 0..NbStores-1;
  • krotka tuple: odpowiednik wiersza tabeli, czyli powiązanie kilku typów danych ze sobą, np. tuple daneProduktu {string nazwa; int minZapas; float zapotrzebowanie}
Krotki mogą zawierać inne struktury, np. zbiory, tablice, krotki. Jednak najczęściej spotykane są  struktury typu zbiory i tablice, których elementami są krotki. Mogą też oczywiście występować tablice zbiorów, itd.

Typy zmiennych decyzyjnych

Dla zmiennych decyzyjnych, które są deklarowane przy użyciu słowo kluczowe dvar (decision variable) dostępne są wbudowane typy liczbowe, jak też dodatkowo typ binarny, czyli zmienna 0-1. Pogrubieniem zaznaczyliśmy zmienne całkowitoliczbowe, których użycie w modelu powoduje, że problem staje się zadniem optymalizacji dyskretnej:

  • int
  • float
  • boolean

Projekt warehouse

Implementacja problemu przedstawionego w poprzednim rozdziale jest już przygotowana w CPLEX Studio, należy ją otworzyć wchodząc poprzez menu 'File > New > Example menu' i wpisać nazwę 'warehouse'.

Widok okienka poniżej pokazuje katalog otwrtych projektów, w tym interesujący nas projekt 'warehouse', w którym są cztery pliki z modelami, cztery instancje konfiguracji uruchomienia oraz jeden plik z danymi. Uwaga - model, który przedstawiliśmy w poprzednim rozdziale jest zaimplementowany w pliku 'warehouse.mod'.
widok katalogu projektów OPL

Rozwiązanie problemu

Aby rozwiązać problem musimy wygenerować jego konkretną instancję, czyli zapis modelu dla konkretnych danych  - temu służy konfiguracja uruchomienia.  Dla rozważanego przykładu przeznaczona jest tzw. konfiguracja domyślna, czyli 'Basic Configuration'. Gdy ją rozwiniemy, widzimy, że przekierowuje ona do naszego pliku z modelem, oraz pliku z danymi. W projekcie można mieć dowolną liczbę konfiguracji, w każdej z nich można mieć różne zestawy model+dane (+ustawienia solwera).
Rozwiązanie problemu polega na uruchomieniu konfiguracji, co wykonujemy np. klikając prawym przyciskiem myszki na wybraną konfigurację i wybierając 'Run this'. 
  • Jeśli model zawiera błędy, to są one wyświetlane na karcie 'Problems'. Warto zwrócić uwagę, że IDE nie uruchamia w takiej sytuacji solwera, ponieważ najpierw należy  poprawić błędy - kierując się opisem błędu i ew. poszukując dalszych wskazówek, np. na forum ibm.com;
  • Gdy składnia modelu jest poprawna, IDE zaczyna rozwiązywać problem.  Aktualizowane są wtedy zakładki obszaru 'Output Area', w szczególności można podejrzeć przebieg procesu rozwiązywania w 'Status Bar', a wyniki w zakładce 'Solutions'. 
  • Może się zdarzyć, że składniowo poprawny model zawiera błędy logiczne, lub występuje niespójność w danych. W takiej sytuacji solwer cplex wskazuje, że rozwiązanie jest sprzeczne, niedopuszczalne lub że problem jest nieograniczony (Infeasible, Unbounded). Dodatkowo, udostępniane są wspomagające narzędzia:
    • Conflict refinement: w zakładce 'Conflicts' znajdziemy podpowiedź, które ograniczenia są wzajemnie sprzeczne, nie mogą być spełnione jednocześnie;
    • Minimal relaxation: jeśli nie jest możliwe uzyskanie rozwiązania, to cplex stara się wyznaczyć rozwiązanie zadania zrelaksowanego (wynikowe okienko wyświetla wtedy Relaxed solution, przyjmując jak najmniejsze zmiany w definicji problemu) a wynik można obejrzeć w zakładce 'Relaxations'. 
Wartości zmiennych decyzyjnych (jak i parametrów), można też obejrzeć w centralnym obszarze IDE, po kliknięciu na strzałkę (lub dwukrotnym kliknięciu) przy konkretnym elemencie w okienku 'Problem browser' - przykładowy widok na rysunku poniżej pokazuje jak wyświetlić wartości zmiennych 'Open', czyli wybór lokalizacji, w których należy otworzyć magazyny. Te same wartości są też widoczne w zakładce 'Solutions' widocznej w dolnej części.

Ustawienia solwera

Wybór algorytmu oraz specyficznych dla niego parametrów przeprowadzamy w pliku .ops. W standardowym wykorzystaniu solwera nie ma potrzeby zmieniać domyślych ustawień, jednak w bardziej wymagających przypadkach wiedza o takich możliwościach bywa przydatna. Najłatwiej będzie zaobserwować zmiany w pracy solwera, gdy prześledzimy szczegóły rozwiązywania bardzo dużego problemu, zdefiniowanego w konfiguracji scalableWarehouse. Jest to wersja modelu lokalizacji magazynów, która  nie ma powiązanego pliku danych. Liczby magazynów i sklepów oraz koszty są deklarowane w pliku modelu z danymi wewnętrznymi. Tym samym, problem można skalować poprzez zmianę liczby magazynów i sklepów - w przykładzie możemy ustawić np. 1000 sklepów i 100 lokalizacji magazynów. W konfiguracji przebiegu scalableWarehouse proponujemy zdefiniować plik ustawienia.ops (Prawy przycisk myszy New->Settings) i przeciągnąć go do konfiguracji.

Po otwarciu ustawienia.ops ustawmy MIP gap tolerancję względną na 1%:

  1. Klikamy na Mixed Integer Programming->Tolerances
  2. Wpisujemy wartość 0.01 dla Relative MIP gap tolerance Zmieniony parametr widać poprzez pogrubienie. 
  3. Rozwiąż problem i porównaj czas i wyniki z modelem pierwotnym.

Poniższy rysunek pokazuje odpowiedni widok.



Uwaga. Ogólne wskazówki dla poprawy obliczania przy wykorzystaniu Cplexa, w tym dla ustawiania parametrów obliczania znaleźć można np. w artykule Practical guidelines for solving difficult mixed integer linear programs. W skrócie, do najważniejszych technik należy:

  • wykonanie preprocessingu,
  • dostarczenie dobrego rozwiązania dopuszczalnego (skorzystanie z opcji 'cplex mip start'),
  • dopasowanie dokładności rozwiązania optymalnego (parametr 'mipgap'),
  • skorzystanie z narzędzia 'tunning tool',
  • dodanie własnych odcięć, przeformułowanie modelu.

Wymienione techniki są zaawansowanymi koncepcjami, wymagającymi m.in. znajomości wybranych algorytmów optymalizacji. Część z nich, np. strategie przeszukiwań, czy techniki odcięć omawiamy w dalszych rozdziałach tego kursu.