Как выразить отношение «не равно» в линейном программировании? - PullRequest
Новая
       43

Как выразить отношение «не равно» в линейном программировании?

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

Я хочу решить проблему LP в Python с помощью библиотеки Pulpe (или любой другой).

Я хочу выразить ограничение, утверждающее, что все мои переменные должны иметь разные значения (их домен - {0, 1, 2, 3 ... N} для заданного целого числа N.), равного x_1 != x_2 != x_3 ... != x_N.

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

Чтобы добавить ограничение «все по-другому», я сделал следующее: 

for x_i in variables:
    for x_j in variables:
        if the following constraint has not been already added and x_i != x_j:
            my_problem += x_i - x_j >= 1, "unique name for the constraint"

Предыдущий код не работает.Когда я хочу добавить ограничение x_i != x_j, оно просто не работает.Итак, поскольку я работаю с ограниченным набором целых чисел, я могу (я думаю) переписать «не равно» как x_i - x_j> 0. Pulpe говорит мне, что он не обрабатывает оператор «>» между int иLpAffineExpression поэтому я написал x_i - x_j >= 1.Тем не менее, он работает, но кажется, что он не работает, и я не могу понять, почему.

Ответы [ 2 ]

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

Причина, по которой ваше ограничение не работает, состоит в том, что вы требуете, чтобы x_i было как минимум на 1 больше, чем x_j, для каждых i и j.Таким образом, вы требуете x_1 > x_2 и x_2 > x_1.Вероятно, вы можете решить эту проблему, заменив x_i != x_j на i > j или что-то подобное в своем выражении if.

Но в вашем случае я хотел бы рассмотреть возможность использования двоичных переменных, чтобы указать, какое значение принимает каждый x_i.Например, пусть y_{i,n} = 1, если x_i = n.Тогда у вас есть ограничение, например

sum {i=1,...,N} y_{i,n} <= 1 для всех n = 0,...,N

(т. Е. Каждое значение n может использоваться не более одного раза) и другое, например

sum {n=0,...,N} y_{i,n} = 1 для всех i = 1,...,N

(каждому i должно быть присвоено некоторое значение n).

Затем в вашей формулировке замените все переменные x_i на sum {n=0,...,N} y_{i,n}.

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

Есть несколько способов сделать это, в зависимости от конкретной ситуации.

У вас, похоже, n переменные x[i].Они могут принимать значения {0,...,n} и должны быть разными.

В качестве отступления: ваша запись x[1] ≠ x[2] ≠ x[3].. не совсем верна.Например, x[1]=1, x[2]=2, x[3]=1 удовлетворит x[1] ≠ x[2] ≠ x[3].

Различное ограничение может быть записано попарно как x[i] ≠ x[j] для всех i < j (мы не хотим проверять i и j дважды).Это неравенство можно переформулировать как: x[i] ≤ x[j]-1 OR x[i] ≥ x[j]+1.Условие ИЛИ может быть реализовано в модели MIP следующим образом: 

 x[i] ≤ x[j]-1 + M δ[i,j]        ∀ i < j
 x[i] ≥ x[j]+1 - M (1-δ[i,j])    ∀ i < j
 δ[i,j] ∈ {0,1}

, где M=n+1.Мы добавили дополнительные двоичные переменные δ[i,j].

Это наиболее прямая формулировка "неравной" конструкции.В нем также относительно мало двоичных переменных: около n ^ 2/2.Другие формулировки также возможны.Для получения дополнительной информации см. ссылка .

Обратите внимание, что решатели программирования ограничений часто имеют встроенные средства для всех различных ограничений, поэтому может быть проще использовать CP-решатель (они также могут быть более эффективными для моделей с совершенно разными ограничениями).

...