Gurobi：如何添加约束 x1*x2*x3

Question

我想在Gurobi中添加一个约束条件，形式是 n1 = x1 * x2 * x3，其中 x1、x2 和 x3 是取值为0或1的变量。可惜的是，我找不到解决办法。

有人能帮帮我吗？

Answer 1

将二进制字符串转换成整数的简单方法是什么？然后，再把它乘起来。这样做可以吗？

int x1 = Integer.parseInt("101011", 2);
int x2 = Integer.parseInt("00010", 2);
int x3 = Integer.parseInt("000101", 2);
int n1 = x1 * x2 * x3;
System.out.println(n1);

更新

我不太了解 Gurobi，但是

  GRBVar x1 = model.AddVar(0.0, 1.0, 0.0, GRB.BINARY, "x1");
  GRBVar x2 = model.AddVar(0.0, 1.0, 0.0, GRB.BINARY, "x2");
  GRBVar x3 = model.AddVar(0.0, 1.0, 0.0, GRB.BINARY, "x3");

这是一个例子

Answer 2

n1<=x1
n1<=x2
n1<=x3
2+n1>=x1+x2+x3

如果x中的任何一个是0，那么n就会被强制设为0。如果所有的都是1，n就会被强制设为1。

编辑 因为Gurobi可以识别二进制变量，你可以直接使用

3*n1<=x1+x2+x3
2+n1>=x1+x2+x3

第一个只允许0和1，而这个如果不是二进制要求的话，会允许小数值。

编辑 这个约束

n3 = x2 * (n1 + n2 - n1 * n2) + x1 * (n1 - n2) *(n1 - n2)

似乎是在试图强制执行某种逻辑

IF n1 AND n2: 
    n3 = x2

IF n1 XOR n2:
    n3 = x1

IF (NOT n1) AND (NOT n2):
    n3 = 0

因为在零一整数线性规划（ILP）中表达布尔逻辑运算的标准规则是x1 AND x2 IMPLIES y1，我把上面的内容重构成了

n1 AND n2 IMPLIES i1
n1 XOR n2 IMPLIES i2
(NOT n1) AND (NOT n2) IMPLIES i3   

构建i1, i2, i3的约束如下

IF n1 AND n2, THEN i1 
    i1 ≥ n1 + n2 − 1
    i1 ≤ n1
    i1 ≤ n2
    0 ≤ i1 ≤ 1

IF n1 XOR n2, THEN i2
    i2 ≤ n1 + n2
    i2 ≥ n1 − n2
    i2 ≥ n2 − n1
    i2 ≤ 2 − n1 − n2
    0 ≤ i2 ≤ 1

IF NOT n1 AND NOT n2, THEN i3
    i3 ≥ 1 - n1 - n2
    i3 ≤ (1 - n1)
    i3 ≤ (1 - n2)
    0 ≤ i3 ≤ 1

这给我们提供了三个互斥的指示符，原始问题可以重写为

-(1 - i1) ≤ n3 - x2 ≤ (1 - i1)
-(1 - i2) ≤ n3 - x1 ≤ (1 - i2)
-(1 - i3) ≤ n3 ≤ (1 - i3)

Answer 3

你想要在二进制变量上创建一个看起来不太线性的限制。其实你可以把这个问题转化为一系列线性限制，注意到只有当x1、x2和x3都为1时，n才会等于1。

// only if part
model.addConstr(n, GRB.LESS_EQUAL, x1);
model.addConstr(n, GRB.LESS_EQUAL, x2);
model.addConstr(n, GRB.LESS_EQUAL, x3);

// if part
GRBLinExpr all_three;
all_three.addTerm(1.0, x1);
all_three.addTerm(1.0, x2);
all_three.addTerm(1.0, x3);
all_three.addConstrant(-2);
model.addConstr(n, GRB.GREATER_EQUAL, all_three);

这就增加了以下限制条件：n >= x1 + x2 + x3 - 2 和 n <= min(x1, x2, x3)。