Cмешанное целочисленное программирование (MIP)
Система OptJet поддерживает задачи смешанного целочисленного программирования следующего вида:
Создание объекта модели и инициализация переменных
Первым этапом создания линейной модели является инициализация менеджера, ознакомится с этим можно в разделе sec-gs-base-example. Будем предполагать, что менеджер инициализирован с корректными для MIP задач параметрами.
За создание MIP модели отвечает модуль optjet.md_encoder.linear_parser пакета optjet. Хранилищем модели является экземпляр LinearModel, его инициализация выполняется следующим образом:
```python import optjet.md_encoder.linear_parser as linp
model = linp.LinearModel( qmng, # менеджер "my_model" # имя модели ) ```
Первым шагом создания модели является определение всех доступных переменных. В парадигме кодирования OptJet каждая переменная создаваемой модели представляет собой группу переменных с одинаковыми свойствами в математической модели, для удобства собранную в виде n-мерной матрицы (поддерживается до 9 измерений). Добавление переменных в массив осуществляется при помощи метода модели create_variable.
Для задач MIP поддерживаются три типа переменных:
-
Непрерывные --- переменные, которые могут принимать любое рациональное значение из диапазона
[lb, ub], для определения необходимо использовать типqe.var_type.floating. -
Целые --- переменные, которые могут принимать только целые значения из диапазона
[lb, ub], для определения необходимо использовать типqe.var_type.integer. -
Бинарные --- переменные, которые могут принимать только значения 0 или 1, для определения необходимо использовать тип
qe.var_type.binary.
Ниже приведен пример задания всех возможных типов переменных:
```python
Трехмерная матрица непрерывных переменных
x = model.create_variable( "x", # имя переменной qe.var_type.floating, # тип переменной shape=[3, 1, 4], # размерность матрицы переменных lower_bound=0.5, # нижняя граница, по умолчанию 0 upper_bound=12.4 # верхняя граница, по умолчанию +inf )
Одномерная матрица (вектор) целочисленных переменных
y = model.create_variable( "y", # имя переменной qe.var_type.floating, # тип переменной shape=[3], # размерность матрицы переменных lower_bound=10 # нижняя граница, по умолчанию 0 upper_bound=15 # верхняя граница, по умолчанию +inf )
Одиночная бинарная переменная
z = model.create_variable( "z", # имя переменной qe.var_type.floating, # тип переменной shape=[1], # размерность матрицы переменных ) ```
Задание ограничений
В парадигме OptJet ограничения задаются построчно в виде произвольной линейной комбинации входящих в задачу переменных, ограниченных наперед заданной константой. Создание такого ограничения можно разделить на 2 этапа: создание линейного выражения и дополнение его границами.
Базовой единицей линейного выражения является переменная математической модели. Для доступа к ней необходимо использовать оператор [...]:
python
x[1, 0, 1] # Матричная переменная
y[1] # Векторная переменная
z[0] # Одиночная переменная
Эти переменные объединяются в линейное выражение при помощи следующих операций:
-
Сложения: задается в виде
x[0,0,0] + y[0] + 5, в качестве операндов могут использоваться переменные или рациональные константы. -
Вычитание: задается в виде
x[0,0,0] - y[0] - 5, в качестве операндов могут использоваться переменные или рациональные константы. -
Умножение на константу: задается в виде
10 * x[0,0,0], константа должна быть рациональным числом или типом, который к нему приводится. -
Унарный минус: задается в виде
-x[0,0,0].
Также допустима их любая непротиворечивая комбинация. Для изменения приоритетов выполнения также можно воспользоваться оператором (...).
Также для групп переменных (например, матрицы) поддерживаются операторы редукции, такие как встроенный sum().
После формирования линейного выражения его необходимо дополнить ограничениями. Поддерживаются три типа их задания:
-
lin_expr <= 15--- ограничено только справа. -
lin_expr >= 5--- ограничено только слева. -
5 <= lin_expr <= 15--- ограничено с двух сторон.
Полученное в результате выражение будем называть линейным ограничением. Для его добавления в модель необходимо вызвать метод add_constraint() у модели. Он принимает линейное ограничение и, опционально, его имя:
```python
Ограничение можно задать так
lin_expr = 5 * x[0, 0, 0] - y[0] model.add_constraint(5 <= lin_expr <= 15, name="c1")
Или так
lin_constr = (5 <= 5 * x[0, 0, 0] - y[0] <= 15) model.add_constraint(lin_constr)
Или одним выражением
model.add_constraint(5 <= 5 * x[0, 0, 0] - y[0] <= 15)
Пример с редукцией
model.add_constraint( sum(x[i, 0, j] for i in range(2) for j in range(1, 4)) <= 20, name="cr" ) ```
Задание целевой функции
Целевая функция представляет собой ранее описанное линейное выражение. Модель поддерживает только одну целевую функцию. В случае повторного задания будет использована последняя. Добавление ее в модель осуществляется при помощи метода add_target. Он принимает линейное выражение и, опционально, имя:
```python model.add_target(-x[0, 0, 0] + 10 * y[0], name="tg1")
Пример с редукцией
c = [2, 3] model.add_target( sum(c[i] * x[i, 0, j] for i in range(2) for j in range(1, 4)), name="tgr" ) ```
По умолчанию модель является задачей минимизации. Для задания направления оптимизации (минимум или максимум) используется метод set_maximization модели:
```python
Задача минимизации
model.set_maximization(False)
Задача максимизации
model.set_maximization(True) ```
После завершения построения модели необходимо вызвать метод apply_storage.