CODEWITHSUNDEEP
optimizationlinear-programming
user6040992
user6040992

Reputation:

Integer Programming: Model uniqueness of integer variables

Let's suppose to have three integer variables for integer programming, thus:

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

Now I want to model that all variables are different. Obviously I can do the following for every combination (three in this case). I show it with a and b.

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

Is there an easier way without producing lots of new constraints, bigMs, and binary variables?

Upvotes: 0

Views: 129

Answers (2)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16724

Sorry, not really. This construct is often called the all-different constraint. Here is a reference:

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

See also the discussion here.

Upvotes: 1

user6040992
user6040992

Reputation:

I found out, that one could do the following as well:

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}

Well, obviously there is j^2 new binary variables now. But you have your x_j variables as well as your b_i_j variables thus you are much more flexible for all kind of constraints.

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

Seems okay, doesn't it?

Upvotes: 0

Related Questions