整数計画：整数の変数のモデルの一意性

Question

は、このように、のは、整数プログラミングのための3つの整数の変数を持っているとしましょう：

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

今、私はすべての変数が異なっていることをモデル化します。明らかに私はすべての組み合わせ（この場合は3つ）に対して以下のことを行うことができます。私はaとbでそれを示します。

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

新しい制約、bigMs、およびバイナリ変数をたくさん作成しなくても簡単な方法はありますか？

Answer 1

申し訳ありませんが、本当にありません。この構成は、しばしばall-different constraintと呼ばれます。ここで参照される：

H.P.Williams、香港ヤン、「プログラミング整数で制約充足のすべて-異なる 述語の表現は、」コンピューティング、巻上 ジャーナルが通知されます。 13（2001）96-103

hereも参照してください。

Answer 2

私は1つが同様に次の操作を行うことができること、を発見：

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} 

いいですね。