HorusLP-Gurobi: Architektura optymalizacji wysokiego poziomu dla Gurobi

Ponieważ technologie optymalizacji stają się coraz bardziej wyrafinowane, komercyjne rozwiązania do rozwiązywania problemów zaczęły odgrywać coraz większą rolę w branży. W porównaniu do solwerów open-source, rozwiązania komercyjne mają zwykle więcej funkcji do rozwiązywania złożonych modeli optymalizacji, takich jak zaawansowane presolve, ciepły start i rozwiązywanie rozproszone.

Jednym z najpopularniejszych komercyjnych solverów na rynku jest Gurobi, nazwany na cześć współzałożycieli Zonghao Gu, Edwarda Rothberga i Roberta Bixby, z których każdy jest pionierem w komercyjnej przestrzeni solverów. Gurobi wspierał wiele głośnych projektów optymalizacyjnych w najnowszej historii, w tym projekt alokacji przepustowości FCC i projekt zmiany przydziału więźniów w więzieniu stanowym Pensylwanii.

Dzisiaj przyjrzymy się, jak HorusLP, pakiet oprogramowania, który zapewnia deklaratywny interfejs wysokiego poziomu do modelowania optymalizacyjnego, integruje się z interfejsem API Gurobi, aby zapewnić użytkownikom intuicyjne wrażenia z modelowania, jednocześnie wykorzystując najbardziej zaawansowane funkcje Gurobi.

Optymalizacja: szybkie przypomnienie

Dla tych, którzy nie są zaznajomieni z optymalizacją lub badaniami operacyjnymi, optymalizacja odnosi się do zbioru technik matematycznych, które znajdują optymalne wartości zmiennych w układzie równań podlegającym układowi ograniczeń. Jeśli powyższe zdanie brzmi trochę sucho, być może przykład pomoże to zilustrować.

Załóżmy, że masz plecak o nośności 15 funtów. Masz przed sobą kilka przedmiotów, każdy o określonej wadze i wartości pieniężnej:

1. Aparat: waga 2 funty, wartość 5 USD
2. Figurka: waga 4 funty, wartość 7 USD
3. Cydr: waga 7 funtów, wartość $2
4. Róg: waga 10 funtów, wartość 10 USD.

Chcesz tak wybrać przedmioty, które chcesz umieścić w swoim plecaku, aby całkowita waga pozostawała poniżej 15 funtów, ale wartość była zmaksymalizowana. (Jeśli potrzebujesz więcej kontekstu, dlaczego wkładamy wartościowe przedmioty do plecaka, zachęcamy do użycia wyobraźni w narracji. Dobre narracje kandydatów obejmują ratowanie rzeczy z pożaru i aukcji nieruchomości… lub niektórych nikczemnych działań, które wolałbym nie wspominać.)

Problem możemy sformułować jako następujący problem optymalizacyjny:

 Let // Each variable stands for whether we put the item into the knapsack Camera = {0, 1} Figurine = {0, 1} Cider = {0, 1} Horn = {0, 1} // Maximize dollar value Maximize 5 * camera + 7 * figurine + 2 * cider + 10 * horn // Weight must stay below 15 pounds 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Po sformułowaniu tego problemu możemy zastosować techniki optymalizacji, aby znaleźć najlepsze przedmioty do umieszczenia w naszym plecaku. Przykład rozwiązania można znaleźć w moich wcześniejszych artykułach na temat rozwiązywania problemów optymalizacyjnych za pomocą Pythona i rozwiązywania problemów optymalizacyjnych za pomocą rdzenia HorusLP API.

Podstawowa technika matematyczna jest dość fascynująca, ale wykracza poza zakres tego artykułu. Jeśli chcesz dowiedzieć się więcej, polecam zajrzeć tu i tutaj, dzięki uprzejmości Gurobi.

Gurobi

Podczas gdy najwcześniejsze problemy optymalizacyjne były rozwiązywane przez zespoły matematyków pracujących z kalkulatorami, większość dzisiejszych problemów optymalizacyjnych jest rozwiązywanych przy użyciu specjalistycznego oprogramowania zwanego solverami. Podczas gdy większość solverów jest w stanie znaleźć rozwiązania większości dobrze sformułowanych problemów programowania liniowego i całkowitoliczbowego, niektóre solvery są znacznie bardziej wydajne niż inne. Mogą rozwiązywać klasy problemów, których inni nie mogą rozwiązać, rozwiązywać problemy szybciej, stosując najnowocześniejszą matematykę, lub rozwiązywać duże, trudne problemy za pomocą rozproszonych komputerów. Najbardziej zaawansowane funkcje są zwykle dostępne w komercyjnych solwerach opracowanych i utrzymywanych przez firmy specjalizujące się w budowaniu najszybszych i najbardziej zaawansowanych solwerów.

Gurobi jest jednym z liderów na rynku komercyjnych solverów, z którego korzystają duże segmenty społeczności optymalizacyjnej, w tym rządy, instytucje akademickie i firmy działające w branżach od finansów po logistykę. Pod względem szybkości gurobi konsekwentnie przewyższa wyniki w kilku testach używanych do oceny rozwiązań komercyjnych i open source.

Gurobi jest również wyposażony w potężne API Pythona, które pozwala budować modele z Pythona. Ta funkcja daje modelarzom dostęp do wszystkich przydatnych bibliotek Pythona do manipulacji danymi podczas konstruowania modelu, co bardzo pomaga w ich procesie. Jako demonstrację gurobi Python API, oto jak możesz modelować problem z plecakiem:

 import gurobipy as gr m = gr.Model() camera = m.addVar(name='camera', vtype=gr.GRB.BINARY) figurine = m.addVar(name='figurine', vtype=gr.GRB.BINARY) cider = m.addVar(name='cider', vtype=gr.GRB.BINARY) horn = m.addVar(name='horn', vtype=gr.GRB.BINARY) m.addConstr(2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 , 'size constraint') m.setObjective(5 * camera + 7 * figurine + 2 * cider + 10 * horn, gr.GRB.MAXIMIZE) m.optimize() print(camera.x) print(figurine.x) print(horn.x) print(cider.x)

Uruchomienie przykładu da następujące dane wyjściowe:

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% -0.0 1.0 1.0 -0.0

HorusLP

HorusLP to biblioteka modelowania optymalizacji, która została zbudowana na doświadczeniach z opracowywaniem algorytmów optymalizacji. Obecnie dostępnym bibliotekom modelowania brakuje narzędzi niezbędnych do pracy z tego typu złożonymi, wieloaspektowymi problemami, z którymi spotykają się zwykle komercyjne zastosowania badań operacyjnych.

Podczas gdy większość bibliotek optymalizacyjnych oferuje interfejs imperatywny niskiego poziomu, w miarę jak modele optymalizacji stają się coraz bardziej złożone, do zarządzania złożonością potrzebne są lepsze narzędzia. HorusLP to biblioteka, która zapewnia narzędzia wyższego poziomu do zarządzania tymi złożonościami. HorusLP zapewnia również potężne narzędzia do debugowania i raportowania, które pozwalają na szybszy rozwój i iterację.

W swej istocie HorusLP jest biblioteką zorientowaną obiektowo, która zapewnia bardzo potrzebną architekturę wokół modeli optymalizacyjnych. Wykorzystując zorientowaną obiektowo składnię Pythona, biblioteka HorusLP zapewnia strukturę, wokół której można optymalizować modele optymalizacji. Rezultatem jest baza kodu, która jest oddzielona, ​​modułowa i łatwa do odczytania.

Jeśli chcesz uzyskać bardziej szczegółowe wprowadzenie do podstawowej biblioteki HorusLP z przykładami kodu, możesz znaleźć samouczek tutaj.

Integracja HorusLP-Gurobi

Chociaż podstawowe API HorusLP zapewnia wygodny, wysokopoziomowy interfejs API do budowania modeli optymalizacyjnych, jest ono oparte na PuLP, które chociaż może wykorzystywać Gurobi jako solwera, nie ma dostępu do niektórych bardziej zaawansowanych możliwości Gurobi.

HorusLP-Gurobi to wersja API HorusLP zbudowana przy użyciu API Pythona Gurobi. Pozwala to użytkownikowi na bezpośredni dostęp do zaawansowanych funkcji Gurobi, przy jednoczesnym zachowaniu spójności API HorusLP.

Jedną z kluczowych filozofii przyświecających rozwojowi HorusLP-Gurobi była spójność z podstawowym API HorusLP. Zachowując spójną minimalistyczną strukturę HorusLP, użytkownik rozwiązania open source może łatwo przejść do korzystania z Gurobi, instalując Gurobi API i przełączając instrukcje importu.

W przypadku prostych modeli modele oparte na HorusLP zajmą więcej linii kodu niż zwykłe użycie Pythonowego API. Jednak w miarę postępu procesu rozwoju i w miarę jak modele stają się coraz bardziej złożone, zorientowane obiektowo i deklaratywne projekty interfejsu API HorusLP ułatwią debugowanie i rozwój. Orientacja obiektowa sprawi również, że model będzie bardziej czytelny, ponieważ definicja modelu centralizuje i wyraźnie określa cele, ograniczenia i zmienne itp.

Bez zbędnych ceregieli zagłębimy się w kilka przykładów kodu!

Przykłady kodu

Podstawowe API HorusLP

Ponieważ HorusLP-Gurobi utrzymuje spójność API, kod z podstawowego samouczka HorusLP można przenieść z prostą zmianą importu. Aby jednak korzystać z HoruLP-Gurobi, musisz upewnić się, że masz zainstalowany optymalizator Gurobi i interfejs Gurobi's Python. Możesz dostać Gurobi, kontaktując się z nimi tutaj.

Po zainstalowaniu Gurobi możemy zacząć od kodowania z HorusLP-Gurobi! Zacznijmy od zainstalowania wymaganego pakietu:

 Pip install horuslp horuslp-gurobi

Po zakończeniu instalacji możemy zacząć korzystać z HorusLP-Gurobi! Przypomnij sobie wcześniejszy przykładowy problem z plecakiem. Możemy użyć HorusLP-Gurobi do modelowania problemu w następujący sposób:

Najpierw zaimportuj odpowiednie biblioteki.

 from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE

Zdefiniuj kilka zmiennych.

 class KnapsackVariables(VariableManager): # we define variables by declaring the “vars” class variable vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn')

Teraz możemy zdefiniować ograniczenia za pomocą klasy ograniczenia.

 class SizeConstraint(Constraint): # implement the 'define' function, the variables will get passed in by name def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Możemy następnie zrealizować cel w podobny sposób.

 class ValueObjective(ObjectiveComponent): # implement the define function and return the objective expression def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

I wreszcie możemy zdefiniować problem.

 class KnapsackProblem(Problem): # defining a problem using the Horus API is a matter of setting variables in the subclass variables = KnapsackVariables objective = ValueObjective # constraints is a list variable, since there can be multiple constraints,. constraints = [SizeConstraint] # make sure to set the sense! sense = MAXIMIZE

I tworzymy wystąpienie problemu i wywołujemy funkcję solve. Tutaj dzieje się magia.

 prob = KnapsackProblem() # instantiate prob.solve() # call the solve method prob.print_results() # optional: print the standard Horus debug report print(prob.result_variables) # optional: print the variable results as a list

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

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% 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}

Pierwsza część to solwer Gurobi, a druga część to dane wyjściowe z HorusLP. Jak widać, algorytm zaleca, abyśmy wzięli figurkę i róg, w wyniku czego otrzymujemy 14 funtów przedmiotów o wartości 17 USD.

Jedną z korzyści płynących z używania HorusLP z Gurobi jest to, że otrzymujesz wiele informacji „za darmo”. Wiele informacji, na które normalnie chciałoby się patrzeć podczas projektowania, takich jak wartość każdej zmiennej, ostateczna wartość celu i wartości ograniczeń, jest automatycznie obliczanych i wyprowadzanych w łatwym do odczytania formacie.

Jeśli przeczytałeś poprzedni artykuł o rdzeniu HorusLP, zauważysz, że jest to prawie dokładnie to samo API. Aby interfejs API był prosty, interfejsy rdzenia HorusLP i HorsLP-Gurobi są identyczne, z różnicami między solverami wyabstrahowanymi w implementacji superklasy.

Tak więc zostawimy wprowadzenie HorusLP do tego prostego przykładu; bardziej złożone przykłady demonstrujące zaawansowane funkcje HorusLP można znaleźć w poprzednim artykule.

Funkcje Gurobi

Gurobi zapewnia wiele zaawansowanych funkcji do rozwiązywania złożonych problemów. Większość funkcji jest dostępna za pośrednictwem obiektu Model. Aby umożliwić pełną kompatybilność z Gurobi API, obiekt modelu jest łatwo dostępny z klasy problemu jako model .

Na przykład, jeśli chcesz napisać plik MPS modelu plecakowego, w Gurobi możesz napisać coś w m.write('knapsack.mps') . Korzystając z HorusLP-Gurobi, możesz po prostu:

 # import the problem as usual from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE # define the constraint class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 # define the objectives as above class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn # define the variables used by the constraints and objectives class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') # define the problem as in the above example class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE # instantiate the problem. We don't need to call solve or print any reports. prob = KnapsackProblem() prob.model.write('knapsack.mps') # this is the only bit of new code!

Powinieneś zobaczyć plik MPS w swoim katalogu roboczym.

Możesz użyć tego interfejsu, aby uzyskać dostęp do zaawansowanych funkcji Gurobi, takich jak obliczanie IIS, tworzenie wywołań zwrotnych lub udzielanie wskazówek dotyczących zmiennych.

Zaawansowane funkcje Gurobi do Twoich usług

Dzisiaj przyjrzeliśmy się wersji biblioteki HorusLP zbudowanej na bazie API Gurobi Python. Oprócz funkcji raportowania i debugowania podstawowego HorusLP, masz teraz dostęp do wszystkich zaawansowanych funkcji Gurobi, dostępnych bezproblemowo dzięki integracji z Gurobi's Python API.

Jeśli jesteś aktualnym użytkownikiem Gurobi lub kimś zainteresowanym optymalizacją Gurobi, mam nadzieję, że wypróbujesz HorusLP! Możesz znaleźć przykładowy kod, zgłosić sugestie lub przyczynić się do HorusLP-Gurobi na GitHub.