Разработка алгоритмов оптимизации с помощью HorusLP

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

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

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

Сегодня я хотел бы представить HorusLP, библиотеку оптимизации Python, которая помогает с архитектурой рабочих процессов разработки алгоритмов. Мы поговорим о проблемах, для решения которых предназначен инструмент, затем предоставим краткий обзор библиотеки Python и создадим несколько примеров алгоритмов оптимизации.

Проблемы, с которыми сталкиваются разработчики алгоритмов оптимизации

Одной из вечных проблем, с которыми сталкивается большинство разработчиков, является баланс между созданием удобного в сопровождении, эффективного, идиоматического программного обеспечения и выпуском продукта в рамках временных ограничений проекта. Независимо от того, работаете ли вы над браузерным приложением, веб-API или микрослужбой аутентификации пользователей, часто возникает компромисс между «правильным» и «быстрым» способами достижения ваших целей. Этот неотъемлемый компромисс становится более заметным по мере увеличения сложности продукта.

В большинстве дисциплин разработчик может облегчить эту проблему, выбрав фреймворк или библиотеку, которая помогает с архитектурой. В веб-интерфейсе многие разработчики выбирают React или Angular; в мире разработки API инженеры-программисты могут выбирать из Django, ASP.NET MVC или Play среди многих других. Однако, когда дело доходит до скромного разработчика алгоритмов оптимизации, очень мало архитектурных инструментов, помогающих справиться со сложностью архитектуры. Разработчику остается самостоятельно управлять переменными, ограничениями и различными целями. Более того, алгоритмы исследования операций, как правило, трудно поддаются самоанализу, что усугубляет проблему.

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

Типичные проблемы рабочего процесса оптимизации

Существует несколько основных источников сложности при разработке алгоритмов ИЛИ:

Сложность от переменных

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

Сложность из-за ограничений

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

Сложность от целей

• Объективные выражения могут стать громоздкими, если они состоят из нескольких компонентов. Это может усугубиться, если различные компоненты взвешены, и веса должны быть скорректированы в соответствии с бизнес-требованиями.

Сложность от отладки

• Нет простого способа увидеть результаты модели во время разработки. Разработчик должен явно напечатать новые переменные и значения ограничений, чтобы увидеть результаты. Это приводит к дублированию кода и замедлению разработки.
• Когда добавление ограничения приводит к тому, что модель становится недопустимой, может быть неочевидно, почему ограничение сделало модель недопустимой. Обычно разработчикам приходится устранять различные ограничения и искать несовместимость методом проб и ошибок.

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

Учебник HorusLP: алгоритм оптимизации и обзор API

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

Поскольку HorusLP основан на Python и PuLP, мы хотим установить их с помощью pip. Запустите в командной строке следующее:

 Pip install horuslp pulp

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

Библиотека HorusLP имеет очень простой декларативный API и очень мало шаблонов. Начнем с импорта необходимых классов и переменных:

 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

После того, как мы импортировали все переменные, давайте определим переменные, которые нам нужны для этой задачи. Мы делаем это, создавая подкласс диспетчера переменных и заполняя его двоичными переменными:

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

Теперь, когда переменные определены, давайте определим ограничения. Мы создаем ограничения, создавая подкласс основного класса ограничений и реализуя его функцию «определения».

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

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

После того, как ограничение реализовано, мы можем реализовать цель. Поскольку это простая цель, мы будем использовать ObjectiveComponent :

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

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

Теперь, когда переменные, ограничения и цели определены, давайте определим модель:

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

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

 prob = KnapsackProblem() prob.solve()

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

 prob.print_results() print(prob.result_variables)

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

 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}

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

И вот она, наша первая задача HorusLP примерно в 35 строк!

В следующих примерах мы рассмотрим некоторые более сложные функции библиотеки HorusLP.

Использование групп переменных

Иногда переменные связаны и принадлежат к логической группе. В случае задачи о рюкзаке все переменные можно поместить в группу объектов. Мы можем реорганизовать код для использования группы переменных. Обязательно сохраните код из предыдущего раздела, так как мы будем ссылаться на него в последующих руководствах!

Измените операторы импорта следующим образом:

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

Теперь нам также нужно изменить объявления переменных рюкзака следующим образом:

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

Первый аргумент — это имя группы переменных, вторая переменная — это список имен переменных в этой группе.

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

 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']

Теперь мы можем использовать то же определение задачи и запускать команды:

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

Вы должны увидеть это в своем выводе:

 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}}

Управление несколькими ограничениями

Модели с одним ограничением относительно редки. При работе с несколькими ограничениями хорошо иметь все ограничения в одном месте, чтобы их можно было легко отслеживать и управлять ими. HorusLP делает это естественным.

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

Вернитесь к модели, которую мы реализовали в первом уроке. Добавьте следующее ограничение:

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

Чтобы добавить ограничение в модель, нам просто нужно добавить его в определение задачи следующим образом:

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

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

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

Вы должны увидеть новое ограничение, напечатанное в стандартном выводе, и измененные оптимальные значения переменных.

Управление зависимыми ограничениями и группами ограничений

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

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

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

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

А теперь, чтобы проверить, что зависимые ограничения реализуются автоматически, давайте MustHaveItemConstraint из определения задачи:

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

И снова запустите код, и вы должны увидеть следующее в стандартном выводе:

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

Похоже, MustHaveItemConstraint реализован! Для более сложного примера того, как можно использовать зависимое ограничение, обратитесь к примеру с персоналом в конце учебника.

Управление несколькими взвешенными целями

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

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

Во-первых, импортируйте класс CombinedObjective следующим образом:

 from horuslp.core import CombinedObjective

Мы можем реализовать независимый объектный компонент следующим образом:

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

Теперь мы можем объединить цель ценности и цель сидра/статуэтки, реализуя CombinedObjective :

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

Теперь давайте изменим определение проблемы следующим образом:

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

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

 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

На выходе будет указано комбинированное целевое значение, значение каждого из компонентов цели, вес и, конечно же, значение всех ограничений.

Поиск несовместимых ограничений

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

Предположим, мы добавляли ограничения и получили следующий набор ограничений:

 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

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

Предположим также, что ограничения сгруппированы следующим образом, что, возможно, затрудняет обнаружение:

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

Вот определение проблемы:

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

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

 KnapsackProblem: Infeasible

о нет! Что мы делаем? Если мы используем большинство инструментов, мы должны приступить к сложному сеансу отладки, где мы сужаем потенциально конфликтующие ограничения одно за другим. К счастью, HorusLP имеет функцию поиска несовместимости, которая поможет вам быстрее сузить круг несовместимых ограничений. Самый простой способ использовать функцию поиска несовместимости — изменить вызов print_results таким образом:

 prob.print_results(find_infeasible=True)

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

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

Здорово! Теперь мы установили, что MustHaveItemConstraint не является причиной невыполнимости и что проблема связана с CombinedConstraints1 и CombinedConstraints2 .

Это дает нам некоторую информацию, но между комбинированными ограничениями есть четыре зависимых ограничения. Можем ли мы определить, какие из четырех ограничений несовместимы? Ну да. Измените вызов print_results образом:

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

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

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

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

Построение алгоритмов из файлов данных

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

Мы можем сделать это, полагаясь на поддержку kwargs функции «определить», которую мы реализуем для ограничений и целей.

Давайте изменим код простой задачи о рюкзаке (задача, которую мы реализовали в разделе 1 руководства). Во-первых, давайте поместим строку JSON в файл. Конечно, мы бы нормально прочитали его из внешнего источника, но для простоты давайте сохраним все в одном файле. Добавьте в свой код следующее:

 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 } '''

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

 Import json

Теперь давайте изменим наш код установки переменных следующим образом:

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

Это определит переменную для каждого из элементов в JSON и назовет ее соответствующим образом.

Давайте изменим ограничения и определения цели следующим образом:

 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)

Запрашивая **kwargs вместо конкретных переменных, функция define получает словарь, содержащий все переменные по именам. Затем функция определения ограничения может получить доступ к переменным из словаря.

Примечание. Для групп переменных это будет вложенный словарь, где первый уровень — это имя группы, а второй уровень — это имя переменной.

Остальное довольно просто:

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

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

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

Определение пользовательских показателей в HorusLP

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

Предположим, мы хотим отслеживать, сколько фруктов модель из нашего предыдущего раздела кладет в рюкзак. Чтобы отслеживать это, мы можем определить пользовательскую метрику. Начнем с импорта базового класса Metrics:

 From horuslp.core import Metric

Теперь давайте определим пользовательскую метрику:

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

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

Теперь нам нужно добавить метрику в определение проблемы. Интерфейс здесь снова очень похож на определение ограничения:

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

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

 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

Вы можете увидеть количество фруктов, напечатанных внизу.

Работа над более сложной задачей: два рюкзака

Давайте рассмотрим немного более сложный пример. Предположим, что вместо одного рюкзака у нас сумка и чемодан. У нас также есть два класса объектов, прочные и хрупкие. Чемодан, будучи более защитным, может вместить как хрупкие, так и товары длительного пользования. Сумка, с другой стороны, может содержать только товары длительного пользования. Предположим также, что данные для элементов представлены в следующем формате 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 }

Посмотрим, как это изменит модель. Начнем с чистого листа, так как модель будет совсем другой. Начните с постановки задачи:

 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)

Теперь настроим переменные. Мы настроим двоичную переменную для каждой возможной комбинации элемента/контейнера.

 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']]) ]

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

 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']

Теперь нам нужно реализовать немного более сложное ограничение — ограничение, которое гарантирует, что предмет не попадет и в чемодан, и в сумку, то есть если переменная «в чемодане» равна 1, то «в сумке» переменная должна быть равна нулю, и наоборот. Конечно, мы хотим убедиться, что разрешены случаи, когда элемент также не попадает ни в один из контейнеров.

Чтобы добавить это ограничение, нам нужно перебрать все предметы длительного пользования, найти переменные «в чемодане» и «в сумке» и утверждать, что сумма этих переменных меньше 1.

Мы можем легко динамически определять зависимые ограничения в HorusLP:

 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

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

 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

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

 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']])

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

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

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

 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

Таким образом, камера, очки, яблоко и банан помещаются в чемодан в общей сложности на 15 единиц веса, фигурка, рог и кожевник — в сумку на общую сумму 17 единиц веса. Общая стоимость товаров составляет 32 единицы стоимости. Интересно, что ни один из товаров длительного пользования не оказался в чемодане, скорее всего, потому, что сумка была достаточно вместительной, чтобы вместить все товары длительного пользования.

Более масштабный и реалистичный сценарий: кадровая проблема

Если вы дошли до этого места в нашем туториале HorusLP, поздравляем! Теперь у вас есть хорошее представление о том, как использовать HorusLP.

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

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

Итак, начнем с постановки задачи:

 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

Теперь давайте определим переменные, которые в данном случае будут бинарными переменными, определяющими, должен ли рабочий работать свою смену, и целочисленными переменными, определяющими, сколько дотракийцев мы нанимаем в каждую смену:

 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))

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

 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

Теперь нам нужно реализовать ограничения, запрещающие конкретным людям работать друг с другом:

 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.

Подведение итогов

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!