Pyomo

Материал из MachineLearning.

Версия 23:07, 21 декабря 2016

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

• PyomoGallery,

• Примеры из репозитория pyomo.

Ensemble Clustering

В статье Ensemble CLustering Using Factor Graphs решается задача ensemble clustering, где промежуточным шагом является решение линейной бинарной задачи. Хотя авторы статьи применяют для этого метод, названный Belief Propagation, задачу можно решить и напрямую. Приведенный ниже код основан на примере Diet оригинального мануала [1].

Исходный код на google drive.

Запуск производится командой

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

Исходный код на google drive. Входные данные.