Pyomo
Материал из MachineLearning.
(→Хроматическое число графа) |
(→Документация) |
||
(18 промежуточных версий не показаны.) | |||
Строка 121: | Строка 121: | ||
Примеры решений задач с помощью Pyomo можно найти на [http://www.pyomo.org/documentation странице документации]. Попробуйте запустить Jupyter Notebook в архиве, решающий транспортную проблему (transport.ipynb). | Примеры решений задач с помощью Pyomo можно найти на [http://www.pyomo.org/documentation странице документации]. Попробуйте запустить Jupyter Notebook в архиве, решающий транспортную проблему (transport.ipynb). | ||
+ | |||
+ | === Документация === | ||
+ | |||
+ | * [http://www.pyomo.org/documentation/ Онлайн-докуметнация] | ||
+ | |||
+ | * [https://vk.com/doc279781892_440088583 Pyomo-книга] | ||
=== Примеры === | === Примеры === | ||
+ | |||
+ | ==== Официальные примеры pyomo ==== | ||
+ | |||
+ | * [https://github.com/Pyomo/PyomoGallery/wiki PyomoGallery], | ||
+ | |||
+ | * Примеры из [https://github.com/Pyomo/pyomo/tree/master/examples репозитория] pyomo. | ||
+ | |||
==== Ensemble Clustering ==== | ==== Ensemble Clustering ==== | ||
В статье [http://www.sciencedirect.com/science/article/pii/S0031320315003039 Ensemble CLustering Using Factor Graphs] решается задача ensemble clustering, где промежуточным шагом является решение линейной бинарной задачи. Хотя авторы статьи применяют для этого метод, названный Belief Propagation, задачу можно решить и напрямую. Приведенный ниже код основан на примере Diet оригинального мануала [http://nbviewer.jupyter.org/github/Pyomo/PyomoGallery/blob/master/diet/DietProblem.ipynb]. | В статье [http://www.sciencedirect.com/science/article/pii/S0031320315003039 Ensemble CLustering Using Factor Graphs] решается задача ensemble clustering, где промежуточным шагом является решение линейной бинарной задачи. Хотя авторы статьи применяют для этого метод, названный Belief Propagation, задачу можно решить и напрямую. Приведенный ниже код основан на примере Diet оригинального мануала [http://nbviewer.jupyter.org/github/Pyomo/PyomoGallery/blob/master/diet/DietProblem.ipynb]. | ||
Строка 136: | Строка 149: | ||
Хроматическое число графа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. | Хроматическое число графа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. | ||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
Постановка задача на языке Pyomo: | Постановка задача на языке Pyomo: | ||
Строка 179: | Строка 184: | ||
==== Сеточная визуализация тематической модели ==== | ==== Сеточная визуализация тематической модели ==== | ||
+ | |||
+ | Данная задача естественно возникла в задаче визуализации тематической модели. Пусть имеется N тем, в i-й теме находится <tex>S_i</tex> документов. | ||
+ | Мы хотим отобразить документы в таблице размера <tex>W \times H</tex> так, чтобы каждый документ находился в одной клетке, и документы, относящиеся | ||
+ | к одной теме образовывали связную область. Кроме того, нужно чтобы некоторые темы оказались смежны. | ||
+ | |||
+ | Давайте представим, что документы одной темы притягиваются друг к другу. Тогда можно считать, что у пары документов одной темы есть энергия связи, которая тем больше, чем дальше они расположены друг от друга. Документы "смежных" тем тоже должны притягиваться, но с меньшей энергией. | ||
+ | |||
+ | Теперь задачу можно сформулировать в терминах задачи минимизации суммарной энергии связи. Подробное описание [https://github.com/fedimser/iad-discropt/blob/master/GridArranging/report/GridArranging.pdf здесь]. В модели pyomo ниже задача сведена к задаче квадратичного программирования. | ||
+ | |||
+ | <source lang = "python"> | ||
+ | |||
+ | from __future__ import division | ||
+ | from pyomo.environ import * | ||
+ | import numpy as np | ||
+ | |||
+ | model = AbstractModel() | ||
+ | |||
+ | model.N = Param() #The number of areas | ||
+ | model.W = Param() #Width | ||
+ | model.H = Param() #Height | ||
+ | |||
+ | model.Xrange = RangeSet(model.W) | ||
+ | model.Yrange = RangeSet(model.H) | ||
+ | model.Colors = RangeSet(model.N) | ||
+ | |||
+ | model.S = Param(model.Colors, domain = Integers) #Sizes of areas | ||
+ | model.A = Param(model.Colors, model.Colors) | ||
+ | |||
+ | model.Z = Var(model.Xrange, model.Yrange, model.Colors, domain=Binary) | ||
+ | |||
+ | def dist_init(model,x1,y1,x2,y2): | ||
+ | dx = x1 - x2 | ||
+ | dy = y1 - y2 | ||
+ | return sqrt(dx*dx + dy*dy) | ||
+ | |||
+ | model.dist = Param(model.Xrange, model.Yrange, model.Xrange, model.Yrange, initialize = dist_init) | ||
+ | |||
+ | |||
+ | |||
+ | # Objective - energy | ||
+ | def U_rule(model): | ||
+ | return sum(sum(sum(sum (model.dist[x1,y1,x2,y2]*sum(sum(model.A[i1,i2]*model.Z[x1,y1,i1]*model.Z[x2,y2,i2] for | ||
+ | i1 in model.Colors) for i2 in model.Colors) for y2 in model.Yrange) | ||
+ | for x2 in model.Xrange) for y1 in model.Yrange) for x1 in model.Xrange) | ||
+ | |||
+ | model.U = Objective(rule=U_rule, sense=minimize) | ||
+ | |||
+ | #Constraint: no collisions | ||
+ | def Correct_rule (model, x, y) : | ||
+ | return sum(model.Z[x,y,i] for i in model.Colors) <= 1 | ||
+ | |||
+ | model.Correct = Constraint (model.Xrange, model.Yrange, rule = Correct_rule) | ||
+ | |||
+ | #Constraint: square of i-th area is S[i] | ||
+ | def Square_rule(model, i): | ||
+ | return sum(sum(model.Z[x,y,i] for y in model.Yrange) for x in model.Xrange) == model.S[i] | ||
+ | model.Square = Constraint (model.Colors, rule = Square_rule) | ||
+ | </source> | ||
+ | [https://github.com/fedimser/iad-discropt/blob/master/GridArranging/report/GridArranging.pdf отчёт], [https://github.com/fedimser/iad-discropt/tree/master/GridArranging код] | ||
==== Soft Margin SVM ==== | ==== Soft Margin SVM ==== | ||
+ | |||
+ | [https://github.com/LLOleg/DO_374/blob/master/DO_Report%20(1).pdf Отчёт] | ||
+ | |||
==== Поиск топологических доменов ==== | ==== Поиск топологических доменов ==== | ||
Кластеризация невзвешенных неориентированных графов с помощью максимизации модулярности. | Кластеризация невзвешенных неориентированных графов с помощью максимизации модулярности. |
Текущая версия
Pyomo — открытая библиотека языка Python, созданная для создания и использования оптимизационных моделей.
Содержание |
Установка
macOS
Через pip
- Устанавливаем
pyomo
черезpip
. В зависимости от используемой версии интерпретатора Python можно заменитьpip
наpip2
илиpip3
.
pip install pyomo
- Устанавливаем пакет
pyomo.extras
pip install pyomo.extras
Через Anaconda
См. раздел Windows.
Windows
- Установить Anaconda
- Запустить Anaconda Prompt (интерфейс командной строки)
- Выполнить следующие команды. Устанавливаем пакеты
pyomo
,pyomo.extras
и решательglpk
.
Для этого используется сторонний репозиторий:
conda install --channel https://conda.anaconda.org/conda-forge pyomo conda install --channel https://conda.anaconda.org/conda-forge pyomo.extras conda install --channel https://conda.anaconda.org/conda-forge glpk
Linux
Предполагается, что вы используете Debian-based дистрибутив (например, Ubuntu).
Скачиваем отсюда: https://www.gnu.org/software/glpk/
cd ~/Downloads tar -xzf glpk-4.43.tar.gz cd ./glpk ./configure --prefix=/usr/local # see note [1] make sudo make install
Через pip
Здесь лучше использовать виртуальную среду, используя virtualenv
. В этом случае в скрипте внизу перед pip3
не нужно sudo
. Обратите внимание, что вы можете использовать pip2
, если хотите работать со второй версией языка.
sudo pip3 install pyomo sudo apt-get install glpk*
Через Anaconda
См. раздел Windows.
Тестирование установки
Установка солверов
Для решения поставленных задач Pyomo использует заданный в параметрах солвер. Решение задачи состоит из
.py
скрипта с определением модели и сущностей и .dat
– файл с данными (параметрами) в AMPL формате. Пример запуска решения задачи:
pyomo solve --solver=bonmin sol.py prod.dat
Существует некоторое множество солверов, которые может использовать Pyomo. Среди них есть свободно распространяемые (glpk, bonmin, ipopt, cbc) и проприетарные (minos, другие решатели AMPL). Для их использования их нужно устанавливать отдельно.
macOS
На macOS для установки ПО удобно использовать менеджер пакетов homebrew.
GLPK
- Скачиваем с сайта проекта последнюю версию.
- Устанавливаем (предполагается, что архив скачался в
~/Downloads
, а скачаный архив называетсяglpk-4.43.tar.gz
).
cd ~/Downloads tar -xzf glpk-4.43.tar.gz ./configure --prefix=/usr/local # see note [1] make sudo make install
- Проверяем, корректно ли установлен солвер (должен вывести путь до исполняемого файла).
which glpsol
bonmin
brew tap staticfloat/homebrew-juliadeps brew install bonmin
cbc
brew tap coin-or-tools/coinor brew install cbc
ipopt
brew tap Homebrew/homebrew-science brew install ipopt
lpsolve
brew tap Homebrew/homebrew-science brew install lp_solve
Примеры решений задач с помощью Pyomo можно найти на странице документации. Попробуйте запустить Jupyter Notebook в архиве, решающий транспортную проблему (transport.ipynb).
Документация
Примеры
Официальные примеры pyomo
- Примеры из репозитория pyomo.
Ensemble Clustering
В статье Ensemble CLustering Using Factor Graphs решается задача ensemble clustering, где промежуточным шагом является решение линейной бинарной задачи. Хотя авторы статьи применяют для этого метод, названный Belief Propagation, задачу можно решить и напрямую. Приведенный ниже код основан на примере Diet оригинального мануала [1].
Запуск производится командой
pyomo solve --solver=glpk ensemble_clustering.py ensemble_сlustering.dat
Хроматическое число графа
Хроматическое число графа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета.
Постановка задача на языке Pyomo:
from __future__ import division from pyomo.environ import * model = AbstractModel() model.N = Param() model.I = RangeSet(model.N) model.Adj = Param(model.I, model.I, domain = Binary) model.X = Var(model.I, domain=NonNegativeIntegers) # Objective def ChromaticNumber_rule(model): return sum(model.X[i] for i in model.I) model.ChromaticNumber = Objective(rule=ChromaticNumber_rule, sense=minimize) #Constraint: adjacent vertices are painted in different color def NeigboursDifferent_rule (model, i, j) : if model.Adj[i,j]==1: return abs(model.X[i] - model.X[j])>=1 else: return Constraint.Skip model.NeigboursDifferent = Constraint (model.I, model.I, rule = NeigboursDifferent_rule)
Сеточная визуализация тематической модели
Данная задача естественно возникла в задаче визуализации тематической модели. Пусть имеется N тем, в i-й теме находится документов.
Мы хотим отобразить документы в таблице размера
так, чтобы каждый документ находился в одной клетке, и документы, относящиеся
к одной теме образовывали связную область. Кроме того, нужно чтобы некоторые темы оказались смежны.
Давайте представим, что документы одной темы притягиваются друг к другу. Тогда можно считать, что у пары документов одной темы есть энергия связи, которая тем больше, чем дальше они расположены друг от друга. Документы "смежных" тем тоже должны притягиваться, но с меньшей энергией.
Теперь задачу можно сформулировать в терминах задачи минимизации суммарной энергии связи. Подробное описание здесь. В модели pyomo ниже задача сведена к задаче квадратичного программирования.
from __future__ import division from pyomo.environ import * import numpy as np model = AbstractModel() model.N = Param() #The number of areas model.W = Param() #Width model.H = Param() #Height model.Xrange = RangeSet(model.W) model.Yrange = RangeSet(model.H) model.Colors = RangeSet(model.N) model.S = Param(model.Colors, domain = Integers) #Sizes of areas model.A = Param(model.Colors, model.Colors) model.Z = Var(model.Xrange, model.Yrange, model.Colors, domain=Binary) def dist_init(model,x1,y1,x2,y2): dx = x1 - x2 dy = y1 - y2 return sqrt(dx*dx + dy*dy) model.dist = Param(model.Xrange, model.Yrange, model.Xrange, model.Yrange, initialize = dist_init) # Objective - energy def U_rule(model): return sum(sum(sum(sum (model.dist[x1,y1,x2,y2]*sum(sum(model.A[i1,i2]*model.Z[x1,y1,i1]*model.Z[x2,y2,i2] for i1 in model.Colors) for i2 in model.Colors) for y2 in model.Yrange) for x2 in model.Xrange) for y1 in model.Yrange) for x1 in model.Xrange) model.U = Objective(rule=U_rule, sense=minimize) #Constraint: no collisions def Correct_rule (model, x, y) : return sum(model.Z[x,y,i] for i in model.Colors) <= 1 model.Correct = Constraint (model.Xrange, model.Yrange, rule = Correct_rule) #Constraint: square of i-th area is S[i] def Square_rule(model, i): return sum(sum(model.Z[x,y,i] for y in model.Yrange) for x in model.Xrange) == model.S[i] model.Square = Constraint (model.Colors, rule = Square_rule)
Soft Margin SVM
Поиск топологических доменов
Кластеризация невзвешенных неориентированных графов с помощью максимизации модулярности.
pyomo solve --solver=ipopt modularity.py modularity.dat