(a - b) ²

Это работает, потому что:

(a − b)² = a * (a − b) + b * (b − a)

Поскольку умножение в ℤ₂ является соединением ( & ), и 1 - a отрицание (! ), приведенная выше формула эквивалентна XOR для a, b ∈ {0, 1} :

(a & !b) | (b & !a)

См. комментарий Паскаля Куока ниже, объясняющий, почему это не может быть линейным уравнением .

Простейшее выражение, которое я могу придумать, это: a! = B .

(Предыдущее максимальное усилие было (a + b) == 1 )

Вы можете сделать что-нибудь вроде:

(a + b) % 2

Исключающее ИЛИ - это линейная функция, но определение «линейного» относительно логического функция - это не то же самое, что и с полиномиальной функцией. Вам нужно будет просмотреть документацию к вашей библиотеке lp_solve , чтобы узнать, способна ли она обрабатывать линейные логические функции. Судя по тому, что я прочитал, я не подозреваю, что это возможно.

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

абс (A + B-1). если не работает абс, то (A + B-1) * (A + B-1) должен это сделать.

Weellllllllllllll........

Все не так просто.

Чтобы смоделировать XOR (назовем его X), мы начнем с логики.

X = (A & !B) | (!A & B)

В математике это можно записать так:

X = A*(1-B) + B*(1-A)

Но приведенное выше выражение нелинейно (из-за билинейных членов - чтобы сохранить линейность, нам не разрешается перемножать переменные друг с другом).

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

Сначала расширим термины:

X = A*(1-B) + B*(1-A) = A + B - 2*A*B

Теперь нам нужно позаботиться о термине A*B (что по сути означает A & B). Пусть переменная H представляет логическое условие A & B. Теперь мы можем записать условие AND следующим образом: (см. цитируемую ссылку PDF ниже)

H <= A
H <= B
H >= A + B - 1
H >= 0

Линейная формула XOR

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

X = A + B - 2*H
H <= A
H <= B
H >= A + B - 1
H >= 0

Я знаю, что это выглядит сложно (для такой простой операции, как XOR). Возможно, существует более компактная формулировка.

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

Ссылка

Список стандартных целочисленных формулировок для линейного представления логики см. здесь. http://brblog.typepad.com/files/mipformref-1.pdf

Edit:

Объяснение того, как ограничения H моделируют логическое условие "AND". По сути, в ЛП мы задаем ограничения неравенства, которые должны быть выполнены в точке решения - то, что мы делаем здесь, это игра в трюк, чтобы "сжать" H до нужного значения. Например, для кортежа (A,B) = (0,0) ограничения для H будут следующими:

H <= 0
H <= 0
H >= -1
H >= 0

В приведенном выше случае единственное значение H может быть равно 0, поскольку H принадлежит интервалу [0,0]. Отсюда получаем (A,B) = (0,0) => H = 0.

Рассмотрим другой пример, (A,B) = (1,1).

H <= 1
H <= 1
H >= 1
H >= 0

Из вышесказанного сразу видно, что 1 <= H <= 1 подразумевает, что H = 1. Получаем (A,B) = (1,1) => H = 1.

И так далее. Вы увидите, что ограничения H в точности моделируют условие "AND".