Projekt optymalizacja kombinatoryczna

1. Grupa dziekańska jest dzielona na 2-osobowe zespoły. Każdy zespół programuje przynajmniej 2 rozwiązania dla jednego z 3 problemów. Rozwiązania dotyczą tego samego problemu (nie zmieniamy problemu w kolejnych rozwiązaniach). Dwa rozwiązania są obowiązkowe, trzecie rozwiązanie dla chętnych (np. w celu podwyższenia średniej). Trzecie rozwiązanie może też zostać przydzielone jako dodatkowa praca za powtarzające się niepoprawne rozwiązania.
2. Oceny określane są następująco. Wyliczana jest średnia z ocen za rozwiązania. Do oceny średniej za programy mogą być dodane punkty:
   • +0.5 za najlepsze jakościowo rozwiązanie - dodawane na końcu semestru,
   • +0.5 dla zespołu, który jako pierwszy zrobi jedną metodę,
   • +0.25 dla zespołu, który jako drugi zrobi jedną metodę,
   • +1 za znalezienie błędu w sprawdzarce.
   • za szczególnie ciekawe rozwiązania (b. szybkie, b. dobrej jakości, ciekawa idea metody, użycie LP/lp_solve/Gurobi/CPLEXa),
   Wszelkie ekstra-punkty i inne "bonusy" są doliczane tylko osobom, które rozliczyły się w terminie ze wszystkich zadań.
3. Jeżeli przygotowane zostaną 3 rozwiązania (tzn. trzy programy), to do średniej brane są 2 najlepsze oceny.
4. 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 sposobu wyboru kolejności wierzchołków. Algorytm zachłanny i wyprowadzona z niego metoda GRASP również są jedną podobną metodą. Trzy różne metaheurystyki (np. simulated annealing, tabu search i genetic algorithm) SĄ trzema różnymi metodami. Co do różnych wersji algorytmu BB (branch and bound), to istnienie różnic między implementacjami jest zależne od szczegółów, tj. metod cięcia i liczenia dolnych ograniczeń. W razie wątpliwości proszę pytać.
5. Język programowania C, C++, kompilator gcc, g++ dla środowiska Linux, Cygwin (z tego wynika, że nie można użyć bibliotek conio.h, windows.h stosowanych np. przez mingw, dev-cpp, code::blocks). Akceptowane będą tylko te programy, które uda się skompilować na zajęciach dostępnymi kompilatorami. Tekst programu musi być w kodzie ASCII (niektóre edytory tekstowe (Linux,Mac) zostawiają niewidoczne znaki nawet w plikach tekstowych. Tego ma nie być). Dopuszczalne jest użycie make, inne narzędzia zarządzania procesem kompilacji programu nie są akceptowane.
6. Wszystkie programy muszą się dać wykonać z linii poleceń i z linii poleceń przyjmować parametry wykonania (nazwy plików, liczby, przełączniki, itp.).
7. Proszę aby programy pobierały dane z bieżącego katalogu i zapisywały wyniki albo na konsolę, albo do pliku o jednej i tej samej nazwie. Proszę NIE tworzyć własnych systemów nazw i katalogów dla plików wynikowych, nie przetwarzać więcej niż jednego pliku na raz. To ułatwia mi wsadowe testowanie Państwa programów.
8. Jakie metody wchodzą w rachubę:
   a) "szyte" algorytmy zachłanne,
   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.
9. Rada: łatwiej zacząć od prostej metody, np. to może być szybki algorytm zachłanny albo GRASP.
10. 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, artykułach i w sieci, wówczas w sprawozdaniu trzeba podać źródło. Np. w ten sposób:
    Literatura
    Autor, tytuł, źródło, rok publikacji (ewent. czas dostępu dla str. www).
11. Limit czasu. Aby możliwa była weryfikacja działania programów na zajęciach i sprawdzarką, muszą się one wykonywać w ograniczonym czasie. Przyjmujemy, że limit czasu to 5 minut na instancję. Tzn. tego limitu będę używać na etapie weryfikacji kodu w trybie off-line. Do weryfikacji poprawności rozwiązania na zajęciach przyjmijmy limit 3 minut. Programy muszą się same zatrzymać w tym czasie i podać poprawne rozwiązanie. Trzeba tak dobrać liczbę iteracji, albo śledzić upływ czasu, aby limit nie był przekraczany. Proszę zwrócić uwagę, że programy będą wykonywane na komputerach o różnych prędkościach i nawet na najwolniejszym limit czasu musi być przestrzegany.
12. Wymóg jakościowy. Druga metoda po czasie 5 minut musi dawać lepsze rozwiązanie niż pierwsza.
13. Aby rozwiązanie zostało przyjęte należy:
    • na zajęciach pokazać program w działaniu na testach,
    • ustnie objaśnić zasadę działania kodu na zajęciach,
    • przysłać emailem kod do testów sprawdzarką,
    • sporządzić i oddać mi sprawozdanie.
14. Terminy zaliczenia rozwiązań.
    • Pierwsze rozwiązanie powinno być zaliczone do 22 XI 2024.
    • Drugie rozwiązanie do 13 XII 2024.
    • Ewentualne trzecie rozwiązanie do 17 I 2025.
    Do tych terminów powinny być zaliczone wszystkie powyższe kroki weryfikujące rozwiązanie. Wszystkie elementy materialne potrzebne do zaliczenia (sprawozdanie i kod) muszą do mnie dotrzeć najpóźniej w tych terminach, nawet jeżeli na zajęciach (z powodów od Państwa niezależnych) nie udało się sprawdzić pracy. Dopiero wykonanie wszystkich kroków i dostarczenie sprawozdania i kodu wyznacza termin przyjęcia rozwiązania. Termin dotyczy obu grup (niezależnie od parzystości tygodnia). Wszystko można też zaliczać wcześniej.
15. 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ć ponownie oceniona), 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ń. Czas oczekiwania na moją odpowiedź nie liczy się jako opóźnienie (czas upływający po mojej stronie nie obniża oceny). Minimalna ocena pracy, która (w końcu) zostanie zaakceptowana wynosi 3.0.
16. 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ę na nim możemy wpisać razem ;-). Jako ostateczna data wpłynięcia rozwiązania brany jest zawsze termin dostarczenia ostatniego elementu weryfikacji rozwiązania. Innymi słowy, jeżeli praca jest oddawana w kawałkach (program, tekst, rozmowa na zajęciach), to liczy się data oddania ostatniego kawałka.
17. Jeżeli rozwiązanie zostanie zwrócone do poprawy więcej niż 4 razy, liczba programów do przedstawienia zostaje zwiększona do 3.
18. Trzeba dostarczyć co najmniej 2 działające rozwiązania. Nie ma możliwości rezygnacji z jednego programu z oceną 2.0.
19. Po zakończeniu semestru nowe prace nie będą przyjmowane. W sesji poprawkowej przyjmowane są tylko poprawki do wcześniej przysłanych projektów. Po zakończeniu sesji żadne prace nie będą przyjmowane.
20. Tekst sprawozdania może być tworzony przyrostowo, tzn. sprawozdanie dla kolejnego rozwiązania może zawierać elementy poprzedniego sprawozdania jako podzbiór. Umożliwia to porównanie jakości i szybkości dwóch rozwiązań.
21. Proszę nie traktować mnie jako swojego korektora. Za przysłanie niedziałających programów, niekompletnych sprawozdań i z błędami zwracam pracę do poprawy i obniżam ocenę o 0.5 stopnia (za każdy zwrot). Więcej niż 4 zwroty, to dodatkowa praca (3-cie rozwiązanie).
22. Programy można testować i zgłaszać dowolną liczbę razy na zajęciach bez wpływu na ocenę.

Format sprawozdania jest dowolny, powinno jednak zawierać:

1. Metadane nt. autorów i projektu: imiona, nazwiska, numery 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 rozmiaru problemu. Przykładowe instancje testowe zostaną wskazane przy każdym temacie. Przeprowadzenie obszerniejszych testów będzie zaletą pracy. Limit czasu działania w testach opisanych w sprawozdaniu może przekraczać 5 min.
4. Jeżeli algorytm jest probabilistyczny (in. randomizowany, in. korzysta z losowości), to trzeba pokazać rozrzut jakości wyników.
5. W wynikach pomiarów czasu wykonania należy pokazać rozrzut (np. odchylenie standardowe, kwartyle, minimum-maksimum, itp.)
6. Jeżeli algorytm ma jakieś parametry kontrolne, które należy stroić (tuning) to trzeba udokumentować proces wyboru tych parametrów.
7. Przy drugim rozwiązaniu przeprowadzić testy określające, którą z dwóch metod należy uruchomić dla zadanego rozmiaru problemu i limitu czasu wykonania. Można to zrobić badając jakość rozwiązań dla różnych rozmiarów problemu i limitów czasu.
8. Wnioski. Spostrzeżenia nt. działania algorytmu(-ów), trudności instancji itp. Np. można: wskazać której metody użyć dla pewnego rozmiaru instancji i ograniczeń czasowych; porównać swoje dwie/trzy metody na wykresie jakość/czas i stwierdzić, która dominuje nad którą i dlaczego.
9. Załącznik w postaci kodu programu proszę przysłać pocztą (może być spakowany jakimś typowym programem, np. w formacie zip,tgz,rar,7z). Program będzie testowany pod kątem poprawności generowanych rozwiązań.
10. W emailu i/lub sprawozdaniu proszę napisać jak skompilować Państwa program i jak go uruchomić.
11. Proszę przesyłać tylko kod źródłowy (i ewentualnie makefile). Proszę nie przesyłać zestawów danych, plików repozytoriów (np. .git), plików wykonywalnych (.out), pośrednich (.o), .sh, .xml, .cbp, etc. etc.

• Niepotrzebne wygładzanie linii na wykresach czasu wykonania lub jakości rozwiązań. Zwykle na tych wykresach nie ma nic pomiędzy punktami dla których dokonano pomiaru. Dodatkowo np. liczby zadań w problemach A (Parallel Tasks) i B (Job-Shop), lub liczby klientów w zadaniu C (CVRPTW) są dyskretne. Skąd więc możemy wiedzieć jak te zależności się kształtują pomiędzy tymi liczbami? Albo między tymi punktami, dla których dokonano pomiaru/rejestracji? Puryści matematyczni zażądaliby wykresów słupkowych. Ja przeboleję wykres liniowy, ale wygładzanie linii między wartościami dyskretnymi, to przesada i za to obniżam ocenę.
• Dokładność pomiaru czasu. Proszę zwrócić uwagę, że rejestrując czas trwania algorytmu, nie dokonujemy tego z nieograniczoną dokładnością. Np. w Windows dokładność pomiaru czasu jest na poziomie 0.1 mikrosekundy. Może być gorsza, zależnie od użytej metody. W Unixach i Linuxach bywa bardzo różnie (tu trzeba sprawdzić jaki jest kwant czasu, z którym przyrastają zmierzone wartości). Na to nakłada się niedeterminizm systemów komputerowych – w kolejnych wykonaniach programu jego czasy trwania mogą być różne. Jeżeli rozrzut czasów wykonania (mierzony np. odchyleniem standardowym, SIQR, IQR) jest większy niż dokładność (kwant) pomiaru czasu to mamy jeszcze mniejszą dokładność. Co więc praktycznie zrobić? Trzeba wybrać większą z tych dwóch wartości (dokładność pomiaru, miara rozrzutu) i zaokrąglić uzyskany pomiar czasu do takiej jednostki. Tym wszystkim zajmują się metrologia i statystyka.
• Z czym porównać jakość rozwiązania skoro nie mamy rozwiązania optymalnego? Możliwe rozwiązania: a) z dolnym ograniczeniem wartości funkcji celu (dla minimalizacji, tzw. lower bound), b) z algorytmem losowym, c) z najlepszymi rozwiązaniami innymi heurystykami.

• Szeregowanie parallel tasks (zadań równoległych) wg danych z parallel workload archives. Znaleźć uszeregowanie o najmniejszym średnim czasie przepływu, co jest równoważne minimalnej sumie czasów zakończenia zadań, 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ć, pominąć). Identyfikatory zignorowanych zadań z pliku wejściowego nie pojawią się w pliku wyjściowym. Nie można jednak zmieniać identyfikatorów zadań w wynikowym pliku. Czyli mówiąc inaczej, nie można ich przenumerowywać, aby były po kolei w pliku wynikowym.
     
  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 ma 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. Ponieważ czas wykonania algorytmów zależy od liczby zadań, a liczby zadań w plikach bywają bardzo duże, łatwo można zadać taką instancję, której nie da się rozwiązać w ustalonym limicie 5 minut. Dlatego zakładamy, że w czasie 5 minut programy muszą być w stanie znaleźć rozwiązanie dla co najmniej 10000 zadań.
  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ąć w tych testach powinien wynikać z limitu czasu. Patrz uwagi o implementacji. Dobra instancja do testów sumy czasów zakończenia zadań: test-n10k-m128-r0-0.zip, gdyż wszystkie zadania są gotowe jednocześnie. W sprawozdaniu można przedstawić wyniki działania programu z dłuższym limitem czasu niż 5 min.
  Sprawdzarka konsola. Uwaga: sprawdzarka zakłada, że identyfikatory zadań są ≤ MaxJobs.
  
  
• 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, separatorem między liczbami powinna być spacja lub inna "whitespace". 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 (np. instancja orb07.txt). Operacji o czasie trwania 0 można nie przydzielać do niczego, ale jej pozorny moment rozpoczęcia trzeba wypisać w wynikowym rozwiązaniu, tak jakby była przydzielona do wirtualnej maszyny, która jest zawsze dostępna. Zakładamy też że możliwy jest 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. Inna dobra instancja do testów to Ta70. Pocięte pliki z instancjami orlib i Taillarda do testów js1.ZIP. Przykładowe instancje o dużym rozmiarze TaiLarge.ZIP (1000×1000)
  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), konsola. Plik zawiera 4 różne wersje: katalog ver23 - stara wersja zachowana dla zainteresowanych, katalog główny plik "chk_jsorl.exe" wersja dla Windows, katalog główny plik "chk_jsorl" wersja dla Linuxa. W razie wykrycia błędów w nowej wersji można posłużyć się starą. Proszę też informować o problemach.
  
  
• Capacitated Vehicle Routing Problem with Time Windows (CVRPTW, problem marszrutyzacji z ograniczeniami pojemności i oknami czasowymi).
  Na czym polega CVRP można przeczytać na stronach:
  
  • CVRPLIB proszę użyć instancji VRPTW benchmarks (Solomon (1987) i Homberger and Gehring (1999)),
  • TSPLIB,
  • http://en.wikipedia.org/wiki/Vehicle_routing_problem.
    
  Ponieważ opisy w różnych źródłach różnią się co do szczegółów, przyjmujemy następujące sformułowanie problemu:
  Dany jest graf skierowany G=(V,A), V to zbiór wierzchołków z wyróżnionym źródłem (depot, magazyn), A to zbiór łuków. Każdy wierzchołek (odbiorca) jest scharakteryzowany przez wektor wartości (i,x,y,q,e,l,d), gdzie: i - numer wierzchołka (i=0 to magazyn/depot), x,y - współrzędne wierzchołka na płaszczyźnie (Euklidesowej), q - zapotrzebowanie na towar, e,L - początek i koniec okna, w którym dostawa ma być wykonana, d - czas rozładunku. Każda ciężarówka ma ograniczoną pojemność Q. Każdego odbiorcę wolno odwiedzić tylko raz dostarczając mu całe zapotrzebowanie q. W pojedynczym objeździe ciężarówka może odwiedzić wierzchołki o całkowitym zapotrzebowaniu niewiększym niż Q. Jeżeli ciężarówka przyjedzie do odbiorcy/wierzchołka przed czasem e, to musi czekać. Dlatego moment rozpoczęcia rozładunku w wierzchołku odwiedzonym jako i-ty można wyznaczyć z rekurencyjnego wzoru: b_i=max{b_{i-1}+d_{i-1}+c_{i-1,i},e_i}, b_0=0. (Uwaga "_i" oznacza dolny indeks "i"). Jeżeli ciężarówka przyjedzie po czasie L, to rozwiązanie jest niedopuszczalne. Rozładunek może się zakończyć po czasie L. Długość drogi z wierzchołka i do wierzchołka j równa się czasowi c_{ij}. Koszt drogi dla pojedynczej ciężarówki, to suma wszystkich czasów przejazdów c_{i,i+1}, czasów rozładunku d_i oraz ewentualnego oczekiwania. Całkowity koszt rozwiązania to suma po wszystkich trasach (po wszystkich ciężarówkach). Problem jest wielokryterialny z ograniczeniami dopuszczalności rozwiązania, dlatego przyjmujemy, że w pierwszej kolejności należy zadbać o dopuszczalność rozwiązania, dalej minimalizować liczbę marszrut (in. objazdów, ciężarówek), a w trzeciej kolejności sumaryczny koszt.
  Dodatkowe założenia i zastrzeżenia:
  1. Między wierzchołkami ciężarówki poruszają się po liniach prostych ("lotem ptaka").
  2. Dane wejściowe będą w pliku w formacie Solomona :
     nazwaproblemu\n
     VEHICLE\n
     NUMBER CAPACITY\n
     K Q\n
     CUSTOMER\n
     CUST NO. XCOORD. YCOORD. DEMAND READY TIME DUE DATE SERVICE TIME\n
     i_0 x_0 y_0 q_0 e_0 l_0 d_0\n
     ...
     i_n x_n y_n q_n e_n l_n d_n\n
     gdzie "\n" oznacza znak nowej linii. K jest liczbą ciężarówek/marszrut. Wszystkie liczby w pliku wejściowym są typu int. Puste linie należy zignorować.
  3. Liczba marszrut w rozwiązaniu nie musi być mniejsza, lub równa K (można ją zignorować). (K zachowujemy w plikach wejściowych ze względu na kompatybilność z zewnętrznymi źródłami instancji).
  4. Instancje do testów znajdują się na stronie https://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-with-time-windows-instances/ . Lokalne kopie: solomon_25.zip , solomon_50.zip , solomon_100.zip , s-cvrptw.zip .
  5. Rozwiązanie podać w pliku w postaci:
     liczbatras całkowitadługośćwszystkichtras\n
     nr_1._wierzchołka_w_1.trasie nr_2._wierzchołka_w_1.trasie ...\n,
     ...
     nr_1._wierzchołka_w_ostatnietrasie nr_2._wierzchołka_w_ostatniejtrasie ...\n
     gdzie "\n" oznacza znak nowej linii, separatorem między numerami powinna być spacja lub inna "whitespace".
     
  6. Jeżeli rozwiązanie dopuszczalne nie istnieje, to jako "liczbatras" podać -1.
  7. W rozwiązaniach wierzchołki numerujemy od 1 tak jak w plikach danych (a nie od 0 jak w niektórych plikach z wynikami w ww. repozytoriach sieciowych),
  8. W ciągu wierzchołków składających się na jedną marszrutę (objazd) pomijamy wierzchołek początkowy i końcowy, którym zawsze jest magazyn.
  9. Długość trasy należy podać z co najmniej 5 miejscami po przecinku.
  10. Plik musi być prawidłowo zamknięty.
  11. Nie można przyjmować ograniczenia na rozmiar problemu mniejszego niż w przykładowych instancjach.
  Przykładowe dane testowe (tylko do sprawdzania poprawności działania programu): cvrptw1.txt (niedopuszczalne), cvrptw2.txt (1 objazd/ciężarówka, koszt 90), cvrptw3.txt (niedopuszczalne), cvrptw4.txt (3 objazdy/ciężarówki, koszt 160), m2kvrptw-0.txt (≤1048, ≤4520131.2), solomon_50.zip 56 instancji do testów.
  Instancje do testów efektywnościowych. W sprawozdaniu muszą się znaleźć pomiary czasu i jakości dla instancji: rc21010 dla narastającej liczbie wierzchołków od 1 do 1000. Większa liczba testów będzie działać na korzyść przy ocenie pracy.
  Sprawdzarka: ckrptw.exe - Windows konsola, ckrptw_lin - Linux.
  Wykład o CVRP: Jan Christiaens, Greet Vanden Berghe, Vehicle routing. A focus on heuristic design, Scheduling seminar 12.X.2022 (pdf, ~3.5MB)

1. Jak określić kiedy metaheurystyka ma się zatrzymać? Są (przynajmniej) dwa wyjścia.
   a) Jeżeli algorytm jest zdefiniowany tak, że znamy optymalną wartość funkcji celu (taka wartość nie musi być "prawdziwa" można przyjąć jakąś wartość spekulatywnie do osiągnięcia), to algorytm może zatrzymać się po jej osiągnięciu. Spekulatywnie przyjętą testową wartość funkcji celu można też zmniejszyć, o ile metodzie udało się uzyskać tę wartość.
   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 (dla instancji tak małych jak te na zajęciach), a algorytmy takie jak BB, GA, Tabu nie powinny działać dłużej niż kilka minut. Programy muszą zatrzymywać się w określonych powyżej limitach czasu.
   
2. Strojenie (tuning) metaheurystyk.
   Jeżeli ktoś z Państwa implementuje jakąś metaheurystykę, to proszę zwrócić uwagę, że metaheurystyki zwykle mają szereg "magicznych" parametrów sterujących ich działaniem. Na przykład: tabu search - długość listy tabu, rozmiar przeszukiwanego sąsiedztwa, genetic search - rozmiar populacji, prawdopodobieństwo mutacji, simulated annealing - sposób zmieniania temperatury, a wszystkie takie algorytmy razem mają jakiś warunek stopu (np. liczba iteracji, czas działania do zatrzymania). Te wszystkie parametry trzeba sensownie dobrać. Wymaga to testowania i eksperymentalnego dobierania. Wyniki takich testów trzeba opisać i objaśnić w sprawozdaniu. Program musi też mieć jakieś domyślne wartości parametrów kontrolnych, aby osoba używająca programu nie musiała zaczynać używania od ponownego strojenia. Zwykle wiązanie ad hoc tych "magicznych" liczb ze strukturą instancji (np. długość listy tabu równa się 10% liczby wierzchołków w grafie) nie jest dobrym pomysłem. Brak strojenia oznacza, że metaheurystyka 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. Informacja o błędzie musi zawierać przykładowe pliki wejściowe z objaśnieniem co działa niepoprawnie.
3. Za znalezienie błędów w danych +0.1 do oceny końcowej.

• Szeregowanie zadań równoległych (PaTa) - F.Kaczmarek, P.Serdeczna - uzyskany wynik: 1083417580. Najlepszy dotychczas: 725251161.
• Job-shop (JS) - P.Brzozowski, D.Pasler - uzyskany wynik: 3184. Najlepszy uzyskany dotychczas 3211. Jest ulepszenie!. Zastosowano środowisko MiniZinc. Znany upper bound: 2902.
• CVRPTW - J.Kozicki, J.Ogrodowski - uzyskany wynik: (1020, 4307740.573). Najlepsze dotychczas znane wyniki: (998, 4050701.965) ciężarówki, (1018, 3688638.546) długość trasy.

Osoby, które uzyskały polepszające wyniki w przeszłości

2014 -- G.Latosiński + J.Synak (JS: 3291), K.Krakowski + M.Ledzianowski (CRPTW: 1020 ciężarówek), A.Borowski (CVRPTW: 3874362.6312 długość trasy)
2016 -- F.Krawiec + M.Leśny (Pata: 1083230633), N.Schlaffke + M.Slysz (CRPTW: 1017 ciężarówek, długość trasy: 4362883.055)
2017 -- K.Krakowski + I.Małyszka (Pata: 725251161)
2018 -- M.Leszczyk + A.Zielińska (CVRPTW: 3756354.9435 długość trasy, liczba ciężarówek: 1021)
2019 -- D.Makałowski + M.Okonek (CVRPTW: 4050701.9654 długość trasy, liczba ciężarówek: 998)
2020 -- K.Jajeśnica + K.Jakusik (JS: 3211)
2023 -- B.Kozłowski + A.Pilawski (CVRPTW: 3688638.54649 długość trasy, liczba ciężarówek: 1018)
2024 -- P.Brzozowski, D.Pasler (JS: 3184)

MD. Ostatnia zmiana :