Zaliczenie 'Optymalizacji'

Kolokwium

Przez pierwsze 30 minut zajęć będzie miało miejsce kolokwium. Do zdobycia będzie 14 punktów.

Zagadnienia

Wszystko przerabiane na zajęciach, w szczególności:

• Programowanie matematyczne i liniowe
  • Zapisywanie problemu w postaci zadania programowania liniowego.
  • Wskazywanie rozwiązań dopuszczalnych i optymalnych
  • Różnice między programowaniem liniowym, całkowitoliczbowym i binarnym
• Optymalizacja lokalna: algorytmy Greedy i Steepest
  • Umiejętność określania, które punkty należą do sąsiedztwa.
  • Wskazywania sąsiada, którego wybierze dany algorytm.
• Algorytmy ewolucyjne

Projekt z modelowania

Na zajęciach poszczególne grupy prezentują sposób rozwiązania wybranego problemu za pomocą heurystyki oraz poznanych algorytmów optymalizacji (algorytmu pełnego przeszukiwania, algorytmu losowego, programowania matematycznego, branch and bound, optymalizacji lokalnej).

Przed przystąpieniem do modelowania przypomnij sobie

• problemy: komiwojażera, plecakowy, QAP (kwadratowe zagadnienie przydziału)
• algorytmy heurystyczne — konstruujące
• poznane dotąd algorytmy przeszukiwania lokalnego oraz: branch and bound
• sąsiedztwo w przeszukiwaniu lokalnym — rozmiar i sposób określania, czy są sąsiedzi, jak się ich wyznacza (co musi zostać spełnione, żeby znależć rozwiązanie sąsiednie i przejść do niego)

Materiały

• wykład i poprzednie zajęcia
• o branch and bound w: Wykład BB_DP.pdf

Projekty

1. Proszę zapoznać się z zadaniami (dostępnymi tutaj) dotyczącymi różnych sposobów poszukiwania optymalnego rozwiązania
2. Celem zadania jest:
   • Zamodelowanie zadania jako problemu optymalizacji, tak, żeby można było rozwiązać je przy pomocy poznanych algorytmów.
   • Należy określić:
     • model rozwiązania — czym jest rozwiązanie tego problemu?
     • próba oszacowania: ile jest wszystkich rozwiązań?
     • funkcję oceny rozwiązania – jak je ocenić liczbowo? (albo określić, czy jedno rozwiązanie jest lepsze od drugiego)
     • czy ocena rozwiązania jest jednokryterialna (jedna liczba), czy wielokryterialna (wiele liczb)?
     • jak zbudować losowe rozwiązanie?
     • jak heurystycznie zbudować niezłe rozwiązanie?
     • relację sąsiedztwa – jak wyznaczyć zbiór rozwiązań podobnych do danego tak, żeby można było użyć lokalnego przeszukiwania?
     • próba opisu matematycznego: czy da się ten problem zapisać w postaci matematycznej (dla solvera)?
     • próba przystosowania do algorytmu Branch and Bound: jak zbudować drzewo i zdefiniować ograniczenie?
     • (dla chętnych) pomysł na innowacyjną aplikację rozwiązującą wybrany problem
3. Zadanie należy wykonać w 2-3 osobowych grupach wyłonionych na zajęciach.
4. Każda z grup ma opracować jedno zadanie.
5. Za zadanie jest do zdobycia 8 punktów.
6. Przy tworzeniu prezentacji możesz skorzystać z szablonu.