scipy.optimize.

milp

scipy.optimize.milp(c, *, integrality=None, границы=None, ограничения=None, опции=None)

Смешанно-целочисленное линейное программирование

Решает задачи следующего вида:

\[\begin{split}\min_x \ & c^T x \\ \mbox{such that} \ & b_l \leq A x \leq b_u,\\ & l \leq x \leq u, \\ & x_i \in \mathbb{Z}, i \in X_i\end{split}\]

где \(x\) является вектором переменных решения; \(c\), \(b_l\), \(b_u\), \(l\), и \(u\) являются векторами; \(A\) является матрицей, и \(X_i\) это множество индексов переменных решения, которые должны быть целочисленными. (В этом контексте переменная, которая может принимать только целые значения, называется "целочисленной"; она имеет ограничение "целочисленности".)

Альтернативно, это:

минимизировать:

c @ x

такой, что:

b_l <= A @ x <= b_u
l <= x <= u
Specified elements of x must be integers

По умолчанию, l = 0 и u = np.inf если не указано с помощью bounds.

Параметры:

c1D плотный массивоподобный объект

Коэффициенты линейной целевой функции для минимизации. c преобразуется в массив двойной точности перед решением задачи.

integrality1D плотный array_like, опционально

Указывает тип ограничения целочисленности для каждой переменной решения.

0 : Непрерывная переменная; ограничение целочисленности отсутствует.

1 : Целочисленная переменная; переменная решения должна быть целым числом в пределах границы.

2 : Полунепрерывная переменная; переменная решения должна находиться в пределах границы или принимать значение 0.

3 : Полуцелая переменная; переменная решения должна быть целым числом в пределах границы или принимать значение 0.

По умолчанию все переменные непрерывны. integrality преобразуется в массив целых чисел перед решением задачи.

границыscipy.optimize.Bounds, опционально

Границы на переменные решения. Нижние и верхние границы преобразуются в массивы двойной точности перед решением задачи. keep_feasible параметр Bounds объект игнорируется. Если не указано, все переменные решения ограничены неотрицательными значениями.

ограниченияпоследовательность scipy.optimize.LinearConstraint, опционально

Линейные ограничения задачи оптимизации. Аргументы могут быть одним из следующих:

1. Один LinearConstraint object

2. Один кортеж, который можно преобразовать в LinearConstraint объект как LinearConstraint(*constraints)

3. Последовательность, полностью состоящая из объектов типа 1 и 2.

Перед решением задачи все значения преобразуются в двойную точность, а матрицы коэффициентов ограничений преобразуются в экземпляры scipy.sparse.csc_array. keep_feasible оценок. LinearConstraint объектов игнорируется.

опцииdict, optional

Словарь параметров решателя. Распознаются следующие ключи.

dispbool (по умолчанию: False)

Установить в True если индикаторы статуса оптимизации должны выводиться в консоль во время оптимизации.

node_limitint, необязательный

Максимальное количество узлов (релаксаций линейного программирования) для решения перед остановкой. По умолчанию нет максимального количества узлов.

предварительное решениеbool (по умолчанию: True)

Предварительное решение пытается выявить тривиальные несовместимости, определить тривиальную неограниченность и упростить задачу перед отправкой в основной решатель.

time_limitfloat, опционально

Максимальное количество секунд, выделенное на решение задачи. По умолчанию ограничения по времени нет.

mip_rel_gapfloat, опционально

Критерий остановки для решателя MIP: решатель завершит работу, когда разрыв между значением целевой функции для прямой задачи и границей целевой функции для двойственной задачи, масштабированный значением целевой функции для прямой задачи, будет <= mip_rel_gap.

Возвращает:

resOptimizeResult

Экземпляр scipy.optimize.OptimizeResult. Объект гарантированно имеет следующие атрибуты.

statusint

Целое число, представляющее статус завершения алгоритма.

0 : Оптимальное решение найдено.

1 : Достигнут предел итераций или времени.

2 : Задача неразрешима.

3 : Задача неограничена.

4 : Другое; подробности см. в сообщении.

successbool

True когда найдено оптимальное решение и False в противном случае.

messagestr

Строковый дескриптор статуса завершения алгоритма.

Следующие атрибуты также будут присутствовать, но их значения могут быть None, в зависимости от статуса решения.

xndarray

Значения переменных решения, которые минимизируют целевую функцию при соблюдении ограничений.

funfloat

Оптимальное значение целевой функции c @ x.

mip_node_countint

Количество подзадач или "узлов", решаемых MILP-решателем.

mip_dual_boundfloat

Окончательная оценка решателем MILP нижней границы оптимального решения.

mip_gapfloat

Разница между значением прямой целевой функции и границей двойственной целевой функции, нормированная на значение прямой целевой функции.

Примечания

milp является оболочкой для программного обеспечения линейной оптимизации HiGHS [1]. Алгоритм детерминирован и обычно находит глобальный оптимум умеренно сложных смешанно-целочисленных линейных программ (если он существует).

Ссылки

[1]

Huangfu, Q., Galabova, I., Feldmeier, M., and Hall, J. A. J. “HiGHS - высокопроизводительное программное обеспечение для линейной оптимизации.” alphap

[2]

Хуанфу, К. и Холл, Дж. А. Дж. «Параллелизация двойственного пересмотренного симплексного метода». Математическое программирование и вычисления, 10 (1), 119-142, 2018. DOI: 10.1007/s12532-017-0130-5

Примеры

Попробуйте в вашем браузере!

Рассмотрим задачу на https://en.wikipedia.org/wiki/Integer_programming#Example, что выражается как задача максимизации двух переменных. Поскольку milp требует чтобы задача была выражена как задача минимизации, коэффициенты целевой функции для переменных решения:

>>> import numpy as np
>>> c = -np.array([0, 1])

Обратите внимание на отрицательный знак: мы максимизируем исходную целевую функцию, минимизируя отрицание целевой функции.

Мы собираем коэффициенты ограничений в массивы, такие как:

>>> A = np.array([[-1, 1], [3, 2], [2, 3]])
>>> b_u = np.array([1, 12, 12])
>>> b_l = np.full_like(b_u, -np.inf, dtype=float)

Поскольку для этих ограничений нет нижнего предела, мы определили переменную b_l заполнен значениями, представляющими отрицательную бесконечность. Это может быть незнакомо пользователям scipy.optimize.linprog, который принимает только ограничения типа "меньше" (или "верхняя граница") вида A_ub @ x <= b_u. Принимая оба b_l и b_u ограничений b_l <= A_ub @ x <= b_u, milp позволяет кратко задавать ограничения-неравенства «больше», ограничения-неравенства «меньше» и ограничения-равенства.

Эти массивы собираются в единый LinearConstraint объект, подобный:

>>> from scipy.optimize import LinearConstraint
>>> constraints = LinearConstraint(A, b_l, b_u)

Ограничения неотрицательности на переменные решения применяются по умолчанию, поэтому нам не нужно предоставлять аргумент для границы.

Наконец, в задаче указано, что обе переменные решения должны быть целыми числами:

>>> integrality = np.ones_like(c)

Мы решаем задачу следующим образом:

>>> from scipy.optimize import milp
>>> res = milp(c=c, constraints=constraints, integrality=integrality)
>>> res.x
[2.0, 2.0]

Обратите внимание, что если бы мы решили ослабленную задачу (без целочисленных ограничений):

>>> res = milp(c=c, constraints=constraints)  # OR:
>>> # from scipy.optimize import linprog; res = linprog(c, A, b_u)
>>> res.x
[1.8, 2.8]

мы бы не получили правильное решение, округляя до ближайших целых чисел.

Другие примеры приведены в учебнике.

НазадОткрыть во вкладке