Architektoniczne algorytmy optymalizacji z HorusLP

Badania operacyjne i optymalizacja wypukła to dziedzina matematyki stosowanej, która przez lata znalazła szerokie zastosowanie komercyjne. Gdy moc obliczeniowa stała się bardziej przystępna cenowo i powszechnie dostępna, naukowcy zaczęli tworzyć coraz bardziej wyrafinowane algorytmy optymalizacyjne, aby pomóc im podejmować lepsze decyzje. Obecnie aplikacje oparte na badaniach operacyjnych mają wpływ na wszystko, od wyznaczania tras w globalnej logistyce po wygładzanie produkcji energii elektrycznej w przemyśle energetycznym.

Ponieważ podstawowa technologia stawała się coraz bardziej złożona, stworzono nowy zestaw narzędzi, aby pomóc naukowcom i programistom pracować bardziej produktywnie. Narzędzia te, takie jak AMPL, CVXPY i PuLP, umożliwiają programistom szybkie definiowanie, tworzenie i uruchamianie algorytmów optymalizacji oraz interfejs z szeroką gamą solwerów.

Jednak podczas gdy technologie optymalizacji i potrzeby biznesowe wciąż stają się coraz bardziej wyrafinowane, większość z tych narzędzi pozostała mniej więcej taka sama i nie ewoluowała wystarczająco szybko, aby sprostać potrzebom branży. W rezultacie opracowywanie, zarządzanie, debugowanie i dostrajanie tych algorytmów często wymaga dużych nakładów kognitywnych, zwłaszcza w szybko zmieniającym się środowisku biznesowym.

Dzisiaj chciałbym przedstawić HorusLP, bibliotekę optymalizacyjną Pythona, która pomaga w architekturze przepływów pracy związanych z tworzeniem algorytmów. Porozmawiamy o problemach, które narzędzie ma rozwiązać, a następnie przedstawimy krótki przegląd biblioteki Pythona i zbudujemy kilka przykładowych algorytmów optymalizacji.

Problemy stojące przed programistami algorytmów optymalizacji

Jednym z odwiecznych problemów, z jakimi boryka się większość programistów, jest równowaga między tworzeniem łatwego w utrzymaniu, wydajnego, idiomatycznego oprogramowania a dostarczaniem produktu w ramach czasowych ograniczeń projektu. Niezależnie od tego, czy pracujesz nad aplikacją opartą na przeglądarce, internetowym interfejsem API, czy mikrousługą uwierzytelniania użytkowników, często istnieje kompromis między „właściwym” sposobem a „szybkim” sposobem realizacji celów. Ten nieodłączny kompromis staje się coraz bardziej widoczny wraz ze wzrostem złożoności produktu.

W większości dyscyplin programista może złagodzić ten problem, wybierając framework lub bibliotekę, która pomaga w architekturze. W interfejsie internetowym wielu programistów wybiera React lub Angular; w świecie programowania API inżynierowie oprogramowania mogą wybierać między innymi Django, ASP.NET MVC czy Play. Jednak jeśli chodzi o skromnego programistę algorytmów optymalizacji, istnieje bardzo niewiele narzędzi architektury, które pomagają zarządzać złożonością architektury. Deweloper sam musi zarządzać zmiennymi, ograniczeniami i różnymi celami. Co więcej, algorytmy badań operacyjnych są generalnie trudne do introspekcji, co zaostrza problem.

Głównym celem HorusLP jest dostarczenie architektury do tworzenia algorytmów optymalizacji. Zapewniając spójność strukturalną, framework ułatwia organizację i pozwala programistom skupić się na tym, co robią najlepiej: tworzeniu algorytmów.

Typowe wyzwania związane z optymalizacją przepływu pracy

Istnieje kilka głównych źródeł złożoności podczas opracowywania algorytmów OR:

Złożoność ze zmiennych

• Zmienne często muszą być dodawane, aby uwzględnić dodatkowe wymagania biznesowe i nie ma łatwego sposobu na ich śledzenie w celu późniejszego wykorzystania w definicjach modeli i raportowaniu.
• Powiązane zmienne muszą być pogrupowane i śledzone, a nie ma oczywistego sposobu zarządzania nimi.

Złożoność z ograniczeń

• Ograniczenia muszą być dodawane i usuwane, aby obsługiwać różne scenariusze i wykonywać debugowanie, ale nie ma oczywistego miejsca do dodawania lub usuwania ograniczeń.
• Ograniczenia są często powiązane/zależne od siebie i nie ma naturalnego sposobu na wyrażenie ich relacji.

Złożoność z celów

• Wyrażenia obiektywne mogą stać się nieporęczne, jeśli mają wiele składników. Sytuacja może się pogorszyć, jeśli różne składniki są ważone, a wagi należy dostosować na podstawie wymagań biznesowych.

Złożoność wynikająca z debugowania

• Nie ma łatwego sposobu, aby zobaczyć wyniki modelu podczas opracowywania. Deweloper musi jawnie wydrukować nowe zmienne i wartości ograniczeń, aby zobaczyć wyniki. Prowadzi to do powielania kodu i wolniejszego rozwoju.
• Gdy dodanie wiązania powoduje, że model staje się niewykonalny, może nie być oczywiste, dlaczego wiązanie spowodowało, że model stał się niewykonalny. Zwykle programiści muszą usuwać różne ograniczenia i szukać niezgodności metodą prób i błędów

HorusLP ma nadzieję, że te wyzwania staną się łatwiejsze do opanowania poprzez zapewnienie struktury, narzędzi, najlepszych praktyk w celu poprawy produktywności programistów i łatwości konserwacji produktu.

Samouczek HorusLP: Algorytm optymalizacji i przegląd interfejsu API

Bez zbędnych ceregieli zanurkujmy i zobaczmy, co biblioteka HorusLP może dla Ciebie zrobić!

Ponieważ HorusLP jest oparty na Pythonie i PuLP, będziemy chcieli zainstalować je za pomocą pip. Uruchom następujące polecenie w wierszu poleceń:

 Pip install horuslp pulp

Po zakończeniu instalacji przejdźmy dalej i otwórzmy plik Pythona. Zaimplementujemy problem plecakowy z mojego wcześniejszego artykułu na temat badań operacyjnych.

Biblioteka HorusLP ma bardzo proste deklaratywne API i bardzo mało boilerplate’u. Zacznijmy od zaimportowania niezbędnych klas i zmiennych:

 from horuslp.core.Variables import BinaryVariable # we will be using binary variables, so we will import the BinaryVariable class from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent # We will also need to import the constraint class, variable manager class, the main problem class, and the objective class to define the objective. from horuslp.core.constants import MAXIMIZE # since we're maximizing the resulting value, we want to import this constant

Po zaimportowaniu wszystkich zmiennych zdefiniujmy zmienne, których potrzebujemy do tego problemu. Robimy to, tworząc podklasę menedżera zmiennych i wypełniając ją zmiennymi binarnymi:

 class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), # the first argument is the name of the variable BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') ]

Teraz, gdy zmienne są zdefiniowane, zdefiniujmy ograniczenia. Tworzymy ograniczenia, tworząc podklasę głównej klasy ograniczenia i implementując jej funkcję „definiuj”.

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

W funkcji define możesz poprosić o wymagane zmienne według nazwy. Framework zlokalizuje zmienną w menedżerze zmiennych i przekaże ją do funkcji define.

Po wdrożeniu ograniczenia możemy zrealizować cel. Ponieważ jest to prosty cel, użyjemy ObjectiveComponent :

 class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

Funkcja define ma bardzo podobną konfigurację do funkcji define klasy ograniczenia. Jednak zamiast zwracać wyrażenie ograniczające, zwracamy wyrażenie afiniczne.

Teraz, gdy zmienne, ograniczenia i cele są zdefiniowane, zdefiniujmy model:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE

Aby zbudować model, tworzymy klasę, która jest podklasą klasy Problem i określamy zmienne, cele, ograniczenia i sens. Mając określony problem, możemy go rozwiązać:

 prob = KnapsackProblem() prob.solve()

Po rozwiązaniu możemy wydrukować wyniki za pomocą funkcji print_results klasy problemu. Możemy również uzyskać dostęp do wartości określonych zmiennych, patrząc na klasę result_variables .

 prob.print_results() print(prob.result_variables)

Uruchom skrypt, a powinieneś zobaczyć następujące dane wyjściowe:

 KnapsackProblem: Optimal camera 0.0 figurine 1.0 cider 0.0 horn 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'camera': 0.0, 'figurine': 1.0, 'cider': 0.0, 'horn': 1.0}

Powinieneś zobaczyć status problemu, końcową wartość zmiennych, wartość celu i wartość wyrażenia ograniczającego. Widzimy również wynikowe wartości zmiennych jako słownik.

I oto mamy, nasz pierwszy problem HorusLP w około 35 wierszach!

W kolejnych przykładach omówimy bardziej wyrafinowane funkcje biblioteki HorusLP.

Korzystanie z grup zmiennych

Czasami zmienne są powiązane i należą do logicznej grupy. W przypadku problemu plecakowego wszystkie zmienne można umieścić w grupie obiektów. Możemy zrefaktoryzować kod tak, aby używał zmiennej group. Upewnij się, że zapisałeś kod z poprzedniej sekcji, ponieważ będziemy się do niego odnosić w kolejnych samouczkach!

Zmień instrukcje importu w następujący sposób:

 from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp.core.constants import MAXIMIZE

Teraz musimy również zmienić deklaracje zmiennych plecakowych w następujący sposób:

 class KnapsackVariables(VariableManager): vars = [ BinaryVariableGroup('objects', [ 'camera', 'figurine', 'cider', 'horn' ]) ]

Pierwszy argument to nazwa grupy zmiennych, druga zmienna to lista nazw zmiennych z tej grupy.

Teraz musimy zmienić ograniczenia i definicje celu. Zamiast pytać o poszczególne nazwy, zajmiemy się grupą zmiennych, która zostanie przekazana jako słownik, w którym klucze są nazwami, a wartości zmiennymi. Zmień definicje ograniczeń i celów w następujący sposób:

 class SizeConstraint(Constraint): def define(self, objects): return 2 * objects['camera'] + 4 * objects['figurine'] + 7 * objects['cider'] + 10 * objects['horn'] <= 15 class ValueObjective(ObjectiveComponent): def define(self, objects): return 5 * objects['camera'] + 7 * objects['figurine'] + 2 * objects['cider'] + 10 * objects['horn']

Teraz możemy użyć tej samej definicji problemu i uruchomić polecenia:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results() print(prob.result_variables)

Powinieneś zobaczyć to w swoim wyniku:

 KnapsackProblem: Optimal objects[camera] 0.0 objects[figurine] 1.0 objects[cider] 0.0 objects[horn] 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'objects': {'camera': 0.0, 'figuring': 1.0, 'cider': 0.0, 'horn': 1.0}}

Zarządzanie wieloma ograniczeniami

Modele z jednym wiązaniem są stosunkowo rzadkie. Podczas pracy z wieloma ograniczeniami dobrze jest mieć wszystkie ograniczenia w jednym miejscu, aby można było je łatwo śledzić i zarządzać nimi. HorusLP czyni to naturalnym.

Załóżmy na przykład, że chcielibyśmy zobaczyć, jak zmieniłyby się wyniki, gdybyśmy zmusili modelkę do dodania aparatu do naszego plecaka. Zaimplementowalibyśmy dodatkowe ograniczenie i dodaliśmy je do naszej definicji problemu.

Wróć do modelu, który zaimplementowaliśmy w pierwszym samouczku. Dodaj następujące ograniczenie:

 class MustHaveItemConstraint(Constraint): def define(self, camera): return camera >= 1

Aby dodać ograniczenie do modelu, wystarczy dodać je do definicji problemu w następujący sposób:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, MustHaveItemConstraint # just add this line :) ] sense = MAXIMIZE

Uruchom problem i powinieneś zobaczyć następujące dane wyjściowe:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

Powinieneś zobaczyć nowe ograniczenie drukowane na standardowym wyjściu i zmienione optymalne wartości zmiennych.

Zarządzanie wiązaniami zależnymi i grupami wiązań

Ograniczenia są często ze sobą powiązane, ponieważ są od siebie zależne lub logicznie należą do tej samej grupy.

Na przykład, jeśli chcesz ustawić ograniczenie, aby ograniczyć sumę wartości bezwzględnych zestawu zmiennych, musisz najpierw określić ograniczenia, aby wyrazić relacje wartości bezwzględnych między zamierzonymi zmiennymi, a następnie określić granice wartości bezwzględnych. Czasami trzeba zastosować podobne ograniczenia do grupy zmiennych, aby wyrazić określoną relację między zmiennymi.

Aby wyrazić te grupowania, możemy użyć funkcji więzów zależnych naszych definicji ograniczeń. Aby zobaczyć, jak można użyć funkcji wiązania zależnego, zrefaktoryzuj ograniczenie SizeConstraint z poprzedniego problemu w następujący sposób:

 class SizeConstraint(Constraint): dependent_constraints = [MustHaveItemConstraint] def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

A teraz, aby sprawdzić, czy ograniczenia zależne są implementowane automatycznie, MustHaveItemConstraint z definicji problemu:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, ] sense = MAXIMIZE

I uruchom kod ponownie, a powinieneś zobaczyć następujące wyjście na standardowe wyjście:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

Wygląda na to, że zaimplementowano MustHaveItemConstraint ! Bardziej złożony przykład wykorzystania wiązania zależnego można znaleźć w przykładzie dotyczącym personelu na końcu samouczka.

Zarządzanie wieloma celami ważonymi

Często podczas opracowywania naszych algorytmów optymalizacyjnych napotkamy obiektywne wyrażenie złożone z wielu części. W ramach naszych eksperymentów możemy zmienić ważenie różnych obiektywnych komponentów, aby nakierować algorytm na pożądany wynik. CombinedObjective zapewnia czysty i prosty sposób na wyrażenie tego.

Załóżmy, że chcemy zmienić algorytm, aby wybrać figurkę i cydr. Zrefaktoryzujmy kod z poprzedniej sekcji, aby użyć CombinedObjective .

Najpierw zaimportuj klasę CombinedObjective w następujący sposób:

 from horuslp.core import CombinedObjective

Możemy wdrożyć niezależny komponent celu, taki jak:

 class ILoveCiderFigurineObjectiveComponent(ObjectiveComponent): def define(self, figurine, cider): return figurine + cider

Teraz możemy połączyć cel wartości i cel cydru/figurki, implementując CombinedObjective :

 class Combined(CombinedObjective): objectives = [ (ILoveCiderFigurineObjectiveComponent, 2), # first argument is the objective, second argument is the weight (ValueObjectiveComponent, 1) ]

Teraz zmieńmy definicję problemu w ten sposób:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = Combined constraints = [SizeConstraint] sense = MAXIMIZE

Uruchom problem i powinieneś zobaczyć następujące dane wyjściowe:

 KnapsackProblem: Optimal camera 1.0 figurine 1.0 cider 1.0 horn 0.0 Combined: 18.00 ILoveCiderFigurineObjectiveComponent: 2.00 * 2 ValueObjectiveComponent: 14.00 * 1 SizeConstraint: 13.00 MustHaveItemConstraint: 1.00

Wynik przedstawi łączną wartość celu, wartość każdego z komponentów celu, wagę i oczywiście wartość wszystkich ograniczeń.

Znajdowanie niekompatybilnych ograniczeń

Opracowując algorytmy, często spotykamy się z niewykonalnymi modelami. Jeśli model jest złożony, ustalenie, dlaczego model nagle stał się niewykonalny, może być trudne. HorusLP ma przydatne narzędzie, które pomoże Ci w takich przypadkach.

Załóżmy, że dodaliśmy ograniczenia i otrzymaliśmy następujący zestaw ograniczeń:

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 class SizeConstraint2(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 20 class MustHaveItemConstraint(Constraint): def define(self, cider): return cider >= 1 class IncompatibleConstraint1(Constraint): def define(self, camera): return camera >= 1 class IncompatibleConstraint2(Constraint): def define(self, camera): return camera <= 0

Mamy kilka ograniczeń dotyczących całkowitego rozmiaru przedmiotów w plecaku, ograniczenie wymagające, aby cydr musiał znajdować się w plecaku oraz niezgodny zestaw ograniczeń, które wymagają, aby kamera była zarówno w plecaku, jak i poza nim. (Oczywiście w rzeczywistym algorytmie ograniczenia zwykle nie są tak oczywiste i obejmują złożone relacje zmiennych i ograniczenia).

Załóżmy również, że ograniczenia są pogrupowane w następujący sposób, co może utrudniać wykrywanie:

 class CombinedConstraints1(Constraint): dependent_constraints = [SizeConstraint2, IncompatibleConstraint1] class CombinedConstraints2(Constraint): dependent_constraints = [SizeConstraint, IncompatibleConstraint2] # MustHaveItemConstraint will be included in the problem definition independently

Oto definicja problemu:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [CombinedConstraints1, CombinedConstraints2, MustHaveItemConstraint] sense = MAXIMIZE

Uruchom problem, a powinieneś zobaczyć następujący wynik:

 KnapsackProblem: Infeasible

O nie! Co robimy? Jeśli używamy większości narzędzi, musimy rozpocząć trudną sesję debugowania, w której jeden po drugim zawęzimy potencjalnie sprzeczne ograniczenia. Na szczęście HorusLP ma funkcję wyszukiwania niezgodności, która pomaga szybciej zawęzić niekompatybilne ograniczenia. Najprostszym sposobem użycia funkcji wyszukiwania niezgodności jest zmiana wywołania print_results w następujący sposób:

 prob.print_results(find_infeasible=True)

Proste! Uruchom kod, a teraz powinieneś zobaczyć następujące dane wyjściowe:

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('CombinedConstraints1', 'CombinedConstraints2')

Świetnie! Teraz ustaliliśmy, że MustHaveItemConstraint nie jest przyczyną niewykonalności i że przyczyną problemu są CombinedConstraints1 i CombinedConstraints2 .

To daje nam trochę informacji, ale pomiędzy połączonymi ograniczeniami są cztery ograniczenia zależne. Czy możemy określić, które z czterech ograniczeń są niezgodne? No tak. Zmodyfikuj swoje wywołanie print_results ten sposób:

 prob.print_results(find_infeasible=True, deep_infeasibility_search=True)

Spowoduje to, że wyszukiwanie niewykonalności rozszerzy zależne ograniczenia, dzięki czemu uzyskamy znacznie bardziej szczegółowy obraz tego, co powoduje niewykonalność. Uruchom to i powinieneś zobaczyć następujące dane wyjściowe:

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('IncompatibleConstraint1', 'IncompatibleConstraint2')

Chociaż kuszące jest, aby za każdym razem przeprowadzać głębokie wyszukiwanie niewykonalności, w przypadku realistycznych problemów z dużą liczbą całkowitych ograniczeń, głębokie wyszukiwanie niewykonalności może być bardzo zasobożerne i czasochłonne. Dlatego najlepiej jest przeprowadzić podstawowe wyszukiwanie niewykonalności, aby zawęzić możliwość i przeprowadzić głębokie wyszukiwanie niewykonalności w mniejszym podzbiorze po przeprowadzeniu ręcznego dochodzenia.

Algorytmy budowania z plików danych

Budując modele rzadko mamy luksus zakodowania na sztywno każdego ograniczenia i zmiennej. Często nasz program musi być na tyle elastyczny, aby zmieniać model w zależności od danych wejściowych. Załóżmy, że zamiast zakodowanych danych wejściowych chcielibyśmy zbudować nasz problem plecakowy z następującego JSON:

 { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 }

Możemy to zrobić, opierając się na wsparciu kwarg funkcji „definiuj”, którą implementujemy dla ograniczeń i celów.

Zmodyfikujmy kod z prostego problemu plecakowego (problem, który zaimplementowaliśmy w sekcji 1 samouczka). Najpierw wstawmy do pliku ciąg JSON. Oczywiście normalnie byśmy to odczytali z zewnętrznego źródła, ale dla uproszczenia trzymajmy wszystko w jednym pliku. Dodaj następujące elementy do swojego kodu:

 JSON = ''' { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 } '''

Upewnijmy się również, że nasz program będzie w stanie go przeanalizować. Dodaj następujące informacje do swoich instrukcji importu:

 Import json

Teraz zmodyfikujmy nasz kod konfiguracji zmiennej w następujący sposób:

 mip_cfg = json.loads(JSON) class KnapsackVariables(VariableManager): vars = [ BinaryVariable(i['name']) for i in mip_cfg['items'] ]

Spowoduje to zdefiniowanie zmiennej dla każdego elementu w JSON i odpowiednią nazwę.

Zmieńmy ograniczenia i definicje celu w następujący sposób:

 class CapacityConstraint(Constraint): def define(self, **kwargs): item_dict = {i['name']: i['weight'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs) <= mip_cfg['capacity'] class ValueObjective(ObjectiveComponent): def define(self, **kwargs): item_dict = {i['name']: i['value'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs)

Pytając o **kwargs zamiast o konkretne zmienne, funkcja define pobiera słownik zawierający wszystkie zmienne według nazwy. Funkcja definicji ograniczenia może wtedy uzyskać dostęp do zmiennych ze słownika.

Uwaga: W przypadku grup zmiennych będzie to słownik zagnieżdżony, w którym pierwszy poziom to nazwa grupy, a drugi poziom to nazwa zmiennej.

Reszta jest całkiem prosta:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

Uruchom ten program i powinieneś zobaczyć następujące dane wyjściowe:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00

Definiowanie niestandardowych metryk w HorusLP

Czasami, zarówno do celów debugowania, jak i raportowania, tworzymy niestandardowe metryki, które nie są wyrażane bezpośrednio w celu lub jako ograniczenie. HorusLP ma funkcję ułatwiającą określanie niestandardowych metryk.

Załóżmy, że chcielibyśmy śledzić, ile owoców model z naszej poprzedniej sekcji wkładał do plecaka. Aby to śledzić, możemy zdefiniować niestandardowe metryki. Zacznijmy od zaimportowania klasy bazowej Metrics:

 From horuslp.core import Metric

Teraz zdefiniujmy metrykę niestandardową:

 class NumFruits(Metric): name = "Number of Fruits" def define(self, apple, banana): return apple + banana

Jak widać, zdefiniowany interfejs wygląda bardzo podobnie do interfejsów klasy ograniczenia i komponentu obiektywnego. Jeśli do tej pory postępowałeś zgodnie z samouczkiem, powinien on być ci dość znajomy.

Teraz musimy dodać metrykę do definicji problemu. Interfejs tutaj ponownie jest bardzo podobny do definicji ograniczenia:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective metrics = [NumFruits] sense = MAXIMIZE

Uruchom to i powinieneś zobaczyć następujące dane wyjściowe:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00 Number of Fruits: 1.00

Możesz zobaczyć liczbę owoców wydrukowaną na dole.

Praca nad bardziej złożonym problemem: dwa plecaki

Przeanalizujmy nieco bardziej złożony przykład. Załóżmy, że zamiast pojedynczego plecaka mamy torbę i walizkę. Posiadamy również dwie klasy przedmiotów, trwałe i delikatne. Walizka, będąc bardziej ochronną, może pomieścić zarówno delikatne, jak i trwałe towary. Z drugiej strony torba może pomieścić tylko towary trwałe. Załóżmy również, że dane dotyczące pozycji są podane w następującym formacie JSON:

 { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 }

Zobaczmy, jak to zmieni model. Zacznijmy od czystej planszy, ponieważ model będzie zupełnie inny. Zacznij od konfiguracji problemu:

 import json from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, Metric, ObjectiveComponent from horuslp.core.constants import MAXIMIZE JSON = ''' { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 } ''' mip_cfg = json.loads(JSON)

Teraz skonfigurujmy zmienne. Skonfigurujemy zmienną binarną dla każdej możliwej kombinacji pozycji/pojemnika.

 class KnapsackVariables(VariableManager): vars = [ # suitcase can hold both fragile and durable goods BinaryVariableGroup('suitcase_f', [i['name'] for i in mip_cfg['fragile']]), BinaryVariableGroup('suitcase_d', [i['name'] for i in mip_cfg['durable']]), # bag can only hold durable goods. BinaryVariableGroup('bag_d', [i['name'] for i in mip_cfg['durable']]) ]

Teraz chcemy wprowadzić ograniczenia wagowe zarówno dla walizki, jak i torby.

 class SuitcaseCapacityConstraint(Constraint): def define(self, suitcase_d, suitcase_f): fragile_weight = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_weight = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_weight + durable_weight <= mip_cfg['suitcase_capacity'] class BagCapacityConstraint(Constraint): def define(self, bag_d): durable_weight = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return durable_weight <= mip_cfg['bag_capacity']

Teraz musimy zaimplementować nieco bardziej złożone ograniczenie — ograniczenie, które zapewnia, że ​​przedmiot nie trafi zarówno do walizki, jak i torby — to znaczy, jeśli zmienna „w walizce” wynosi 1, to „w torbie” zmienna musi wynosić zero i na odwrót. Oczywiście chcemy upewnić się, że zezwolimy również na przypadki, w których przedmiot nie znajdzie się w żadnym z kontenerów.

Aby dodać to ograniczenie, musimy wykonać iterację po wszystkich elementach trwałych, znaleźć zmienną „w walizce” i zmienną „w torbie” i stwierdzić, że suma tych zmiennych jest mniejsza niż 1.

W HorusLP możemy dość łatwo dynamicznie definiować więzy zależne:

 class UniquenessConstraints(Constraint): def __init__(self): super(UniquenessConstraints, self).__init__() # call the dependent constraint builder function for every durable item, and push them into dependent constraints. dependent_constraints = [self.define_uniqueness_constraint(item) for item in mip_cfg['durable']] self.dependent_constraints = dependent_constraints def define_uniqueness_constraint(self, item): # classes are first-class objects in python, so we can define a class within this function and return it class UQConstraint(Constraint): # we name the constraint based on the item this is for, so that debugging is easier. name = "Uniqueness_%s" % item['name'] def define(self, suitcase_d, bag_d): # the define function can access the variables much in the same way as other functions return suitcase_d[item['name']] + bag_d[item['name']] <= 1 return UQConstraint

Teraz, gdy ograniczenia są zdefiniowane, zbudujmy cel. Celem jest prosta suma wszystkich wartości, które otrzymujemy ze wszystkich przedmiotów znajdujących się w pojemnikach. Zatem:

 class TotalValueObjective(ObjectiveComponent): def define(self, suitcase_f, suitcase_d, bag_d): fragile_value = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_value_s = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) durable_value_d = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_value + durable_value_s + durable_value_d

Zdefiniujmy również kilka niestandardowych metryk, abyśmy mogli na pierwszy rzut oka zobaczyć, ile wagi zostało włożone do torby i walizki, a także ile wagi walizki pochodziło z towarów trwałych i delikatnych:

 class SuitcaseFragileWeightMetric(Metric): def define(self, suitcase_f): return sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) class SuitcaseDurableWeightMetric(Metric): def define(self, suitcase_d): return sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) class BagWeightMetric(Metric): def define(self, bag_d): return sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']])

Teraz mamy gotowe wszystkie elementy, stwórzmy wystąpienie problemu i uruchommy model:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [SuitcaseCapacityConstraint, BagCapacityConstraint, UniquenessConstraints] objective = TotalValueObjective metrics = [SuitcaseDurableValueMetric, SuitcaseFragileValueMetric, BagValueMetric] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

Uruchom to, a powinieneś zobaczyć następujące dane wyjściowe na swoim stdout:

 KnapsackProblem: Optimal suitcase_f[camera] 1.0 suitcase_f[glasses] 1.0 suitcase_f[apple] 1.0 suitcase_f[pear] 0.0 suitcase_f[banana] 1.0 suitcase_d[figurine] 0.0 suitcase_d[horn] 0.0 suitcase_d[leatherman] 0.0 bag_d[figurine] 1.0 bag_d[horn] 1.0 bag_d[leatherman] 1.0 TotalValueObjective: 32.00 SuitcaseCapacityConstraint: 15.00 BagCapacityConstraint: 17.00 Uniqueness_figurine: 1.00 Uniqueness_horn: 1.00 Uniqueness_leatherman: 1.00 SuitcaseDurableWeightMetric: 0.00 SuitcaseFragileWeightMetric: 15.00 BagWeightMetric: 17.00

Tak więc aparat, okulary, jabłko i banan trafiają do walizki w sumie 15 jednostek wagi, figurka, róg i rzemieślnik trafiają do torby, łącznie 17 jednostek wagi. Łączna wartość towaru wynosi 32 jednostki wartości. Co ciekawe, żaden z dóbr trwałych nie trafił do walizki, najprawdopodobniej dlatego, że torba miała wystarczającą pojemność, aby pomieścić wszystkie dobra trwałe.

Większy i bardziej realistyczny scenariusz: problem kadrowy

Jeśli dotarłeś tak daleko w naszym samouczku HorusLP, gratulacje! Masz teraz dobry pomysł, jak korzystać z HorusLP.

Jednak wszystkie przykłady, nad którymi pracowaliśmy, były do ​​tej pory permutacjami problemu plecakowego, a niektóre wymagania i parametry są nieco nierealistyczne. Przeanalizujmy jeszcze jeden problem, aby zobaczyć, jak HorusLP może rozwiązać bardziej realistyczny problem. Zajmiemy się problemem kadrowym przedstawionym w drugiej połowie mojego poprzedniego artykułu w Toptal.

W trosce o czas, przejdziemy od razu do ostatecznej wersji modelu (z konfliktami osobistymi, przepisami pracy i dodatkami dla pracowników tymczasowych), ale implementacja początkowego prostszego modelu jest również dostępna na GitHubie.

Zacznijmy więc od skonfigurowania problemu:

 from horuslp.core.Variables import BinaryVariableGroup, IntegerVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent, CombinedObjective from horuslp.core.constants import MINIMIZE shift_requirements = [1, 4, 3, 5, 2] # the number of workers we need to staff for each shift # the availability and pay rates of each of the employees workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } } # the following people can't work together, sadly. ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } # Dothraki Staffing Corp will provide us with expensive temp workers DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Zdefiniujmy teraz zmienne, które w tym przypadku byłyby zmiennymi binarnymi określającymi, czy pracownik powinien pracować na swojej zmianie, oraz zmiennymi całkowitymi określającymi, ile dothraków zatrudnimy na każdą zmianę:

 class StaffingVariables(VariableManager): vars = [] def __init__(self): # like dependent constraints, we can dynamically define variables in the init function super(StaffingVariables, self).__init__() # regular workers varkeys = [] for employee, availability_info in workers.items(): for shift in availability_info['availability']: varkeys.append((employee, shift)) self.vars.append(BinaryVariableGroup('employee_shifts', varkeys)) # dothrakis dothraki_keys = [i for i in range(len(shift_requirements))] self.vars.append(IntegerVariableGroup('dothraki_workers', dothraki_keys, 0, DOTHRAKI_COST))

Teraz zaimplementujmy ograniczenie, które wymaga od nas wystarczającej liczby pracowników na każdą zmianę:

 class SufficientStaffingConstraint(Constraint): # we need to staff people sufficiently dependent_constraints = [] def __init__(self): super(SufficientStaffingConstraint, self).__init__() for shift_num, shift_req in enumerate(shift_requirements): self.dependent_constraints.append(self.build_shift_constraint(shift_num, shift_req)) def build_shift_constraint(self, sn, sr): class ShiftConstraint(Constraint): name = "shift_requirement_%d" % sn def define(self, employee_shifts, dothraki_workers): variables = [val for key, val in employee_shifts.items() if key[1] == sn] variables.append(dothraki_workers[sn]) return sum(variables) >= sr return ShiftConstraint

Teraz musimy wprowadzić ograniczenia uniemożliwiające poszczególnym osobom współpracę:

 class PersonalConflictsConstraint(Constraint): # some people can't work together dependent_constraints = [] def __init__(self): super(PersonalConflictsConstraint, self).__init__() for person_1, person_2 in ban_list: for shift in range(len(shift_requirements)): self.dependent_constraints.append(self.build_conflict_constraint(person_1, person_2, shift)) def build_conflict_constraint(self, p1, p2, s): class ConflictConstraint(Constraint): name = "Conflict_%s_%s_%d" % (p1, p2, s) def define(self, employee_shifts): if (p1, s) in employee_shifts and (p2, s) in employee_shifts: return employee_shifts[p1, s] + employee_shifts[p2, s] <= 1 return True # returning true will make the constraint do nothing return ConflictConstraint

And finally the labor standards constraint. We'll implement this one slightly differently for demonstrative purposes:

 class LaborStandardsConstraint(Constraint): # we can make someone work more than two shifts a day. dependent_constraints = [] def __init__(self): super(LaborStandardsConstraint, self).__init__() for worker in workers.keys(): # we don't need a constraint builder function, but in those circumstances # we need to set the needed values as class variables and refer to them # via the self keyword due to how python's closure system works class LaborConstraint(Constraint): # we can't use worker directly! wk = worker name = "labor_standard_%s" % worker def define(self, employee_shifts): # we need to access the worker using self. Change self.wk to worker to see # why we need to do this worker_vars = [var for key, var in employee_shifts.items() if key[0] == self.wk] return sum(worker_vars) <= 2 self.dependent_constraints.append(LaborConstraint)

And now let's set up the objectives. The dothraki cost and regular employee costs are calculated very differently, so we'll put them in separate objective components:

 class CostObjective(ObjectiveComponent): # this is the cost function for all the named workers def define(self, employee_shifts, dothraki_workers): costs = [ workers[key[0]]['cost'] * var for key, var in employee_shifts.items() ] return sum(costs) class DothrakiCostObjective(ObjectiveComponent): # don't forget the Dothrakis def define(self, dothraki_workers): dothraki_costs = [ dothraki_workers[sn] * DOTHRAKI_COST for sn in dothraki_workers ] return sum(dothraki_costs) class TotalCostObjective(CombinedObjective): objectives = [ (CostObjective, 1), (DothrakiCostObjective, 1) ]

And now we can define and run the problem:

 class StaffingProblem(Problem): variables = StaffingVariables objective = TotalCostObjective constraints = [SufficientStaffingConstraint, PersonalConflictsConstraint, LaborStandardsConstraint] sense = MINIMIZE # we're minimizing this time, not maximizing. if __name__ == '__main__': prob = StaffingProblem() prob.solve() prob.print_results()

Run the script and you should see the following:

 StaffingProblem: Optimal employee_shifts[('Melisandre', 0)] 0.0 employee_shifts[('Melisandre', 1)] 1.0 employee_shifts[('Melisandre', 4)] 1.0 employee_shifts[('Bran', 1)] 0.0 employee_shifts[('Bran', 2)] 1.0 employee_shifts[('Bran', 3)] 1.0 employee_shifts[('Bran', 4)] 0.0 employee_shifts[('Cersei', 2)] 0.0 employee_shifts[('Cersei', 3)] 0.0 employee_shifts[('Daenerys', 3)] 1.0 employee_shifts[('Daenerys', 4)] 0.0 employee_shifts[('Theon', 1)] 1.0 employee_shifts[('Theon', 3)] 1.0 employee_shifts[('Theon', 4)] 0.0 employee_shifts[('Jon', 0)] 0.0 employee_shifts[('Jon', 2)] 1.0 employee_shifts[('Jon', 4)] 0.0 employee_shifts[('Tyrion', 1)] 1.0 employee_shifts[('Tyrion', 3)] 1.0 employee_shifts[('Tyrion', 4)] 0.0 employee_shifts[('Jaime', 1)] 1.0 employee_shifts[('Jaime', 2)] 0.0 employee_shifts[('Jaime', 4)] 1.0 employee_shifts[('Arya', 0)] 1.0 employee_shifts[('Arya', 1)] 0.0 employee_shifts[('Arya', 3)] 1.0 dothraki_workers[0] 0.0 dothraki_workers[1] 0.0 dothraki_workers[2] 1.0 dothraki_workers[3] 0.0 dothraki_workers[4] 0.0 TotalCostObjective: 335.00 CostObjective: 290.00 * 1 DothrakiCostObjective: 45.00 * 1 shift_requirement_0: 1.00 shift_requirement_1: 4.00 shift_requirement_2: 3.00 shift_requirement_3: 5.00 shift_requirement_4: 2.00 Conflict_Jon_Cersei_2: 1.00 Conflict_Jon_Jaime_2: 1.00 Conflict_Jon_Jaime_4: 1.00 Conflict_Daenerys_Cersei_3: 1.00 Conflict_Daenerys_Jaime_4: 1.00 Conflict_Arya_Jaime_1: 1.00 Conflict_Arya_Cersei_3: 1.00 Conflict_Arya_Melisandre_0: 1.00 Conflict_Arya_Melisandre_1: 1.00 Conflict_Jaime_Cersei_2: 0.00 labor_standard_Melisandre: 2.00 labor_standard_Bran: 2.00 labor_standard_Cersei: 0.00 labor_standard_Daenerys: 1.00 labor_standard_Theon: 2.00 labor_standard_Jon: 1.00 labor_standard_Tyrion: 2.00 labor_standard_Jaime: 2.00 labor_standard_Arya: 2.00

If you compare this with the problem we implemented in the previous tutorial, you should see that the results match.

Zawijanie

Congratulations for making it through our first HorusLP tutorial! You're now a competent practitioner of HorusLP.

I hope that this article convinced you of the benefits of architecting your MIP models, and that you will make use of HorusLP in your coming projects. You can find the HorusLP source code, as well as the code for all the tutorials, on GitHub. Additional HorusLP documentation and a tutorial page will be added to GitHub very soon.

As HorusLP is a fairly new project, we would love to hear from you and incorporate your input. If you have any questions, comments, or suggestions, please drop me a line either through Toptal or using the contact information you can find on GitHub. I hope to hear from you soon!