HorusLP-Gurobi: Архитектура оптимизации высокого уровня для Gurobi

По мере того как технологии оптимизации становятся все более изощренными, коммерческие решатели начинают играть все более важную роль в отрасли. По сравнению с решателями с открытым исходным кодом коммерческие решения, как правило, имеют больше возможностей для решения сложных моделей оптимизации, таких как расширенное предварительное решение, теплый запуск и распределенное решение.

Одним из самых популярных коммерческих решателей на рынке является Gurobi, названный в честь соучредителей Зонгхао Гу, Эдварда Ротберга и Роберта Биксби, каждый из которых является пионером в области коммерческих решателей. В новейшей истории Гуроби участвовал во многих громких проектах по оптимизации, включая проект FCC по распределению пропускной способности и проект по перераспределению заключенных в тюрьме штата Пенсильвания.

Сегодня мы рассмотрим, как HorusLP, программный пакет, предоставляющий высокоуровневый декларативный интерфейс для оптимизационного моделирования, интегрируется с API Gurobi, чтобы предоставить пользователям интуитивно понятный опыт моделирования при использовании самых передовых функций Gurobi.

Оптимизация: быстрое освежение знаний

Для тех, кто не знаком с оптимизацией или исследованием операций, оптимизация относится к набору математических методов, которые находят оптимальные значения переменных в системе уравнений с учетом системы ограничений. Если приведенное выше предложение звучит немного сухо, возможно, пример поможет проиллюстрировать его.

Предположим, у вас есть рюкзак грузоподъемностью 15 фунтов. Перед вами несколько предметов, каждый из которых имеет определенный вес и денежную стоимость:

1. Камера: вес 2 фунта, стоимость 5 долларов.
2. Фигурка: вес 4 фунта, стоимость 7 долларов.
3. Сидр: вес 7 фунтов, стоимость 2 доллара.
4. Рог: вес 10 фунтов, стоимость 10 долларов.

Вы хотите выбрать предметы для размещения в рюкзаке таким образом, чтобы общий вес оставался ниже 15 фунтов, но ценность была максимальной. (Если вам нужно больше информации о том, почему мы кладем ценные предметы в рюкзак, вам рекомендуется использовать свое воображение для повествования. Хорошие повествования-кандидаты включают в себя спасение вещей от пожара и аукционы недвижимости… или некоторые гнусные действия, которые мы лучше не упоминать)

Мы можем сформулировать проблему как следующую задачу оптимизации:

 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

Как только мы сформулируем эту проблему, мы можем применить методы оптимизации, чтобы найти лучшие предметы для размещения в нашем рюкзаке. Вы можете найти пример решения в моих более ранних статьях о решении задач оптимизации с помощью Python и решении задач оптимизации с помощью основного API HorusLP.

Лежащая в основе математическая техника весьма увлекательна, но выходит за рамки этой статьи. Если вы хотите узнать больше, я рекомендую посмотреть здесь и здесь, оба любезно предоставлены Gurobi.

Гуроби

В то время как самые ранние задачи оптимизации решались группами математиков, работающих с калькуляторами, сегодня большинство задач оптимизации решается с помощью специализированного программного обеспечения, называемого решателями. Хотя большинство решателей, как правило, способны находить решения большинства хорошо сформулированных задач линейного и целочисленного программирования, некоторые решатели обладают гораздо большими возможностями, чем другие. Они могут решать классы проблем, которые не могут решить другие, решать проблемы быстрее, применяя передовую математику, или решать большие и сложные задачи, используя распределенные компьютеры. Наиболее продвинутые функции обычно предоставляются в коммерческих решателях, разработанных и поддерживаемых компаниями, специализирующимися на создании самых быстрых и сложных решателей.

Gurobi является одним из лидеров на рынке коммерческих решателей, используемых большими сегментами сообщества оптимизаторов, включая правительства, академические учреждения и компании, работающие в различных отраслях, от финансов до логистики. С точки зрения скорости, gurobi стабильно превосходит несколько тестов, используемых для оценки коммерческих и открытых решателей.

Gurobi также поставляется с мощным Python API, который позволяет вам создавать модели из Python. Эта функция дает разработчикам моделей доступ ко всем полезным библиотекам обработки данных Python во время построения модели, что очень помогает в их процессе. В качестве демонстрации Python API gurobi, вот как можно смоделировать задачу о рюкзаке:

 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)

Запуск примера даст вам следующий вывод:

 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 — это библиотека моделирования оптимизации, созданная на основе опыта разработки алгоритмов оптимизации. В имеющихся в настоящее время библиотеках моделирования отсутствуют инструменты, необходимые для работы со сложными, многогранными проблемами, с которыми обычно сталкиваются коммерческие приложения для исследования операций.

Хотя большинство библиотек оптимизации предлагают низкоуровневый императивный интерфейс, по мере усложнения моделей оптимизации требуются более совершенные инструменты для управления сложностью. HorusLP — это библиотека, которая предоставляет инструменты более высокого уровня для управления этими сложностями. HorusLP также предоставляет мощные инструменты отладки и отчетности, которые позволяют ускорить разработку и итерацию.

По своей сути HorusLP представляет собой объектно-ориентированную библиотеку, которая обеспечивает столь необходимую архитектуру вокруг моделей оптимизации. Используя объектно-ориентированный синтаксис Python, библиотека HorusLP предоставляет структуру, вокруг которой можно оптимизировать модели оптимизации. В результате получается несвязанная, модульная и легко читаемая кодовая база.

Если вам нужно более подробное введение в основную библиотеку HorusLP с примерами кода, вы можете найти учебник здесь.

Интеграция HorusLP-Gurobi

Хотя основной API HorusLP предоставляет удобный высокоуровневый API для построения моделей оптимизации, он построен на PuLP, который, хотя и может использовать Gurobi в качестве решателя, не имеет доступа к некоторым более продвинутым возможностям Gurobi.

HorusLP-Gurobi — это версия HorusLP API, созданная с использованием Gurobi Python API. Это дает пользователю прямой доступ к расширенным функциям Gurobi, сохраняя при этом согласованность API HorusLP.

Одной из ключевых идей, лежащих в основе разработки HorusLP-Gurobi, была согласованность с основным API HorusLP. Сохраняя последовательную минималистскую структуру HorusLP, пользователь решателя с открытым исходным кодом может легко перейти к использованию Gurobi, установив Gurobi API и переключив операторы импорта.

Для простых моделей модели на основе HorusLP потребуют больше строк кода, чем просто императивное использование Python API. Однако по мере продолжения процесса разработки и усложнения моделей объектно-ориентированный и декларативный дизайн HorusLP API упростит отладку и разработку. Ориентация на объект также сделает модель более удобочитаемой, поскольку определение модели централизует и четко определяет цели, ограничения, переменные и т. д.

Без дальнейших церемоний, давайте погрузимся в некоторые примеры кода!

Примеры кода

Базовый API HorusLP

Поскольку HorusLP-Gurobi поддерживает согласованность API, код из основного руководства HorusLP можно портировать простым изменением импорта. Однако, чтобы использовать HoruLP-Gurobi, вам необходимо убедиться, что у вас установлены оптимизатор Gurobi и интерфейс Gurobi Python. Вы можете получить Гуроби, связавшись с ними здесь.

Как только вы установите Gurobi, мы можем начать программировать с помощью HorusLP-Gurobi! Начнем с установки необходимого пакета:

 Pip install horuslp horuslp-gurobi

После завершения установки мы можем начать использовать HorusLP-Gurobi! Вспомните пример задачи о рюкзаке из предыдущего примера. Мы можем использовать HorusLP-Gurobi для моделирования проблемы следующим образом:

Сначала импортируйте соответствующие библиотеки.

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

Определите некоторые переменные.

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

Теперь мы можем определить ограничения, используя класс ограничений.

 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

Затем мы можем реализовать цель аналогичным образом.

 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

И, наконец, мы можем определить проблему.

 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

И мы создаем экземпляр проблемы и вызываем функцию решения. Вот где происходит волшебство.

 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

Запустите код, и вы должны увидеть следующий вывод:

 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}

Первая часть — это решатель Gurobi, а вторая часть — результат работы HorusLP. Как видите, алгоритм рекомендует взять статуэтку и рог, в результате чего получается 14 фунтов предметов стоимостью 17 долларов.

Одним из преимуществ использования HorusLP с Gurobi является то, что вы получаете много информации «бесплатно». Большая часть информации, которую обычно требуется просматривать во время разработки, например значение каждой переменной, конечное целевое значение и значения ограничений, автоматически вычисляется и выводится в удобном для чтения формате.

Если вы читали предыдущую статью о ядре HorusLP, то заметили, что это практически тот же самый API. Чтобы сохранить простоту API, интерфейсы ядра HorusLP и HorsLP-Gurobi идентичны, а различия между решателями абстрагируются в реализации суперкласса.

Таким образом, мы оставим знакомство с HorusLP на этом простом примере; более сложные примеры, демонстрирующие расширенные возможности HorusLP, можно найти в предыдущей статье.

Особенности Гуроби

Gurobi предоставляет множество дополнительных функций для решения сложных задач. Большинство функций доступны через объект Model. Чтобы обеспечить полную совместимость с API Gurobi, объект модели легко доступен из класса задачи как model .

Например, если вы хотите написать MPS-файл модели рюкзака, в Gurobi вы можете написать что-то вроде m.write('knapsack.mps') . При использовании HorusLP-Gurobi вы можете просто:

 # 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!

И вы должны увидеть файл MPS в своем рабочем каталоге.

Вы можете использовать этот интерфейс для доступа к расширенным функциям Gurobi, таким как расчет IIS, создание обратных вызовов или предоставление подсказок переменных.

Расширенные функции Gurobi к вашим услугам

Сегодня мы рассмотрели версию библиотеки HorusLP, построенную поверх Gurobi Python API. В дополнение к функциям отчетности и отладки ядра HorusLP теперь у вас есть доступ ко всем расширенным функциям Gurobi, легко доступным благодаря интеграции с Gurobi Python API.

Если вы являетесь текущим пользователем Gurobi или заинтересованы в оптимизации Gurobi, я надеюсь, что вы попробуете HorusLP! Вы можете найти примеры кода, внести предложения или внести свой вклад в HorusLP-Gurobi на GitHub.