[Python, Математика] PuLP-MiA: Мультииндексный аддон для PuLP (python-библиотека линейного программирования)
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Привет, Хабр! Сейчас будет мини-пост без единой строки кода для тех, кто имеет дело с многоиндексными задачами ЛП (линейное программирование) в Python и решает их при помощи библиотеки-порта PuLP… Это ненадолго :-)
При формализации задач ЛП довольно часто приходится иметь дело с многоиндексными переменными. При работе с задачами большой размерности — это, прямо скажем, привычное дело.
Взаимосвязи таких многоиндексных переменных в целевой функции (линейная форма — она же линейный критерий оптимизации) и ограничениях (в виде линейных равенств и неравенств) следует генерировать программно. При работе с PuLP (библотека-порт ЛП для Python) используют два основных подхода к такой генерации:
- Генерация матрицы А (матрица ограничений) с помощью генераторов списков Python явным образом. Например, так: Sudoku problem
- Генерация символьных переменных с привязкой к индексам через словари в неявном виде. Это может быть реализовано вручную через dict или же с помощью плагина для PuLP
Классическая задача ЛП практически любой размерности может быть легко формализована любым из данных способов, но при разработке новых структур ограничений (особенно, когда логика взаимосвязей переменных меняется усложняется, появляются новые по смыслу переменные, происходит отказ от каких-либо индексов или вводятся новые индексы, происходит агрегирование/декомпозиция групп переменных и др.) требуется легкое отслеживание многоиндексных переменных в самом программном коде Python, что напрямую отсутствует в вышеописанных подходах.
Для решения этой задачи и предлагается использовать аддон PuLP-MiA (ссылка на репозиторий с кратким описанием функционала).
Автор далек от мысли, что это решение всех проблем, возникающих при формализации и решении задач ЛП со сложной структурой ограничений, однако в многолетней практике (особенно, когда модификация происходит с большими временными перерывами) подход себя неплохо зарекомендовал, преимущественно за счет следующих удобств:
- О создание/привязка к существующим переменных происходит автоматически
- Явная связь имени переменной и ее индексов
- Имя переменной — произвольная строка
- Индексы — числовые значения
- Количество индексов — условно неограничено (индексов может вообще не быть)
- Результаты решения задачи ЛП выдаются в виде словаря, где ключи — ненулевые многоиндексные переменные (поведение можно изменить)
Возможно, кому-то сильно пригодится аддон в длительном исследовании операций. Лицензия MIT. Устанавливается традиционно через pip.
P.S. Для тех, кто дочитал, все-таки будет небольшой
пример формирования серии ограничений))
SPL
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. да-да, где-то глубоко под капотом живет обычный словарь :-)
===========
Источник:
habr.com
===========
Похожие новости:
- [Python, DevOps, Микросервисы] Конфигурируем сервис с помощью Vault и Pydantic
- [Python, Параллельное программирование, Разработка под Linux] Клиент-серверный IPC при помощи Python multiprocessing
- [Профессиональная литература] Книга «Простой Python. Современный стиль программирования. 2-е изд.»
- [Python] Типовые ошибки на собеседовании
- [Python, Машинное обучение, Искусственный интеллект, TensorFlow] Подборка статей о машинном обучении: кейсы, гайды и исследования за ноябрь 2020
- [Python, DevOps] Пушим метрики Prometheus с помощью pushgateway
- [Python, SQL] Немного SQL алхимии
- [Python] Python как компилируемый статически типизированный язык программирования
- [Математика, Игры и игровые приставки] В национальной лотерее ЮАР выпали цифры 5, 6, 7, 8, 9 и 10. Регулятор начал расследование
- [Python, Сетевые технологии, Беспроводные технологии] Небольшой рассказ, как мы модернизировали и расширяли сеть Wi-Fi до 14 000 точек доступа
Теги для поиска: #_python, #_matematika (Математика), #_pulp, #_linejnoe_programmirovanie (линейное программирование), #_multiindeksnost (мультииндексность), #_python, #_matematika (
Математика
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 14:44
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
Привет, Хабр! Сейчас будет мини-пост без единой строки кода для тех, кто имеет дело с многоиндексными задачами ЛП (линейное программирование) в Python и решает их при помощи библиотеки-порта PuLP… Это ненадолго :-) При формализации задач ЛП довольно часто приходится иметь дело с многоиндексными переменными. При работе с задачами большой размерности — это, прямо скажем, привычное дело. Взаимосвязи таких многоиндексных переменных в целевой функции (линейная форма — она же линейный критерий оптимизации) и ограничениях (в виде линейных равенств и неравенств) следует генерировать программно. При работе с PuLP (библотека-порт ЛП для Python) используют два основных подхода к такой генерации:
Классическая задача ЛП практически любой размерности может быть легко формализована любым из данных способов, но при разработке новых структур ограничений (особенно, когда логика взаимосвязей переменных меняется усложняется, появляются новые по смыслу переменные, происходит отказ от каких-либо индексов или вводятся новые индексы, происходит агрегирование/декомпозиция групп переменных и др.) требуется легкое отслеживание многоиндексных переменных в самом программном коде Python, что напрямую отсутствует в вышеописанных подходах. Для решения этой задачи и предлагается использовать аддон PuLP-MiA (ссылка на репозиторий с кратким описанием функционала). Автор далек от мысли, что это решение всех проблем, возникающих при формализации и решении задач ЛП со сложной структурой ограничений, однако в многолетней практике (особенно, когда модификация происходит с большими временными перерывами) подход себя неплохо зарекомендовал, преимущественно за счет следующих удобств:
Возможно, кому-то сильно пригодится аддон в длительном исследовании операций. Лицензия MIT. Устанавливается традиционно через pip. P.S. Для тех, кто дочитал, все-таки будет небольшой пример формирования серии ограничений))SPLfrom 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. да-да, где-то глубоко под капотом живет обычный словарь :-) =========== Источник: habr.com =========== Похожие новости:
Математика ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 14:44
Часовой пояс: UTC + 5