Python Ограничение линейного программирования пульпы

Question

• 1000 *

, поэтому решение может быть [0,0,0,0,0,0,1], [0,0,0,1,0,0,0], [1,1,1,0, 0,0,1], но не [1,0,1,0,1,0,0].

Я пытался добавить ограничение следующим образом:

prob += min([len(list(g)) for k, g in itertools.groupby(x.values()) if k == 0]) >= 3

но это не сработало.

Как я могу это сформулировать?

Answer 1

Нет. PuLP предназначен для линейного программирования, поэтому все ограничения должны быть линейными. Таким образом, нельзя использовать операторы if и подобные программные конструкции.

Требование иметь по крайней мере три последовательных нуля может быть выражено по-разному. Один довольно интересный способ - запретить шаблоны 101 и 1001. Это можно сформулировать как:

 x[i] - x[i+1] + x[i+2] <= 1             for i=0,1,2,....
 x[i] - x[i+1] - x[i+2] + x[i+3] <= 1    for i=0,1,2,....

Эти ограничения очень точно исключают шаблоны 101 и 1001, но допускают любой другой битовый шаблон. Кроме того, они не требуют дополнительных переменных (некоторые другие подходы требуют).

Как упоминалось в комментариях, то, что происходит вблизи границ, требует некоторого внимания. Точная реализация этого немного зависит от деталей проблемы. Подобно разрешено 01 или 001 в начале и разрешено ли 10,100 в конце. Поэтому немного сложно показать, как это должно быть сделано (мне пришлось бы перечислить несколько возможных сценариев ios).

В любом случае это легко выразить в Pulp.