Optymalizacja planu lekcji pod kątem wagi plecaka

Jednym z zadań technologii jest sprawiać, by nasze życie było lżejsze. O ile lżejsze? Sprawdzamy.

Temat wagi plecaka szkolnego od lat cieszy się żywym zainteresowaniem troskliwych rodziców, a w konsekwencji – polityków. Ostatnio plecaki ważyła nawet minister edukacji, choć według niektórych mediów metodologia przeprowadzonego przez panią minister eksperymentu mogła budzić wątpliwości. Cykliczność z jaką temat pojawia się w mediach pozwala twierdzić, że decydenci faktycznie ważą go sobie lekce. Sprawa jest jednak poważna i wymaga odpowiedniego traktowania. Ciekawej analizy zawartości plecaka swojego syna dokonał mój kolega z zespołu Data Science, Kamil Sijko, a efekt swojej pracy opisał na blogu (link). Zainspirowało mnie to do sprawdzenia potencjału jednego z proponowanych rozwiązań tego problemu – optymalizacji planu zajęć pod kątem masy plecaka.

Zadanie optymalizacji

Dla tych, którym wydaje się, że nie mają pojęcia czym jest optymalizacja w praktyce, śpieszę z wyjaśnieniami. Piszę wydaje się, bo zadania optymalizacji rozwiązujemy codziennie, niekoniecznie mając tego świadomość. Przykład: idziemy do baru mlecznego z zamiarem najedzenia się, wydając jednocześnie jak najmniej pieniędzy. Chcielibyśmy danie główne z kurczakiem, coś ciepłego do picia i dwa desery. I już! Właśnie zdefiniowaliśmy zadanie optymalizacji. Określiliśmy i sprecyzowaliśmy funkcję celu, której wartość chcemy zminimalizować (cena trójelementowego obiadu), zmienne decyzyjne i ich charakter (ceny dań głównych, napojów i deserów) oraz ograniczenia nałożone na te zmienne (danie główne ma być z kurczakiem, napój musi być ciepły, a desery chcemy dwa). Teraz wystarczy je tylko rozwiązać, czyli znaleźć takie wartości zmiennych decyzyjnych, dla których funkcja celu przyjmuje najmniejszą możliwą wartość.

Po akapicie wyrównującym poziom wiedzy pomiędzy Czytelnikiem a autorem, możemy omówić zadanie optymalizacji wagi plecaka. Mówi się, że każde równanie, które pojawia się w tekście, zmniejsza liczbę czytelników o połowę. Dlatego w tej części zadanie optymalizacji zdefiniuję jedynie opisowo, pomijając szczegóły istotne tylko dla komputera. Odważnych Czytelników zapraszam do akapitu niżej, a tym zabieganym polecam jego ominięcie i rzucenie okiem na same wyniki. No więc, chcemy ułożyć plan w taki sposób, aby waga plecaka była jak najmniejsza. Tylko co to właściwie znaczy? Można to przecież zinterpretować na kilka sposobów. Nam chodzi o ułożenie planu w taki sposób, aby masa plecaka w dniu, w którym jest on najcięższy, była jak najmniejsza. To jest nasza funkcja celu. Nasze zmienne to po prostu przedmioty zajęć. Jeśli zaś chodzi o ograniczenia, to:

  • Tygodniowa liczba zajęć z danego przedmiotu w planie proponowanym przez optymalizator musi się zgadzać z tą w obecnym planie (tj. jeśli uczeń ma matematykę (tylko!) cztery razy w tygodniu w obecnym planie, to musi ją mieć cztery razy w tygodniu również w zoptymalizowanym planie).
  • Zajęcia nie mogą być zbite w bloki trwające dłużej niż dwie godziny (tj. nie chcemy mieć trzech matematyk jednego dnia).
  • Maksymalna liczba lekcji w danym dniu wynosi osiem.
  • Minimalna liczba lekcji w danym dniu wynosi trzy.

I już! Wystarczy tylko przetłumaczyć to na język matematyki, a później komputera.

Implementacja

Zadanie opisane poniżej zostało rozwiązane przy wykorzystaniu języka Julia (wersja 0.6.4) i pakietu JuMP (0.18.4). Fragmenty kodu poniżej były pisane w notatniku Jupyter i stamtąd też pochodzą wklejane tutaj wyniki. Całość można znaleźć na (link).

Przygotowanie danych

Dane, które otrzymałem od Kamila przygotowałem w formie ramki danych o nazwie data_in do wczytania przez optymalizator:

│ Row │ Przedmiot   │ Sztuk │ Waga  │
│ 1   │ Matematyka  │ 4     │ 0.697 │
│ 2   │ Angielski   │ 3     │ 0.715 │
│ 3   │ Polski      │ 5     │ 1.676 │
│ 4   │ WF          │ 3     │ 0.297 │
│ 5   │ Religia     │ 2     │ 0.568 │
│ 6   │ Przyroda    │ 2     │ 1.214 │
│ 7   │ Technika    │ 1     │ 0.756 │
│ 8   │ Informatyka │ 1     │ 0.159 │
│ 9   │ Plastyka    │ 1     │ 0.167 │
│ 10  │ Historia    │ 1     │ 0.484 │
│ 11  │ Muzyka      │ 1     │ 0.36  │

Kolumna Sztuk przedstawia liczbę lekcji tygodniowo, Waga podaje masę wszystkich akcesoriów, które należy przynieść na dany przedmiot – podręcznik, zeszyt itd. Do tego, do każdego dnia należy doliczyć masę tzw. Przyborów – samego plecaka, piórnika itd., co można zrobić już po wykonaniu procesu optymalizacji. Wynosi ona:

Masa przyborów: 1.415

Inicjalizacja modelu i wybór solvera

Zanim zdefiniujemy zmienne, funkcję celu i ograniczenia, należy najpierw zainicjować model i przypisać mu właściwy solver (czyli silnik, który rozwiąże zdefiniowane zadanie optymalizacji). Taką kolejność wymusza na nas implementacja, choć w praktyce oczywiście robi się na odwrót tj. najpierw zapisujemy zmienne, funkcję celu i ograniczenia stosując formalizm matematyczny i na tej podstawie dobieramy odpowiedni solver. Jak pokażą kolejne akapity, nasze zadanie ma charakter MIQP (Mixed Integer Quadratic Programming – zadanie ze zmiennymi całkowitymi i kwadratową funkcją celu) wykorzystamy jednak solver Couenne (link) stosowany do bardziej ogólnej klasy problemów, która zawiera w sobie MIQP, czyli MINLP (Mixed Integer Non-Linear Programming – programowanie całkowitoliczbowe, nieliniowe). Inicjalizacja modelu w Julii:

mdl = Model(solver = AmplNLSolver(solver_couenne))

Zmienne decyzyjne, funkcja celu i ograniczenia

Jeszcze raz: mamy zminimalizować wagę plecaka w dniu, w którym jest on najcięższy. Jednak zapisanie tego wprost (jako minimalizacja największego z 5 członów, gdzie każdy człon to masa plecaka danego dnia) wymagałoby optymalizacji kilku funkcji na raz, do czego należałoby wykorzystać narzędzia do optymalizacji wielokryterialnej (multi-objective programming), które póki co w takich sytuacjach radzą sobie różnie. Na szczęście ten sam efekt można uzyskać na kilka różnych sposobów. Chcąc mieć jedną funkcję celu, możemy na przykład zminimalizować sumę kwadratów mas plecaka dla każdego dnia – to sprawi, że optymalizator będzie poszukiwał planu zajęć, dla którego masy dla wszystkich dni są jak najmniejsze (a w konsekwencji – zbliżone do siebie na tyle na ile to możliwe). Dlaczego suma kwadratów, a nie np. po prostu suma, czy może suma sześcianów? Obiecałem trzymać się z dala od wzorów i dowodów matematycznych, wyjaśnię więc na prostym przykładzie. Załóżmy, że pracownik magazynu ma do przeniesienia 3 paczki i ma na to 2 dni. Paczki te ważą kolejno 2, 3 i 5 kg. Magazynier, chcąc przenieść każdego dnia jak najmniej, ma do rozwiązania zadanie podobne do naszego. Doświadczony magazynier od razu wie, że należy przenieść paczki 2 i 3 kg jednego dnia, a paczkę 5 kg drugiego (lub na odwrót, kolejność dni nie ma znaczenia). Nasz magazynier jest jednak amatorem, ale na szczęście jest też entuzjastą programowania – siada więc do komputera i pisze optymalizator. Przy pierwszym podejściu jako funkcję celu przyjmuje sumę mas paczek do przeniesienia każdego dnia. Ku swojemu zdziwieniu odkrywa, że optymalizator każe mu przenieść 8 kg (5+3) pierwszego dnia i 2 kg w następnego. Uruchamia optymalizator jeszcze raz i tym razem okazuje się, że powinien przenieść 10 kg pierwszego dnia i poleniuchować drugiego. Magazynier w końcu orientuje się, że przy takiej funkcji celu, wynik optymalizacji to w zasadzie kwestia losowa – sumaryczna masa będzie zawsze równa 10 kg i nie ma znaczenia jak te masy będą rozłożone na dni. Jako że przykład jest bardzo prosty, możemy w zasadzie sprawdzić wszystkie możliwości jakie miał przed sobą optymalizator (dni oddzielono nawiasami):

(0)+(2+3+5) = 10

(2)+(3+5) = 10

(3)+(2+5) = 10

(5)+(2+3) = 10

Magazynier zauważa swój błąd i definiuje nową funkcję celu – sumę kwadratów mas dla każdego z dni. Uruchamia optymalizator i dowiaduje się, że i pierwszego, i drugiego dnia powinien przenieść 5 kg. Jego starszy kolega potwierdza, że to właściwe rozwiązanie. Sprawdźmy możliwe wartości funkcji celu:

(0)2 + (2+3+5)2 = 02 + 102 = 100

(2)2 + (3+5)2 = 22 + 82 = 68

(3)2 + (2+5)2 = 32 + 72 = 58

(5)2 + (2+3)2 = 52 + 52 = 50

Widzimy więc, że nowa funkcja celu przyjmuje minimalną wartość (50) przy optymalnej dystrybucji pracy. Jeśli zaś chodzi o sumę sześcianów i kolejnych potęg – takie funkcje celu również dałyby poprawne wyniki, ale byłoby to tylko niepotrzebne komplikowanie zadania. Im niższy stopień (wartość najwyższej potęgi) funkcji celu, tym łatwiejsze zadanie dla optymalizatora. Mam nadzieję, że teraz wszystko jest już jasne. Czytelników, którzy po tym przykładzie czują jednak pewien niedosyt odsyłam do Internetu, poszerzanie horyzontów można zacząć np. od czytania o metodzie najmniejszych kwadratów, która bazuje na podobnej koncepcji. My tymczasem spójrzmy na implementację funkcji celu w Julii:

@NLobjective(mdl, Min, sum((day[d])^2 for d in 1:days))

Po wydrukowaniu na ekran:

Min day[1] ^ 2.0 + day[2] ^ 2.0 + day[3] ^ 2.0 + day[4] ^ 2.0 + day[5] ^ 2.0

Gdzie day to masa plecaka danego dnia – nasza zmienna decyzyjna. Wcześniej zmienna ta została zainicjowana jako pięcioelementowy wektor w następujący sposób:

days = 5 #liczba dni w tygodniu
@variable(mdl, day[1:days])

Teraz, wykorzystując ograniczenia, przypiszemy funkcję do zmiennej day. Gdyby dany przedmiot mógł mieć miejsce tylko raz dziennie, byłaby to po prostu kombinacja liniowa masy akcesoriów dla danego przedmiotu i zmiennej binarnej, określającej czy dany przedmiot występuje danego dnia (wtedy zmienna binarna przyjmuje wartość 1), czy też nie (co odpowiada zmiennej binarnej =0), np:

Masa_plecaka_w_poniedziałek = x_polski ∙ masa_akcesoria_polski + x_WF ∙ masa_akcesoria_WF + …

Gdzie x_przedmiot to zmienna binarna. Założyliśmy jednak, że przedmioty mogą występować w blokach. Wobec czego możemy zdefiniować zmienną x_przedmiot w taki sposób, by mogła przyjmować wartości ze zbioru [0, 1, 2], ale to utrudniłoby zadanie optymalizatorowi. Możemy też dodać zmienną definiującą cały 2-godzinny blok i pozostawić ją jako zmienną binarną, wtedy:

Masa_plecaka_w_poniedziałek = x_polski ∙ masa_akcesoria_polski +x_dwa_polskie ∙ masa_akcesoria_polski + …

Uwzględniając powyższe rozważania, po przypisaniu każdemu z przedmiotów i dni odpowiedniej liczby, masę dla każdego dnia zaimplementowano w następujący sposób:

for d in 1:days
  @constraint(mdl, day[d] == sum(sum(x[d,c,m]*data_in[:Waga][c] for c in 1:course_no) for m in 1:max_course_occurrences))
end

Oczywiście, uprzednio zdefiniowano zmienną binarną x:

course_no = size(data_in,1) #liczba lekcji - u nas 11
max_course_occurrences = 2 #max liczba zajęć z tego samego przedmiotu danego dnia
@variable(mdl, x[1:days,1:course_no, 1:max_course_occurrences], Bin, start=0)

Wydruk tego równania na ekran dla poniedziałku (dzień pierwszy) wygląda następująco:

day[1] = 0.01394 x[1,1,1] + 0.0143 x[1,2,1] + ... + 0.01394 x[1,1,2] + ... + 0.0072 x[1,11,2]

Teraz należy zapewnić, że każdy przedmiot pojawia się w planie odpowiednią liczbę razy:

for c in 1:course_no
 @constraint(mdl, sum(sum(x[d,c,m]*m for d in 1:days)for m in 1:max_course_occurrences) == data_in[:Sztuk][c])
end

Wydruk na ekran dla kursu nr 1 daje:

x[1,1,1] + x[2,1,1] + x[3,1,1] + x[4,1,1] + x[5,1,1] + 2 x[1,1,2] + 2 x[2,1,2] + 2 x[3,1,2] + 2 x[4,1,2] + 2 x[5,1,2] == 4

Do tego nakazujemy optymalizatorowi, aby danego dnia, dany przedmiot pojawiał się maksymalnie dwa razy:

for d in 1:days
 for c in 1:course_no
  @constraint(mdl, sum(x[d,c,m]*m for m in 1:max_course_occurrences) <= max_course_occurrences)
 end
end

Dla przedmiotu nr 1:

x[1,1,1] + 2 x[1,1,2] <= 2

W analogiczny sposób można zaimplementować ograniczenia na maksymalną oraz minimalną liczbę zajęć danego dnia, ale celowo nie dopisywałem ich do zestawu ograniczeń. Intuicja podpowiada, że optymalizator sam powinien znaleźć rozwiązanie, które nie wykracza poza te granice.  Nie pozostaje więc nic innego jak uruchomić optymalizację i zobaczyć wyniki:

status = solve(mdl)

Optymalizator przystąpi do pracy, a zanim to zrobi poda nam garść ciekawych informacji o naszym zadaniu. Łączna liczba zmiennych wynosi 115, z czego 110 to zmienne binarne (pozostała piątka, to zmienne day), natomiast liczba równań zapisanych w ograniczeniach wynosi 71.

Wyniki i wnioski

Przypomnijmy najpierw wyniki jakie otrzymał Kamil. Masy plecaka dla kolejnych dni tygodnia wynosiły odpowiednio: 4.638, 4.785, 5.099, 5.861, 6.311 kg. Najcięższy plecak ważył więc 6.311 kg, a sumarycznie jego syn przeniósł około 27 kg. Oto wyniki optymalizacji:

│ Row │ Poniedzialek │ Wtorek    │ Sroda      │ Czwartek   │ Piatek   │
│ kg  │ [3.907]      │ [3.806]   │ [3.788]    │ [3.859]    │ [3.869]  │
│ 1   │ Polski       │ Angielski │ Matematyka │ Matematyka │ Przyroda │
│ 2   │ Polski       │ Polski    │ Matematyka │ Matematyka │ Przyroda │
│ 3   │ WF           │ Polski    │ Polski     │ Angielski  │ Technika │
│ 4   │ WF           │           │            │ Angielski  │ Historia │
│ 5   │ Informatyka  │           │            │ WF         │          │
│ 6   │ Muzyka       │           │            │ Religia    │          │
│ 7   │              │           │            │ Religia    │          │
│ 8   │              │           │            │ Plastyka   │          │

Po optymalizacji planu masa plecaka nie przekracza 3.907 kg (czyli wagę plecaka w najcięższym dniu udało się zmniejszyć o prawie 40%!), a sumaryczna masa dźwigana tygodniowo wynosi 19 kg (redukcja o 30%). Oczekiwanym było działanie optymalizatora polegające na łączeniu przedmiotów w dwugodzinne bloki. Warto jednak zauważyć, że strategia ta nie została w żaden sposób narzucona ograniczeniami, co tylko potwierdza poprawny przebieg procesu optymalizacji. W następnym kroku optymalizator łączył dwugodzinne bloki ze sobą oraz z przedmiotami, które występują tylko raz, w optymalny sposób.

Z obawy o zbyt dużą objętość wpisu i dla zachowania ogólności rozwiązania porzuciłem pomysł nałożenia kilku dodatkowych ograniczeń, ale warto wspomnieć, że takowa istnieje. Można np. zabronić optymalizatorowi łączenia w bloki zajęć z WF, tak by zadbać o odpowiednią ilość ruchu każdego dnia. Można uwzględnić zróżnicowaną przyswajalność wiedzy w zależności od pory dnia i nakazać, by przedmioty ścisłe pojawiały się rano (to wcale nie żart – to pomysł MEN, uważam zresztą, że dobry). Można też zastosować wskazówki specjalistów od budowania masy mięśniowej i rozłożyć obciążenie w kolejnych dniach rosnąco (to już żart, wiem – słaby). W końcu – można dodać kolejną warstwę uwzględniającą plany zajęć nauczycieli i innych klas oraz dostępność sal. To wszystkiego leży jednak poza zakresem prostego optymalizatora stworzonego na potrzeby wpisu na blogu.

Podsumowując – potencjał opisanego rozwiązania jest bardzo duży. Warto się więc zastanowić czy nie należałoby uwzględniać kryterium wagi plecaka przy układaniu planu zajęć? Do tego, aby łączyć lekcje dwójkami, nie potrzeba przecież pisać optymalizatora, a już samo to mogłoby znacząco poprawić sytuację uczniów. Wreszcie – poza masą plecaka, to rozwiązanie ma też przecież zalety dydaktyczne.


                      
o autorze
Jakub Białek
Doktorant energetyki, ukończył studia magisterskie na dwóch europejskich uczelniach (Sztokholm, Grenoble) w ramach programu InnoEnergy, doświadczony w modelowaniu matematycznym procesów fizycznych i optymalizacji wielkoskalowej.