整数规划：整数变量的模型唯一性

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 Predicate of Constraint Satisfaction in Integer Programming," INFORMS Journal on Computing, Vol. 13 (2001) 96-103

另请参阅讨论 here。

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}

看起来不错，不是吗？

整数规划：整数变量的模型唯一性

Integer Programming: Model uniqueness of integer variables

optimization

linear-programming