To nic osobistego, po prostu Debian jest lepszy: lp_solve vs Excel Solver

Programowanie liniowe może nie jest najczęściej zlecanym zadaniem dla komputera domowego ale w niektórych przypadkach taki sposób rozwiązywania problemów jest jedynym optymalnym. Dla osób, które nie miały okazji jeszcze zapoznać się z programowaniem liniowym wspomnę, iż jest to dziedzina nauki matematycznej zwana badaniami operacyjnymi. Dzięki tym metodom opisywania problemów możemy uzyskać optymalne rozwiązanie jakiegoś problemu. Jednym z przykładów takich rozwiązań są programy, które po wskazaniu gdzie i skąd chcesz dojechać ustalają najkrótsza z możliwych dróg. Wtedy minimalizujesz zużycie kosztów podróży – prawda że życiowe.

W swojej pracy zdarzały mi się takie zadania, których rozwiązywanie na piechotę krótko mówiąc byłoby bardzo dręczące. Tak więc, gdy mamy do czynienia z rozdysponowaniem ograniczonych zasobów do realizacji ustalonego zadania mamy również do czynienie z zadaniem dążącym do maksymalizacji bądź minimalizacji. Zamiast na kartce papieru rozpisywać wszystkie możliwe kombinacje i szukać tej, która spełni nasze oczekiwania lepiej użyć do tego urządzenia, które zostało stworzone do analizy danych – czyli komputera.

Jeszcze przed potrzebą korzystania z takiego narzędzia wiedziałem o istnieniu dodatku do programu Excel zwanym Solver. Rok temu przyszedł czas jego wykorzystania. Miałem okazje go przetestować, w początkowej fazie byłem z niego zadowolony. Jednak gdy zacząłem zlecać mu coraz bardziej skomplikowane zadania ten albo w ogóle nie generował wyników albo były one nierealne! Nie miałem wyjścia, szybko zacząłem szukać innego narządzi i oczywiście darmowego. Znalazłem lp_solve, który używał najpopularniejszych formatów zapisu zadania liniowego między innymi MPS, którego zazwyczaj uczy się na studiach. Ja osobiście go nie lubiłem ale dostępny był również prostszy format zwany lp. lp_solve potrafił sprostać wymaganiom, z którymi Solver z Excela sobie po prostu nie radził. Problem, na podstawie którego stwierdziłem iż lp_solve jest o wiele lepszy od rozwiązania zaimplementowanego w pakiecie Office był bardziej złożony niż ten, który przedstawię tu jak przykład. Mimo to, że tu zaprezentuje to na prostszym przykładzie to Excel Solver z nim również sobie nie radzi.
Przejdźmy do faktów i przetestujmy oba narzędzia na przykładowym problemie. Problem, który do tego celu wymyśliłem jest tej samej klasy, z którym ostatnio miałem naprawdę do czynienia.

Załóżmy, że mamy ośrodek szkolenia kierowców, w którym mamy trzy sale do prowadzenia zajęć teoretycznych. Uzbieraliśmy aż 4 grupy, ale wszystkie mogą tylko w tym samym czasie odbywać zajęcia, bo np. wszystkim pasuje po pracy. Mamy więc o jedną salę za mało aby wszystkie grupy mogły się pomieścić na raz. Ponadto wszystkie grupy muszą łącznie odbyć 15 spotkań. Dni, w których te spotkania mogą się odbywać jest 20. Oczekuje się takiego rozplanowania harmonogramu dla tych grup aby dla każdej z nich zajęcia były równomiernie rozłożone w ciągu tych 20 dni.

Zaczniemy od Excela, stworzymy tabelkę, gdzie kolumny będą odzwierciedlać grupy, a wiersze kolejne dni, w których mogą odbywać się spotkania. Jeżeli w komórce położonej na skrzyżowaniu grupy oraz konkretnego dnia znajduje się 1 to znaczy, że grupa w tym czasie ma zajęcia, w przeciwnym wypadku będzie to 0. Tabelka będzie wypełniana danym w formie binarnej (0,1).

Każdej komórce w polu tabeli przydzielona jest zmienna, w tym przypadku oznaczona po prostu adresem komórki. Jak widzimy nasza funkcja optymalizująca ma postać prostego dodawania wszystkich pól. Dzięki temu, że nasz program będzie operował na liczbach binarnych nie będziemy musieli tworzyć warunków nakazujących aby liczby były większe lub równe zero itp..

W opcjach możemy zauważyć, jaki jest zakres zmienianych komórek (zmiennych), że funkcja ma maksymalizować wynik oraz warunki jakie przy tym wszystkim muszą być spełnione. Zaznaczony warunek mówi dla Solvera, że zmienne ma traktować jak binarne, czyli tylko wartości 0,1. Warunek poniżej wymaga aby w każdym wierszu nie było więcej jedynek niż 3, czyli w każdym dniu mogą pomieścić się tylko 3 grupy. Należy taki warunek założyć dla każdego wiersza oddzielnie. Powyżej zaznaczonej opcji mamy warunki dla kolumn, odpowiadają one wymogowi który mówi, że wszystkich spotkań każda z grup musi odbyć 15.

Na powyższym rysunku widzimy jak zakłada się takie warunki w Excelu. To są podstawowe warunki, więc dajmy już teraz szanse na Excel Solver i każmy rozwiązać mu to zadanie zanim zaczniemy dodawać kolejne warunki.

Proszę bardzo, oto na co stać wspaniały dodatek Solver do Excela. Wstawił same zera. Próbowałem przy innych warunkach – wstawiał same jedynki, przy innych opcjach same czwórki. Jak widzimy Solver sobie po prostu nie poradził z tak trywialnym zadaniem, przecież to by można od biedy na kartce rozpisać. Warto tu wspomnieć, że przygotowanie funkcji oraz warunków zadania było dość pracochłonne, zwłaszcza biorąc pod uwagę, że jest to narzędzie obsługiwane z graficznym interfejsem.

Teraz to zadanie zlecimy dla lp_solve. Jest to narzędzie bez graficznego interfejsu ale bez obaw, w przypadku większych zadań będzie to jego atutem. Zaczynamy edytować plik test.lp, składnia opisana jest pod adresem http://lpsolve.sourceforge.net/5.5/ zakładka „lp file format”.
Zmienne, które były komórkami w Excelu, tu będziemy oznaczać:
- możliwe spotkania grupy A: a1, a2, .. a20
- możliwe spotkania grupy B: b1, b2, .. b20
- możliwe spotkania grupy C: c1, c2, .. c20
- możliwe spotkania grupy D: d1, d2, .. d20
Pierwsze co musimy robimy to funkcje celu, czyli sumujemy wszystkie pola z przedstawianej tabeli po kolumnach. Hy, musimy wypisać osiemdziesiąt razy „a1 +”? Nie. BASH zrobi to za nas:

$ for ((i=1; i<=20; i++)); do echo -n "a$i + "; done && echo a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10 + a11 + a12 + a13 + a14 + a15 + a16 + a17 + a18 + a19 + a20 +

Powtarzamy pętle dla zmiennych b, c, d i już mamy funkcje celu:

max: a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10 + a11 + a12 + a13 + a14 + a15 + a16 + a17 + a18 + a19 + a20 +  
      b1 + b2 + b3 + b4 + b5 + b6 + b7 + b8 + b9 + b10 + b11 + b12 + b13 + b14 + b15 + b16 + b17 + b18 + b19 + b20 + 
      c1 + c2 + c3 + c4 + c5 + c6 + c7 + c8 + c9 + c10 + c11 + c12 + c13 + c14 + c15 + c16 + c17 + c18 + c19 + c20 + 
      d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10 + d11 + d12 + d13 + d14 + d15 + d16 + d17 + d18 + d19 + d20;

teraz ograniczenie dotyczące dostępności tylko 3 sal dla 4 grup (a,b,c,d):

# for ((i=1; i<=20; i++)); do echo "spotkanie_$i: a$i + b$i + c$i + d$i <= 3;"; done spotkanie_1: a1 + b1 + c1 + d1 <= 3; spotkanie_2: a2 + b2 + c2 + d2 <= 3; spotkanie_3: a3 + b3 + c3 + d3 <= 3; spotkanie_4: a4 + b4 + c4 + d4 <= 3; spotkanie_5: a5 + b5 + c5 + d5 <= 3; spotkanie_6: a6 + b6 + c6 + d6 <= 3; spotkanie_7: a7 + b7 + c7 + d7 <= 3; spotkanie_8: a8 + b8 + c8 + d8 <= 3; spotkanie_9: a9 + b9 + c9 + d9 <= 3; spotkanie_10: a10 + b10 + c10 + d10 <= 3; spotkanie_11: a11 + b11 + c11 + d11 <= 3; spotkanie_12: a12 + b12 + c12 + d12 <= 3; spotkanie_13: a13 + b13 + c13 + d13 <= 3; spotkanie_14: a14 + b14 + c14 + d14 <= 3; spotkanie_15: a15 + b15 + c15 + d15 <= 3; spotkanie_16: a16 + b16 + c16 + d16 <= 3; spotkanie_17: a17 + b17 + c17 + d17 <= 3; spotkanie_18: a18 + b18 + c18 + d18 <= 3; spotkanie_19: a19 + b19 + c19 + d19 <= 3; spotkanie_20: a20 + b20 + c20 + d20 <= 3;

Wynik polecenie wklejamy do naszego pliku test.lp. Kolejnym warunkiem jest to, że każda z grup w sumie musi odbyć 15 spotkań. Kopiujemy naszą funkcje celu i przerabiamy ją na następującą postać:

grupa_a: a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10 + a11 + a12 + a13 + a14 + a15 + a16 + a17 + a18 + a19 + a20 = 15;
grupa_b: b1 + b2 + b3 + b4 + b5 + b6 + b7 + b8 + b9 + b10 + b11 + b12 + b13 + b14 + b15 + b16 + b17 + b18 + b19 + b20 = 15;
grupa_c: c1 + c2 + c3 + c4 + c5 + c6 + c7 + c8 + c9 + c10 + c11 + c12 + c13 + c14 + c15 + c16 + c17 + c18 + c19 + c20 = 15;
grupa_d: d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10 + d11 + d12 + d13 + d14 + d15 + d16 + d17 + d18 + d19 + d20 = 15;

Zostało jeszcze poinformować solver, że zmienne są binarne:

$ for ((i=1; i<=20; i++)); do echo -n "a$i, "; done && echo a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19, a20,

Powtarzamy analogicznie dla zmiennych b,c,d i składamy to do następującej postaci:

bin a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19, a20, 
     b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, 
     c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, c13, c14, c15, c16, c17, c18, c19, c20, 
     d1, d2, d3, d4, d5, d6, d7, d8, d9, d10, d11, d12, d13, d14, d15, d16, d17, d18, d19, d20;

Dobrze, mamy już wszystko co mieliśmy w Excelu, każmy teraz dla lp_solve rozwiązać problem:

$ lp_solve test.lp  
  
 Value of objective function: 60 
  
 Actual values of the variables: 
 a1                              1 
 a2                              1 
 a3                              1 
 a4                              1 
 a5                              1 
 a6                              1 
 a7                              1 
 a8                              1 
 a9                              1 
 a10                             1 
 a11                             1 
 a12                             1 
 a13                             1 
 a14                             1 
 a15                             1 
 a16                             0 
 a17                             0 
 a18                             0 
 a19                             0 
 a20                             0 
 b1                              1 
 b2                              1 
 b3                              1 
 b4                              1 
 b5                              1 
 b6                              1 
 b7                              1 
 b8                              1 
 b9                              1 
 b10                             1 
 b11                             0 
 b12                             0 
 b13                             0 
 b14                             0 
 b15                             0 
 b16                             1 
 b17                             1 
 b18                             1 
 b19                             1 
 b20                             1 
 c1                              1 
 c2                              1 
 c3                              1 
 c4                              1 
 c5                              1 
 c6                              0 
 c7                              0 
 c8                              0 
 c9                              0 
 c10                             0 
 c11                             1 
 c12                             1 
 c13                             1 
 c14                             1 
 c15                             1 
 c16                             1 
 c17                             1 
 c18                             1 
 c19                             1 
 c20                             1 
 d1                              0 
 d2                              0 
 d3                              0 
 d4                              0 
 d5                              0 
 d6                              1 
 d7                              1 
 d8                              1 
 d9                              1 
 d10                             1 
 d11                             1 
 d12                             1 
 d13                             1 
 d14                             1 
 d15                             1 
 d16                             1 
 d17                             1 
 d18                             1 
 d19                             1 
 d20                             1

Ba, jak widać jednak się da! Jeszcze jedna rzecz mi się nie podoba, grupie A również ;) - mają zajęcia dzień w dzień a potem na koniec nie mają ich wcale przed egzaminem. To niepożądana sytuacja, zajęcia muszą być dla wszystkich grup równomiernie rozłożone o ile to możliwe. Można znaleźć wiele sposobów na to i uzyskać mniej lub bardziej pożądany wynik. Po przetestowaniu wielu pomysłów doszedłem do wniosku, że warunek nakazujący wstawić jedną przerwę na każde 4 kolejne dni dla danej grupy jest wystarczający. Oczywiście warunki wygenerujemy przy użyciu pętli:

$ for ((i=1,j=2,h=3,g=4; g<=20; i=i+4,j=j+4,h=h+4,g=g+4)); do echo "odstep_dla_a: a$i + a$j + a$h + a$g >= 3;"; done

Ponownie zmieniamy w pętli wszystkie wystąpienia zmiennej a na b, c, d i wyniki wklejamy do pliku. Poniżej przedstawiam cały plik test.lp:

// funkcja celu
//for ((i=1; i<=20; i++)); do echo -n "a$i + "; done && echo
max: a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10 + a11 + a12 + a13 + a14 + a15 + a16 + a17 + a18 + a19 + a20 + 
     b1 + b2 + b3 + b4 + b5 + b6 + b7 + b8 + b9 + b10 + b11 + b12 + b13 + b14 + b15 + b16 + b17 + b18 + b19 + b20 +
     c1 + c2 + c3 + c4 + c5 + c6 + c7 + c8 + c9 + c10 + c11 + c12 + c13 + c14 + c15 + c16 + c17 + c18 + c19 + c20 +
     d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10 + d11 + d12 + d13 + d14 + d15 + d16 + d17 + d18 + d19 + d20;

// podczas każdego spotkania dostepnych mamy tylko 3 sale
// for ((i=1; i<=20; i++)); do echo "spotkanie_$i: a$i + b$i + c$i + d$i <= 3;"; done
spotkanie_1: a1 + b1 + c1 + d1 <= 3;
spotkanie_2: a2 + b2 + c2 + d2 <= 3;
spotkanie_3: a3 + b3 + c3 + d3 <= 3;
spotkanie_4: a4 + b4 + c4 + d4 <= 3;
spotkanie_5: a5 + b5 + c5 + d5 <= 3;
spotkanie_6: a6 + b6 + c6 + d6 <= 3;
spotkanie_7: a7 + b7 + c7 + d7 <= 3;
spotkanie_8: a8 + b8 + c8 + d8 <= 3;
spotkanie_9: a9 + b9 + c9 + d9 <= 3;
spotkanie_10: a10 + b10 + c10 + d10 <= 3;
spotkanie_11: a11 + b11 + c11 + d11 <= 3;
spotkanie_12: a12 + b12 + c12 + d12 <= 3;
spotkanie_13: a13 + b13 + c13 + d13 <= 3;
spotkanie_14: a14 + b14 + c14 + d14 <= 3;
spotkanie_15: a15 + b15 + c15 + d15 <= 3;
spotkanie_16: a16 + b16 + c16 + d16 <= 3;
spotkanie_17: a17 + b17 + c17 + d17 <= 3;
spotkanie_18: a18 + b18 + c18 + d18 <= 3;
spotkanie_19: a19 + b19 + c19 + d19 <= 3;
spotkanie_20: a20 + b20 + c20 + d20 <= 3;

// każda grupa w sumie musi odbyć 16 spotkań
grupa_a: a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10 + a11 + a12 + a13 + a14 + a15 + a16 + a17 + a18 + a19 + a20 = 15;
grupa_b: b1 + b2 + b3 + b4 + b5 + b6 + b7 + b8 + b9 + b10 + b11 + b12 + b13 + b14 + b15 + b16 + b17 + b18 + b19 + b20 = 15;
grupa_c: c1 + c2 + c3 + c4 + c5 + c6 + c7 + c8 + c9 + c10 + c11 + c12 + c13 + c14 + c15 + c16 + c17 + c18 + c19 + c20 = 15;
grupa_d: d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10 + d11 + d12 + d13 + d14 + d15 + d16 + d17 + d18 + d19 + d20 = 15;

// przerwy
// for ((i=1,j=2,h=3,g=4; g<=20; i=i+4,j=j+4,h=h+4,g=g+4)); do echo "odstep_dla_d: d$i + d$j + d$h + d$g >= 3;"; done
odstep_dla_a: a1 + a2 + a3 + a4 >= 3;
odstep_dla_a: a5 + a6 + a7 + a8 >= 3;
odstep_dla_a: a9 + a10 + a11 + a12 >= 3;
odstep_dla_a: a13 + a14 + a15 + a16 >= 3;
odstep_dla_a: a17 + a18 + a19 + a20 >= 3;

odstep_dla_b: b1 + b2 + b3 + b4 >= 3;
odstep_dla_b: b5 + b6 + b7 + b8 >= 3;
odstep_dla_b: b9 + b10 + b11 + b12 >= 3;
odstep_dla_b: b13 + b14 + b15 + b16 >= 3;
odstep_dla_b: b17 + b18 + b19 + b20 >= 3;

odstep_dla_c: c1 + c2 + c3 + c4 >= 3;
odstep_dla_c: c5 + c6 + c7 + c8 >= 3;
odstep_dla_c: c9 + c10 + c11 + c12 >= 3;
odstep_dla_c: c13 + c14 + c15 + c16 >= 3;
odstep_dla_c: c17 + c18 + c19 + c20 >= 3;

odstep_dla_d: d1 + d2 + d3 + d4 >= 3;
odstep_dla_d: d5 + d6 + d7 + d8 >= 3;
odstep_dla_d: d9 + d10 + d11 + d12 >= 3;
odstep_dla_d: d13 + d14 + d15 + d16 >= 3;
odstep_dla_d: d17 + d18 + d19 + d20 >= 3;

// zmienne sa typu binarnego
// for ((i=1; i<=20; i++)); do echo -n "a$i, "; done && echo
bin a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19, a20,
    b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20,
    c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, c13, c14, c15, c16, c17, c18, c19, c20,
    d1, d2, d3, d4, d5, d6, d7, d8, d9, d10, d11, d12, d13, d14, d15, d16, d17, d18, d19, d20;

Po wygenerowaniu rozwiązania skopiowałem dane do pliku tekstowego w systemie Windows. Z Excela importowałem dane, oddzielając je spacjami w oddzielne kolumny. Po skopiowaniu wyników poszczególnych zmiennych do wcześniej utworzonej tabelki otrzymałem rozwiązanie.

Wydaje mi się, że poprzez użycie pętli powłoki do generowania warunków (już po ich opracowaniu) tekstowe narzędzie zostawiło w tyle graficznego giganta. Biorąc pod uwagę, to że Office jest dominującym produktem w swojej kategorii a Solver istnieje w nim już od bardzo dawna to wstyd, że nie poradził sobie z tak prostym zadaniem.

lp_solve potrafi wiele więcej niż pokazałem, rozwiązywałem na nim o wiele bardziej skomplikowane zadania i zawsze, o ile to logicznie było możliwe generował wyniki.