Как использовать линейное программирование для решения логических ограничений

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

Ограничение 2:

n1 + n2 = 1 - n3

Ограничение 3:

b1 + b2 + b3 = 1  (if at most one of them is true then change = to <=)

Ограничение 1:

Соглашение: я использую y для обозначения логических переменных и z для обозначения непрерывных неотрицательных переменных. Я также предполагаю, что нет разницы между && и AND и между || и OR.

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

y1 := n1==n2 --> (（y1 xor n3） && c1==2 && b1 ) || ( (y1 or n3) && c1==1 && b2 ) || (( y1 and n3) 1&& c1==3 && b3)

y1 >= 1 - (n1 + n2)
y1 >= (n1 + n2) - 1
y1 <= 2 - 2n1 +  n2
y1 <= 2 - 2n2 + n1

y2 := y1 xor n3 --> (y2 && c1==2 && b1 ) || ( (y1 or n3) && c1==1 && b2 ) || (( y1 and n3) 1&& c1==3 && b3)

y2 <= y1 + x3
y2 >= y1 - x3
y2 >= x3 - y1
y2 <= 2 - y1 - x3

y5 := c1==2 --> (y2 && y5 && b1 ) || ( (y1 or n3) && c1==1 && b2 ) || (( y1 and n3) 1&& c1==3 && b3)

Допустим, что epsilon > 0 будет предопределенным допуском (чтобы если 2 - epsilon <= c1 <= 2 + epsilon, то c1=2), а M - большим числом (возможно, верхней границей c1):

z3 >= c1 - 2 + epsilon*y3;  z3 >= 0
z4 >= 2 - c1 + epsilon*y4;  z4 >= 0
z3 <= My3
z4 <= My4
y3 + y4 + y5 = 1

y6 := y2 && y5 && b1 --> y6 || ( (y1 or n3) && c1==1 && b2 ) || (( y1 and n3) 1&& c1==3 && b3)

y6 <= y2
y6 <= y5
y6 <= b1
y6 >= y2 + y5 + b1 - 2

y7 := y1 or n3 --> y6 || ( y7 && c1==1 && b2 ) || (( y1 and n3) 1&& c1==3 && b3)

y7 >= y1
y7 >= n3
y7 <= y1 + n3

y10 := c1 == 1 --> y6 || ( y7 && y10 && b2 ) || (( y1 and n3) 1&& c1==3 && b3)

z8 >= c1 - 1 + epsilon*y8;  z8 >= 0
z9 >= 1 - c1 + epsilon*y9;  z9 >= 0
z8 <= My8
z9 <= My9
y8 + y9 + y10 = 1

y11 := y7 && y10 && b2 --> y6 || y11 || (( y1 and n3) 1&& c1==3 && b3)

y11 <= y7
y11 <= y10
y11 <= b2
y11 >= y7 + y10 + b2 - 2

Предполагая, что 1&& - опечатка, а на самом деле &&,

y12 := ( y1 and n3) --> y6 || y11 || (y12 && c1==3 && b3)

y12 <= y1
y12 <= n3
y12 >= y1 + n3 - 1

y15 := c1==3 --> y6 || y11 || (y12 && y15 && b3)

z13 >= c1 - 3 + epsilon*y13;  z13 >= 0
z14 >= 3 - c1 + epsilon*y14;  z14 >= 0
z13 <= My13
z14 <= My14
y13 + y14 + y15 = 1

y16 := y12 && y15 && b3 --> y6 || y11 || y16

y16 <= y12
y16 <= y15
y16 <= b3
y16 >= y12 + y15 + b3 - 2

Наконец, y6 || y11 || y16

y6 + y11 + y16 >= 1

Надеюсь, это поможет. Для удобства я включил полную математическую модель ниже.

Математическая модель

      min c1 
s.t.  n1 + n2 = 1 - n3
      b1 + b2 + b3 = 1
      y1 >= 1 - (n1 + n2)
      y1 >= (n1 + n2) - 1
      y1 <= 2 - 2n1 +  n2
      y1 <= 2 - 2n2 + n1
      y2 <= y1 + x3
      y2 >= y1 - x3
      y2 >= x3 - y1
      y2 <= 2 - y1 - x3
      z3 >= c1 - 2 + epsilon*y3;  z3 >= 0
      z4 >= 2 - c1 + epsilon*y4;  z4 >= 0
      z3 <= My3
      z4 <= My4
      y3 + y4 + y5 = 1
      y6 <= y2
      y6 <= y5
      y6 <= b1
      y6 >= y2 + y5 + b1 - 2
      y7 >= y1
      y7 >= n3
      y7 <= y1 + n3
      z8 >= c1 - 1 + epsilon*y8;  z8 >= 0
      z9 >= 1 - c1 + epsilon*y9;  z9 >= 0
      z8 <= My8
      z9 <= My9
      y8 + y9 + y10 = 1
      y11 <= y7
      y11 <= y10
      y11 <= b2
      y11 >= y7 + y10 + b2 - 2
      y12 <= y1
      y12 <= n3
      y12 >= y1 + n3 - 1
      z13 >= c1 - 3 + epsilon*y13;  z13 >= 0
      z14 >= 3 - c1 + epsilon*y14;  z14 >= 0
      z13 <= My13
      z14 <= My14
      y13 + y14 + y15 = 1
      y16 >= y12
      y16 >= y15
      y16 >= b3
      y16 >= y12 + y15 + b3 - 2
      y6 + y11 + y16 >= 1
      y1, ..., y16, b1, b2, b3, n1, n2, n3 binary
      z3, z4, z8, z9, z13, z14 >= 0

Кстати, если у вас есть доступ и lpsolve, и Gurobi, обязательно выберите Gurobi. Это лидер на рынке, и производительность lpsolve далека от большинства проблем некоторой сложности.

ОБНОВЛЕНИЕ

После помещения этой модели в решатель я получаю решение c1 = 1 и

n1 = 1
n2 = 1
n3 = 1
b1 = 0
b2 = 1
b3 = 0

Что имеет смысл: c1 == 1 или c2 == 2 или c3 == 3, чтобы пункт 3 оставался верным, а случай c1=1 является минимально возможным. Подставляя значения для других переменных, мы видим, что все три ограничения выполнены.

Кажется, что ваша проблема имеет очень ограниченную структуру, поэтому решение должно быть намного проще. Ясно, что c1 должно быть 1, 2 или 3.

1. Если ((n1 == n2 или n3) && b2) имеет решение, то c1 = 1.
2. В противном случае, если n1 == n2 xor n3） && b1) имеет решение, тогда c1 = 2.
3. В противном случае, если ((n1 == n2 and n3) && b3) имеет решение, то c1 = 3. (Здесь в исходном вопросе есть опечатка с ложной 1).
4. В противном случае решения нет.

Ограничение 3 легко, поскольку каждое из b1, b2 и b3 используется только один раз:

1. Если (n1 == n2 или n3) имеет решение, то c1 = 1, b2 = 1, b1 = b3 = 0.
2. В противном случае, если （n1 == n2 xor n3) имеет решение, то c1 = 2, b1 = 1, b2 = b3 = 0.
3. В противном случае, если (n1 == n2 и n3) имеет решение, то c1 = 3, b3 = 1, b1 = b2 = 0.
4. В противном случае решения нет.

Ограничение 2 означает, что n3 можно вычислить из n1 и n2: n3 = not (n1 и n2), поэтому все, что вам нужно сделать, это попробовать четыре комбинации n1 и n2, вычислить n3 для каждой комбинации и проверить эти условия. Никакого линейного программирования или целочисленного программирования не требуется.

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