Podręcznik

Gwarancja optymalności planów i decyzji jest możliwa tylko wtedy, gdy problemy decyzyjne są  rozwiązywane przy użyciu odpowiednich algorytmów. Wykorzystanie algorytmów optymalizacji, dostarczanych przez pakiety optymalizacyjne - tzw. solwery, daje pewność optymalności wyniku, ale wymaga odpowiedniego opisania tych problemów. Modelowanie matematyczne, wprowadzone we wcześniejszych rozdziałach, to sposób na opis problemów, który umożliwia zastosowanie efektywnych solwerów do ich rozwiązania. Znalezienie rozwiązania dla trudnych problemów decyzyjnych przy użyciu solwerów optymalizacji obejmuje zatem następujące działania, które można pogrupować w powiązanych ze sobą obszarach:

• model: formułowanie problemu w postaci matematycznej zadania programowania liniowego/mieszanego/całkowitoliczbowego/etc;
• dane: przygotowanie wartości liczbowych dla zbiorów i parametrów zdefiniowanych w modelu;

• solwer: 

  • implementacja modelu, przygotowanie struktur danych, wczytanie danych i  wygenerowanie konkretnej instancji problemu do rozwiązania;
  • wywołanie programu, który obliczy najlepsze wartości zmiennych decyzyjnych i kryteriów dla wygenerowanej instancji problemu;
• wynik: przeanalizowanie rezultatów, wdrożenie planu lub poprawa założeń/ powrót do wcześniejszych kroków.

Gotowe solwery na wejściu oczekują modelu problemu w określonej strukturze, a do rozwiązywania wykorzystują gotowe, zaimplementowane algorytmy. Dobre solwery powinny wspierać separację danych od modelu, ale przede wszystkim oczekuje się od nich efektywności w rozwiązywaniu. Zwróćmy tu uwagę, że jakość/optymalność wyniku może zależeć od użytego solwera, ale też od sformułowania modelu -- użycie odpowiednich technik matematycznych może też mieć wpływ na efektywność rozwiązywania. 

Podstawowym algorytmem dostępnym we wszystkich solwerach, również bezpłatnych, jest algorytm sympleksowy przeznaczony do rozwiązywania zadań programowania liniowego PL. Często występuje w wielu wersjach, np.: prymalnej, zrewidowanej, sieciowej, dualnej, w różnych modyfikacjach dualno-prymalnych, etc.. Solwery open-source oferujące efektywne algorytmy do zadań PL to m.in GLPK, lpsolve, GLOP (Google), OpenSolver (dodatek do arkuszy kalkulacyjnych), COIN-OR Optimization Suite, i wiele innych. 

Solwery komercyjne, często udostępniane w ramach zintegrowanych pakietów optymalizacji stosuje się przede wszystkim do zadań ze zmiennymi binarnymi i całkowitoliczbowymi (MILP), jak też do wielkoskalowych zadań PL. Algorytmy, które są zaimplementowane w solwerach komercyjnych bazują na wariantach metody podziału i oszacowań, a ich siła leży w złożonych metodach tzw. presolvingu. Najlepsze popularne solwery to m.in.: IBM Ilog Cplex, Gurobi, Baron, COPT, minos...

Solwery są najczęściej wzbogacone o narzędzia komunikacji z użytkownikiem, w różnych trybach pracy:

• poprzez API wystawiane do popularnych języków programowania (C, C++, Python, Java, C\#, Matlab, R, Pyomo, ...)
• udostępniając dedykowane biblioteki modelowania, np.: PuLP (Python), COPT (C++), ...
• w najprostszym przypadku poprzez interaktywne komunikaty z linii poleceń
• poprzez zintegrowane środowiska, stosujące własne języki modelowania, np.: Ampl, Aimms, Matlab, Ilog CPLEX Studio, Gams, Pyomo, ...

W tym kursie proponujemy implementację modeli w środowisku modelowania ILOG CPLEX Optimization Studio, udostępnianym bezpłatnie w ramach programu Inicjatywy Akademickiej (Academic Initiative) IBM, jako w pełni funkcjonalna wersja, bez ograniczeń rozmiaru problemu. Dostęp do aktualnej wersji można uzyskać poprzez stronę http://ibm.biz/CPLEXonAI, po kliknięciu na 'Software'. Poprzez kartę ILOG CPLEX Optimization Studio zostaniesz przekierowany/a do rejestracji. Po zaakceptowaniu rejestracji będzie możliwe pobranie oprogramowania.

Na stronie IBM ILOG CPLEX Optimization Studio można znaleźć wiele materiałów wspomagających i szkoleniowych oferowanych bezpłatnie, w tym dokumentację z odnośnikami do samouczków, przykładów, itd. W tym materiale przedstawimy sformułowanie modelu i jego implementację w języku OPL, analizując przykładowy projekt.