Реализация Python Solver с настраиваемыми ограничениями - PullRequest
Новая
       17

Реализация Python Solver с настраиваемыми ограничениями

3 голосов
/ 10 июня 2019

У меня есть две переменные, которые связаны друг с другом, и я хочу найти оптимальное решение, которое в этом случае является минимумом их суммы.А пока давайте назовем их X и Y, и вместе с предопределенными константами они складываются в набор «переменных» s1 и s2 (которые позже заполняют ограничения): 

105896649.59 + X = s1
    -6738.82 + Y = s2

При поиске документов SciPy я наткнулся на решение линейного программирования , где у меня есть функция минимизации (в данном случае X + Y) и набор ограничений неравенства и равенствас которыми связаны мои переменные.В моем случае они следующие:

  • X >= 0, Y >= 0
  • s1 >= 1, s2 >= 1
  • s2 / (s1 + s2) = 0.0001%

Для этогоВ конкретном случае код был легко реализуемым: 

from scipy.optimize import linprog

lstConst = [105896649.59, -6738.82]

# function to minimise: X + Y
c= [1, 1]

# left-hand side of the equation for s2 / (s1 + s2) = 0.0001%
# i.e., -0.000001 * X + 0.999999 * Y
Aeq = [[-0.000001, 0.999999]]

# right-hand side of the equation
beq = [0.000001 * (lstConst[0] + lstConst[1]) - lstConst[1]]

# ensures minimum can't be a negative number
minX = max(1, max(1 -lstConst[0], 0))
minY = max(1, max(1 -lstConst[1], 0))

X_bounds = (minX, None)

Y_bounds = (minY, None)

res = linprog(c, A_eq=Aeq, b_eq=beq, bounds=[X_bounds, Y_bounds])

Итак, у нас есть значения для X и Y, чтобы минимизировать функцию параметра x: 

In [1]: res.x
Out[1]: array([1.00000000e+00, 6.84471676e+03])

Я хотел бы опираться на этот подход:

  1. На самом деле существует еще один набор ограничений: s1 и s2 также должны быть целыми числами (обратите внимание, что X иY не имеет проблем с плаванием).
  2. Вместо определения единственного значения для отношения между s1 и s2, я бы предоставил список различных возможных соотношений.

По сути, я хотел бы найти минимальные значения для функции X + Y, учитывая несколько различных соотношений между s1 и s2.Это может быть достигнуто либо путем итерации по списку для определения Aeq и beq на каждой итерации, либо путем определения дополнительных ограничений (если возможно).

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

Если у кого-то есть альтернативное предложение, которое использует библиотеку / оптимизатор, отличную от SciPy и linprog, это также приветствуется.

1 Ответ

3 голосов
/ 10 июня 2019

Сначала решаем проблему: 

minimize x + y, subject to:

    k1 + x = s1
    k2 + y = s2
    x >= 0
    y >= 0
    s1 >= 1
    s2 >= 1
    s2 / (s1 + s2) = k3

Where:

    k1 = 105896649.59
    k2 = -6738.82
    k3 = 0.000001

Обратите внимание, вам не нужны переменные s1 и s2 для кодирования проблемы в linprog. Без вспомогательных переменных s1 и s2 проблема: 

minimize x + y, subject to:

  x >= 0
  y >= 0
  x + k1 >= 1,
  y + k2 >= 1,
  (1-k3)y - k3x = (k1 + k2)k3 - k2

Что немного легче читать и кодировать в linprog: 

import numpy as np
from scipy.optimize import linprog
k1, k2, k3 = 105896649.59, -6738.82, 0.000001
A_ub = -np.eye(2)
b_ub = [k1-1, k2-1]
A_eq = [[-k3, (1-k3)]]
b_eq = (k1 + k2)*k3 -k2
res = linprog([1,1], A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=[[0,None], [0, None]])
print(res)

Это дает [0., 6844.71675549] где, как у вас было x = 1, потому что вы фактически установили нижние границы для x и y равными 1 (я думаю, что это опечатка ...), но это не имеет значения в контекст задаваемого вопроса:

НА ВОПРОС:

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

Если у кого-то есть альтернативное предложение, которое использует библиотеку / оптимизатор, кроме SciPy и linprog, это тоже приветствуется.

Что вы запрашиваете: смешанное целочисленное линейное программирование (MILP) . MILP и линейное программирование (LP), как правило, решаются с помощью разных алгоритмов, и проблему MILP обычно сложнее точно решить. SciPy Optimize не поддерживает MILP. Существует ряд инструментов с открытым исходным кодом, таких как OrTools и PySCIPOpt , которые являются оболочкой Python над SCIP .

ПРИМЕР В PySCIPOpt:

PySCIPOpt хорош тем, что имеет API типа программирования ограничений. В PySCIPOpt вашу проблему довольно легко изложить в удобочитаемой форме. Вновь вводя вспомогательные переменные, мы можем в значительной степени напечатать в ограничениях слово в слово: 

from pyscipopt import Model

k1, k2, k3 = 105896649.59, -6738.82, 0.000001
model = Model()
x = model.addVar(vtype="CONTINUOUS", name="x", lb=0)
y = model.addVar(vtype="CONTINUOUS", name="y", lb=0)
s1 = model.addVar(vtype="CONTINUOUS", name="s1", lb=None, ub=None)
s2 = model.addVar(vtype="CONTINUOUS" name="s2", lb=None, ub=None)
o = model.addVar(vtype="CONTINUOUS", name="Objective Value", lb=0, ub=None)
model.addCons(k1 + x == s1)
model.addCons(k2 + y == s2)
model.addCons(s1 >= 1)
model.addCons(s2 >= 1)
model.addCons(s2/(s1+s2) == k3)
model.addCons(x + y == o)
model.setObjective(o, "minimize")
model.optimize()
print('x + y = o -> (%.4f + %.4f = %.4f)' % (model.getVal(x), model.getVal(y), model.getVal(o)))

Дает тот же ответ, что и linprog, поскольку это просто линейная программа. Однако, поскольку SCIP поддерживает MILP, мы можем ввести целочисленные переменные. Для обработки вашего случая # 1 просто замените s1 и s2 на целые числа: 

...
s1 = model.addVar(vtype="INTEGER", name="s1", lb=None, ub=None)
s2 = model.addVar(vtype="INTEGER", name="s2", lb=None, ub=None)

Дает: 

...
SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.00
Solving Nodes      : 1
Primal Bound       : +1.10089229999989e+05 (1 solutions)
Dual Bound         : +1.10089229999989e+05
Gap                : 0.00 %
x + y = o -> (103244.4100 + 6844.8200 = 110089.2300)

Это совсем другое решение ... но именно поэтому MILP не является LP.

Из приведенного выше примера и прочитав документы , вы сможете понять, как кодировать ваш случай №2 - в основном что-то вроде 1/k3 становится другой целочисленной переменной в вашей модели.

...