Integer Programming: Modell Einzigartigkeit von Integer-Variablen

Question

Lassen Sie uns drei Integer-Variablen für Integer-Programmierung haben annehmen, also:

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

Jetzt will ich modellieren, dass alle Variablen unterschiedlich sind. Natürlich kann ich für jede Kombination folgendes machen (drei in diesem Fall). Ich zeige es mit a und b.

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

Gibt es einen einfacheren Weg ohne viele neue Constraints, bigMs und binäre Variablen zu erzeugen?

Answer 1

Sorry, nicht wirklich. Dieses Konstrukt wird oft all-different constraint genannt. Hier ist eine Referenz:

H.P.Williams, Hong Yan, "Vertretungen des all-verschiedenen Prädikats von Constraint Satisfaction in Integer Programming" INFORMIERT Journal on Computing, Vol. 13 (2001) 96-103

Siehe auch die Diskussion here.

Answer 2

Ich fand heraus, dass man auch Folgendes tun könnte:

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} 

Nun, offensichtlich ist es j^2 neue jetzt Binärgrößen. Aber Sie haben Ihre x_j Variablen sowie Ihre b_i_j Variablen, so dass Sie viel flexibler für alle Arten von Einschränkungen sind.

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

Scheint in Ordnung, nicht wahr?