Ошибка, запрещающая оптимальное решение с использованием Python Pulp - PullRequest
Новая
       29

Ошибка, запрещающая оптимальное решение с использованием Python Pulp

0 голосов
/ 09 мая 2018

У меня есть следующая проблема оптимизации:

maximize(x1+x2+2x3+x4)

подлежит x1+x2+x3+x4 = 2

, где xi = {0,1} (двоичные переменные).

Когда я реализую это в Pulp как: 

from pulp import *
x1 = pulp.LpVariable('x1', cat=LpBinary)
x2 = pulp.LpVariable('x2', cat=LpBinary)
x3 = pulp.LpVariable('x3', cat=LpBinary)
x4 = pulp.LpVariable('x4', cat=LpBinary)

prob = pulp.LpProblem('x1+x2+2*x3+x4', pulp.LpMaximize)
prob += lpSum([x1, x2, 2*x3, x4])
prob += lpSum([x1, x2, x3, x4]) == 2
prob.solve()

Я получаю решение x1, x2, x3 и x4. Однако я бы хотел запретить это решение, добавив еще одно ограничение как x1+x3 < 2 в Pulp как: 

prob += lpSum([x1, x3]) < 2

Но я не могу найти хорошее решение из-за того, что у меня есть фиктивная переменная в prob.solve (). Должен ли я использовать другое ограничение или я делаю что-то не так?

Ответы [ 2 ]

0 голосов
/ 10 мая 2018

Чтобы найти ВСЕ решения, вам нужны следующие модификации 

while True:
    prob += lpSum([x for x in [x1, x2, x3, x4] if x.value() >= 0.99]) <= sum([x.value() for x in [x1, x2, x3, x4]]) -1
    prob.solve()
    if prob.objective.value() >= opt - 1e-6:
        print(x1.value(), x2.value(), x3.value(), x4.value())
    else:
        break  # No more optimal solutions
0 голосов
/ 09 мая 2018

Когда вы запускаете prob += lpSum([x1, x3]) < 2, вы получаете следующую ошибку:

Traceback (последний вызов был последним): файл "xyz.py", строка 13, в prob + = lpSum ([x1, x3]) <2 TypeError: '<' не поддерживается между экземплярами 'LpAffineExpression' и 'int' </p>

Это пакет целлюлозы, сообщающий, что вы не можете добавлять строгие неравенства, что являетсяСтандартное требование в решателях оптимизации.Поскольку все ваши переменные имеют двоичное значение, <2 совпадает с <=1, и внесение этого изменения порадует решателя: 

prob += lpSum([x1, x3]) <= 1
prob.solve()
print(x1.value(), x2.value(), x3.value(), x4.value())
# 0.0 1.0 1.0 0.0

Так что теперь вы получаете другое решение с тем же целевым значениемиз 3 (x2 = 1 и x3 = 1).

Если вы хотите вывести все возможные решения, вы можете использовать цикл, чтобы продолжать добавлять ограничения, запрещающие оптимальное решение, пока не изменится оптимальное целевое значение: 

from pulp import *
x1 = pulp.LpVariable('x1', cat=LpBinary)
x2 = pulp.LpVariable('x2', cat=LpBinary)
x3 = pulp.LpVariable('x3', cat=LpBinary)
x4 = pulp.LpVariable('x4', cat=LpBinary)

prob = pulp.LpProblem('x1+x2+2*x3+x4', pulp.LpMaximize)
prob += lpSum([x1, x2, 2*x3, x4])
prob += lpSum([x1, x2, x3, x4]) == 2
prob.solve()
print(x1.value(), x2.value(), x3.value(), x4.value())

opt = prob.objective.value()
while True:
    prob += lpSum([x.value() * x for x in [x1, x2, x3, x4]]) <= 1 + 1e-6
    prob.solve()
    if prob.objective.value() >= opt - 1e-6:
        print(x1.value(), x2.value(), x3.value(), x4.value())
    else:
        break  # No more optimal solutions

Это дает ожидаемый результат: 

# 1.0 0.0 1.0 0.0
# 0.0 1.0 1.0 0.0
# 0.0 0.0 1.0 1.0
...