Laboratorium optymalizacja kombinatoryczna, 2010/2011

1. Grupa dziekańska jest dzielona na 2-sobowe zespoły. Każdy zespół programuje rozwiązania dla jednego z 3 problemów.
2. Oceny określane są następująco. Ocena bazowa: 1 rozwiązanie - 3, ≥ 2 rozwiązania - 4, ≥ 3 rozwiązania - 5. Za braki w opisie i in. niedostatki rozwiązania będą odejmowane punkty od oceny bazowej.   Wyliczana jest średnia z ocen za 2 rozwiązania. Trzecie rozwiązanie dla chętnych (np. w celu podwyższenia średniej). Brak rozwiązania przyjmuję ocenę 2.0. Do oceny bazowej za pracę mogą być dodane punkty dla: a) 1.0 zespołu, który jako pierwszy zrobi >=2 metody, b) 0.5 zespołu, który jako drugi zrobi >=2 metody, c) za szczególnie ciekawe rozwiązania (b. szybkie, b. dobrej jakości, ciekawa idea metody).
3. Poszczególne rozwiązania muszą się istotnie różnić jakościowo. Na przykład, użycie heurystyki kolorującej wierzchołki grafu w kolejności wynikającej z czegoś jest tylko jedną metodą niezależnie od metody wyboru kolejności wierzchołków. Trzy różne metaheurystki (np. simulated annealing, tabu search i genetic algorithm) SĄ trzema różnymi metodami. Co do różnych wersji algorytmu BB, to istnienie różnic między implementacjami jest zależne od szczegółów, tj. metod cięcia i liczenia dolnych ograniczeń.
4. Wynik pracy trzeba przedstawić w działaniu na testach, objaśnić kod (także ustnie na zajęciach), sporządzić sprawozdanie.
5. Terminy zaliczenia.
   • Pierwsze rozwiązanie powinno być zaliczone do 20 XI 2010.
   • Drugie i ewentualne trzecie rozwiązanie do 17 XII 2010.
   Programy można też zaliczać wcześniej.
6. Każdy tydzień opóźnienia w zaliczeniu obniża ocenę o 0.5. Jeżeli praca była zwrócona do poprawki (tzn. musi być oceniona ponownie), to nową wersję trzeba dostarczyć w ciągu tygodnia od wysłania przeze mnie informacji o błędach. Przekroczenie tego terminu będzie obniżać ocenę bazową o 0.5 stopnia za każdy tydzień. Minimalna ocena pracy, która (w końcu) zostanie zaakceptowana wynosi 3.0.
7. Po zakończeniu sesji poprawkowej prace nie będą przyjmowane. Daty wpłynięcia sprawozdania, programu, wysłania informacji o błędach określa mój system poczty elektronicznej lub (w przypadku papieru) moment wręczenia sprawozdania (datę możemy wpisać razem ;-).
8. Jeżeli praca jest oddawana w kawałkach (program, tekst), to liczy się data oddania ostatniego kawałka. Sprawozdanie może być tworzone przyrostowo, tzn. sprawozdanie dla każdego kolejnego rozwiązania może zawierać poprzednie sprawozdanie jako podzbiór.
9. Język programowania C, C++, preferowany kompilator gcc, g++. Akceptowane będą tylko te programy, które uda się skompilować na zajęciach dostępnymi kompilatorami. Wszystkie programy muszą się dać wykonać z linii poleceń i z linii poleceń przyjmować parametry wykonania (nazwy plików, liczby, itp.).
10. Jakie metody wchodzą w rachubę: a) "szyte" heurystyki, b) BB, c) metaheurystyki, d) użycie zewnętrznych pakietów rozwiązujących części składowe problemu np. (sprowadzenie do) ILP (integer linear programming, np. lp_solve przykład knapsack, przykład max-sat). Pobieżny opis tych metod można znaleźć np. na foliach 60-96 na stronie z prowadzonego kiedyś przeze mnie wykładu. Ale uwaga! Nie wolno importować całych gotowych rozwiązań (cudzego kodu rozwiązującego całe postawione zadanie). Można korzystać z rozwiązań opisanych w książkach, wówczas trzeba podać źródło.
11. Proszę nie traktować mnie jako swojego korektora. Za przysłanie niedziałających programów i niekompletnych sprawozdań zwracam pracę do poprawy i obniżam ocenę o 0.5, za każdą taką iterację. Programy można testować i zgłaszać dowolną liczbę razy na zajęciach.

Sprawozdanie powinno zawierać:

1. Metadane nt. autorów i projektu: imiona, nazwiska, nry indeksów, email do kontaktu, datę oddania sprawozdania (najlepiej wpisać w momencie wręczenia mi), nazwę zadania i nazwę rozwiązania (np. Kolorowanie, algorytm zachłanny).
2. Opis metody rozwiązania problemu. Trzeba opisać ideę/zasadę na której opiera się algorytm. Można tu włączyć istotne wyjątki z kodu.
3. Badania efektywnościowe, tzn. wyniki testów czasu działania metody i jakości uzyskanych rozwiązań w zależności od trudności problemu. Przykładowe instancje testowe zostaną wskazane przy każdym temacie. Przeprowadzenie obszerniejszych testów będzie zaletą pracy.
4. Wnioski. Ciekawe spostrzeżenia nt. działania algorytmu(-ów), trudności instancji itp. Np. można porównać swoje trzy metody na wykresie jakość/czas i stwierdzić, która dominuje nad którą, a które metody są niezdominowane.
5. Załącznik w postaci kodu programu proszę przysłać pocztą (może być spakowany jakimś typownym programem, np. w formacie zip, tgz). Program będzie testowany pod kątem poprawności generowanych rozwiązań.
6. W emailu i/lub sprawozdaniu proszę napisać jak skompilować Państwa program i jak go uruchomić.

• Szeregowanie parallel tasks (zadań równoległych) wg danych z parallel workload archives. Znaleźć najkrótsze uszeregowanie dla zadanego zestawu zadań. Program ma wczytywać dane w tekstowym formacie SWF. Uwzględnić: p_j (czas trwania zadania), r_j (moment gotowości/przybycia), size_j (liczbę żądanych/przydzielonych procesorów). Określają to kolumny 1, 2, 4, 5 w formacie SWF. Zadania są niepodzielne.
  Dodatkowe założenia i zastrzeżenia:
  1. Wyniki wyprowadzić w postaci listy linii opisujących uszeregowanie każdego z zadań w formacie:
     nr_zadania momentstartu momentzakończenia numeryprzydzielonychprocesorów \n
     separatorem w linii mają być spacje. Proszę nie umieszczać żadnych innych wyrazów w linii opisującej pojedyncze zadanie.
  2. Proszę zauważyć, że
     - w niektórych plikach np. DAS2-fs0-2003-1.swf.gz niektóre zadania mają niekompletne dane,
     - w pliku NASA-iPSC-1993-2.1-cln.swf.gz są zadania o zerowym czasie trwania.
     Takie zadania trzeba zignorować (przeskoczyć). Nie można jednak zmieniać identyfikatorów zadań w wynikowym pliku. Inaczej, nie można ich przenumerowywać, aby były po kolei w pliku wynikowym. Jeszcze innymi słowy, identyfikatory zignorowanych zadań z pliku wejściowego nie pojawią się w pliku wyjściowym.
     
  3. Przyjąć, że zawsze MaxNodes=MaxProcs oraz zawsze MaxJobs=MaxRecords.
     
  4. Umożliwić konstrukcję uszeregowania tylko dla podzbioru N pierwszych zadań z pliku SWF, gdzie N może być zadane w czasie uruchomienia programu.
     
  5. Kolejność zadań w wejściowym pliku SWF nie musi być zgodna z r_j.
     
  6. Proszę zdecydować, czy przydziały procesorów są przyległe (contiguous), czy nieprzyległe (noncontiguous). W przydziale przyległym należy zadaniu przydzielić size_j kolejnych numerów procesorów, np. dla sizej_j=5: 3,4,5,6,7. W przydziale nieprzyległym procesory mogą mieć numery, które nie są kolejne np. 2,3,7,19,43. Szeregowanie z nieprzyległymi przydziałami procesorów wydaje się prostsze. Można więc ograniczyć się do niego. Jeżeli jednak ktoś zdecyduje inaczej, to proszę to wyraźnie zaznaczyć w sprawozdaniu.
     
  7. W pliku SWF pominąć zadania, dla których nie wszystkie parametery są znane.
     
  Przykładowe dane testowe (tylko do sprawdzania poprawności działania programu): test1, test2, test3.
  Instancje do testów efektywnościowych: LANL-CM5-1994-3.1-cln.swf.gz, SDSC-SP2-1998-3.1-cln.swf.gz, DAS2-fs0-2003-1.swf.gz. Dla każdego pliku należy rozwiązać pierwsze 1, 2, 5, 10, 20, 50, 100, 200 .... zadań. Limit zadań, które należy osiągnąć powinien wynikać z limitu czasu. Patrz uwagi o implementacji.
  Sprawdzarka windows konsola różne biblioteki dll do niej.
  
  
• Job-shop. Na czym polega problem szeregowania w job-shopie zostało naszkicowane na foliach 101, 102 wykładu, który kiedyś prowadziłem. Należy znaleźć dopuszczalne uszeregowanie o minimalnej długości.
  Przykładowe instancje testowe są na str. http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/jobshop1.txt
  oraz (w innym formacie) na str. (instancje Taillarda): http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html . Opis formatu danych znajduje się w samych plikach.
  Dodatkowe założenia i zastrzeżenia:
  1. Rozwiązanie podać w postaci: długość uszeregowania \n
     momenty_rozpoczęcia_wykonywania_kolejnych_operacji_zadania1 \n
     momenty_rozpoczęcia_wykonywania_kolejnych_operacji_zadania2 \n
     momenty_rozpoczęcia_wykonywania_kolejnych_operacji_zadania3 \n ...
     momenty_rozpoczęcia_wykonywania_kolejnych_operacji_ostatniego_zadania \n
     gdzie "\n" oznacza znak nowej linii. Innymi słowy, liczba o współrzędnych wiersz "i", kolumna "j" oznacza moment rozpoczęcia wykonywania operacji "j" zadania "i".
     
  2. programy powinny czytać oba typy instancji (mogą zostać przygotowane 2 wersje programu),
     
  3. programy muszą umieć rozwiązać instancje tylko dla pewnej zadanej liczby pierwszych zadań, aby można było sporządzić zależność czasu wykonania od liczby zadań,
     
  4. zakładamy, że dopuszczalny jest czas wykonania 0 (to oznacza że operację o czasie trwania 0 można przeskoczyć nie przydzielając jej do niczego) oraz powrót zadania na odwiedzoną wcześniej maszynę.
     
  Przykładowe dane testowe (tylko do sprawdzania poprawności działania programu, w formacie J.E.Beasleya (orlib)): fs1, fs2, fs3. Pocięte pliki z instancjami orlib i Taillarda do testów js1.ZIP.
  Instancje do testów efektywnościowych. W sprawozdaniu muszą się znaleźć pomiary czasu i jakości dla instancji: ta20 do ta25 oraz czasu dla zwiększającej się od 1 do 20 liczby zadań dla instancji ta25. Większa liczba testów będzie działać na korzyść przy ocenie pracy.
  Sprawdzarka dla instancji orlib (beasley), Windows konsola.
  
  
• Największa klika w grafie (max clique). Znaleźć największą klikę w grafie. Przykładowe instancje testowe można pobrać z:
  • ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique/
  • http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm
  • także http://mat.gsia.cmu.edu/COLOR/instances.html.
  Opis formatu w pliku Postscript.
  Translatory z binarnego formatu .b na ASCII znajdują się tutaj.
  Dodatkowe założenia i zastrzeżenia:
  1. Rozwiązanie podać w postaci:
     rozmiar kilki \n
     nr_1._wierzchołka_w_klice nr_2._wierzchołka_w_klice nr_3._wierzchołka_w_klice,...\n,
     gdzie "\n" oznacza znak nowej linii, separatorem między numerami powinna być spacja lub inna "whitespace".
     
  2. instancje do testów będą podawane w postaci tekstowej (.clq),
  3. w rozwiązaniach wierzchołki numerujemy od 1 tak jak w plikach danych .col (a nie od 0 jak w plikach z wynikami .sol które są w ww. repozytoriach sieciowych),
  4. plik musi być prawidłowo zamknięty tj. mieć za ostatnią liczbą ^Z,
  5. nie można przyjmować ograniczenia na rozmiar problemu mniejszego niż w przykładowych instancjach,
  6. pliki z danymi DSJC*.col i DSJR*.col są niekompatybilne z powyższym opisem formatu danych, bo każda krawędź liczy się podwójnie, tzn. liczba linii z krawędziami jest tylko połową tego co zadeklarowano w linii "p edge ...".
  Przykładowe dane testowe (tylko do sprawdzania poprawności działania programu): clq-test1.clq, clq-test2.clq, clq-test3.clq.
  Instancje do testów efektywnościowych. W sprawozdaniu muszą się znaleźć pomiary czasu i jakości dla instancji: johnson8-2-4.clq, c-fat200-1.clq, p_hat300-1.clq, johnson32-2-4.clq, C2000.5.clq. Większa liczba testów będzie działać na korzyść przy ocenie pracy.
  Sprawdzarka Windows konsola.

1. Jak określić kiedy metaheurystyka ma się zatrzymać? Są dwa wyjścia.
   a) Jeżeli algorytm jest zdefiniowany tak, że znamy optymalną wartość funkcji celu, to algorytm może zatrzymać się po jej osiągnięciu.
   b) Jeżeli optimum nie jest znane, to trzeba zatrzymać się po pewnym czasie. Ze względów praktycznych algorytmy zachłanne nie powinny działać dłużej niż kilka sekund, a algorytmy takie jak BB, GA, Tabu nie powinny działać dłużej niż kilka (góra kilkanaście) minut, aby możliwa była weryfikacja ich działania na zajęciach. Trzeba tak dobrać liczbę iteracji, aby ten czas nie był przekraczany. Przyjmijmy, że limit czasu dla testów do sprawozdania to 10 minut. Do weryfikacji poprawności rozwiązania na zajęciach przyjmijmy limit 5 minut.
   
2. Strojenie (tuning) metaheurystyk.
   Jeżeli ktoś z Państwa implementuje jakąś metaheurystykę, to proszę zwróćić uwagę, że metaheurystyki zwykle mają szereg parametrów sterujących ich działaniem. Na przykład: tabu search - długość listy tabu, rozmiar przeszukiwanego sąsidztwa, genetic search - rozmiar populacji, prawdopodobieństwo mutacji, simulated annealing - sposób zmieniania temperatury, wszystkie takie algorytmy - warunek stopu (np. liczba iteracji, czas działania do zatrzymania). Te wszystkie parametry trzeba sensownie dobrać. Zwykle wymaga to testowania i eksperymentalnego dobierania. Wyniki takich testów trzeba opisać i objaśnić w sprawozdaniu. Zwykle wiązanie ad hoc tych "magicznych" liczb ze strukturą instancji nie jest dobrym pomysłem. Brak strojenia oznacza, że metaheurystka nie została prawidłowo użyta.

1. Znalazłeś/Znalazłaś błąd? Informuj!
2. Za znalezienie błędu (wykazanie błędnego działania) sprawdzarki +1 stopień do oceny końcowej.

MD.Ostatnia zmiana :