Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Привет, Хабр! Сейчас будет мини-пост без единой строки кода для тех, кто имеет дело с многоиндексными задачами ЛП (линейное программирование) в Python и решает их при помощи библиотеки-порта PuLP… Это ненадолго :-)
При формализации задач ЛП довольно часто приходится иметь дело с многоиндексными переменными. При работе с задачами большой размерности — это, прямо скажем, привычное дело.
Взаимосвязи таких многоиндексных переменных в целевой функции (линейная форма — она же линейный критерий оптимизации) и ограничениях (в виде линейных равенств и неравенств) следует генерировать программно. При работе с PuLP (библотека-порт ЛП для Python) используют два основных подхода к такой генерации:
Классическая задача ЛП практически любой размерности может быть легко формализована любым из данных способов, но при разработке новых структур ограничений (особенно, когда логика взаимосвязей переменных меняется усложняется, появляются новые по смыслу переменные, происходит отказ от каких-либо индексов или вводятся новые индексы, происходит агрегирование/декомпозиция групп переменных и др.) требуется легкое отслеживание многоиндексных переменных в самом программном коде Python, что напрямую отсутствует в вышеописанных подходах.
Для решения этой задачи и предлагается использовать аддон PuLP-MiA (ссылка на репозиторий с кратким описанием функционала).
Автор далек от мысли, что это решение всех проблем, возникающих при формализации и решении задач ЛП со сложной структурой ограничений, однако в многолетней практике (особенно, когда модификация происходит с большими временными перерывами) подход себя неплохо зарекомендовал, преимущественно за счет следующих удобств:
Возможно, кому-то сильно пригодится аддон в длительном исследовании операций. Лицензия MIT. Устанавливается традиционно через pip.
P.S. Для тех, кто дочитал, все-таки будет небольшой
(остальное см. в кратком описании аддона)
P.P.S. да-да, где-то глубоко под капотом живет обычный словарь :-)
При формализации задач ЛП довольно часто приходится иметь дело с многоиндексными переменными. При работе с задачами большой размерности — это, прямо скажем, привычное дело.
Взаимосвязи таких многоиндексных переменных в целевой функции (линейная форма — она же линейный критерий оптимизации) и ограничениях (в виде линейных равенств и неравенств) следует генерировать программно. При работе с PuLP (библотека-порт ЛП для Python) используют два основных подхода к такой генерации:
- Генерация матрицы А (матрица ограничений) с помощью генераторов списков Python явным образом. Например, так: Sudoku problem
- Генерация символьных переменных с привязкой к индексам через словари в неявном виде. Это может быть реализовано вручную через dict или же с помощью плагина для PuLP
Классическая задача ЛП практически любой размерности может быть легко формализована любым из данных способов, но при разработке новых структур ограничений (особенно, когда логика взаимосвязей переменных меняется усложняется, появляются новые по смыслу переменные, происходит отказ от каких-либо индексов или вводятся новые индексы, происходит агрегирование/декомпозиция групп переменных и др.) требуется легкое отслеживание многоиндексных переменных в самом программном коде Python, что напрямую отсутствует в вышеописанных подходах.
Для решения этой задачи и предлагается использовать аддон PuLP-MiA (ссылка на репозиторий с кратким описанием функционала).
Автор далек от мысли, что это решение всех проблем, возникающих при формализации и решении задач ЛП со сложной структурой ограничений, однако в многолетней практике (особенно, когда модификация происходит с большими временными перерывами) подход себя неплохо зарекомендовал, преимущественно за счет следующих удобств:
- О создание/привязка к существующим переменных происходит автоматически
- Явная связь имени переменной и ее индексов
- Имя переменной — произвольная строка
- Индексы — числовые значения
- Количество индексов — условно неограничено (индексов может вообще не быть)
- Результаты решения задачи ЛП выдаются в виде словаря, где ключи — ненулевые многоиндексные переменные (поведение можно изменить)
Возможно, кому-то сильно пригодится аддон в длительном исследовании операций. Лицензия MIT. Устанавливается традиционно через pip.
P.S. Для тех, кто дочитал, все-таки будет небольшой
пример формирования серии ограничений))
from itertools import product
from pulp_mia import Task, Constraint
i_set = list(range(5))
j_set = list(range(5))
m_set = list(range(2))
g_set = list(range(4))
s_set = list(range(5))
k_set = list(range(5))
task = Task(debug=True)
for i, m, g, s, k in product(i_set, m_set, g_set, s_set, k_set):
a_new = Constraint('<=')
for j in j_set:
a_new.setCoeff(('x', i, j, m, g, s, k), 1)
a_new.setBValue(1)
task.addConstraint(a_new)
print(task)
#TASK info:
# NAME: test-task
# SIZE: 5000 x 1000(остальное см. в кратком описании аддона)
P.P.S. да-да, где-то глубоко под капотом живет обычный словарь :-)
