1

我希望使用线性规划来解决以下逻辑描述。在下面的示例中，n1, n2, n3, b1, b2, b3是布尔变量。

目标是最小化c1。

以下是约束：

约束1： (（n1==n2 xor n3） && c1==2 && b1 ) || ( (n1== n2 or n3) && c1==1 && b2 ) || (( n1 == n2 and n3) 1&& c1==3 && b3)

约束2：n1 && n2== not n3

约束 3：only one of b1, b2, b3 is true

我可以知道是否可以将这些逻辑约束编码为 Gurobi 或 lpsolve 等线性编程工具所需的整数约束？或者有没有可以利用布尔约束的工具？

谢谢。

4

3 回答 3

3

混合整数规划（不是线性规划）是可能的，但很混乱。让我们从简单的开始：

约束 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 和ANDand 之间没有区别||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 + epsilonthen 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是最小的可能。插入其他变量的值，我们可以看到所有三个约束都得到满足。

于 2014-07-30T14:56:53.253 回答
1

您的问题似乎具有非常有限的结构，因此解决方案应该容易得多。显然 c1 必须是 1、2 或 3。

  1. 如果 ( (n1== n2 or 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 意味着可以从 n1 和 n2 计算出 n3：n3 = not (n1 and n2)，所以您需要做的就是尝试 n1 和 n2 的四种组合，计算每种组合的 n3，并检查这些条件。不需要线性规划或整数规划。

于 2014-07-31T13:26:45.793 回答
0

我认为您可以通过在GECODE或Choco等约束编程系统中表达它来解决它。查看它们 - 有很多示例可以帮助您入门。

于 2014-07-30T15:21:38.053 回答