整数规划:对整数变量的唯一性进行建模

Question

假设有三个整数变量用于整数编程，因此：

a in {1,2,3}
b in {1,2,3}
c in {1,2,3}

现在我想对所有变量都不同的变量进行建模。显然，我可以为每个组合执行以下操作（在本例中为三个）。我用 a 和 b 显示它。

a <= b - 1 + bin1 * bigM
a >= b + 1 - (1 - bin1) * bigM
bin1 in {0, 1}

有没有更简单的方法不产生大量新的约束、bigM 和二进制变量？

Answer 1

对不起，不是真的。这种结构通常称为 all-different constraint 。以下是参考：

H.P.Williams， Hong Yan， "Representations of the all-different" 整数规划中约束满足的谓词，"告知 计算学报， Vol. 13 （2001） 96-103

另请参阅此处的讨论。

Answer 2

我发现，人们也可以执行以下操作：

x_j   in {1,2,3} for j in {1,2,3}
b_i_j in {0,1} for i,j in {1,2,3}
sum_{i=1}^{3} i * b_i_j = x_j for j in {1,2,3}
sum_{i=1}^{3} b_i_j = 1 for j in {1,2,3}

嗯，显然现在有j^2新的二进制变量。但是你有你的x_j变量和你的b_i_j变量，因此你对所有类型的约束都更加灵活。

all-different constraint:
sum_{j=1}^{3} b_i_j = 1 for i in {1,2,3}

似乎没问题，不是吗？