How to formulate Unique value constraint in Integer Programming?

Question

Given the following integer programming formulation, how can I specify that the variables are unique and none of them has the same value as the other one. basically x1, x2, x3 , and x4 need to get only one unique value from 1, 2, 3 or 4. and same applies to y1, y2, y3, and y4.

Minimize
obj: +2*x1 -3*y1 +3*x2 -3*y2 +1*x3 -2*y3 +4*x4 -2*y4

Constraints

+2*x1 -3*y1 +3*x2 -3*y2 +1*x3 -2*y3 +4*x4 -2*y4 >= 0

Bounds

1 <= x1 <= 4
1 <= x2 <= 4
1 <= x3 <= 4
1 <= x4 <= 4
1 <= y1 <= 4
1 <= y2 <= 4
1 <= y3 <= 4
1 <= y4 <= 4

Answer 1

One way to make this work is to change the underlying representation. Instead of your basic variables being $x_i$ and $y_i$, use binary indicator variables to indicate which of $\{1,2,3,4\}$ is assigned to $x_i$.

For instance, with four variables $b_{i1}, b_{i2}, b_{i3}, b_{i4}$, if we constrain each $0 \le b_{ij} \le 1$ as well as $b_{i1} + b_{i2} + b_{i3} + b_{i4} = 1$, then exactly one of the four variables will be $1$ and the rest must be $0$. We can then set $x_i = b_{i1} + 2b_{i2} + 3b_{i3} + 4b_{i4}$ to give $x_i$ the chosen value.

Now it should be easy to see how to enforce distinctness: to avoid repeating the value $1$, we just need to prevent $b_{i1} = b_{j1} = 1$ for any distinct $i,j$, and this can be done with a single inequality $\displaystyle\sum_i b_{i1}\le1$. Then another to prevent $2$ from being repeated, etc.

EDIT: Here's a different encoding inspired by dexter04's idea. For each $i$ and $j$ create a boolean variable $b = b_{ij}$ where $0\le b_{ij}\le 1$, which encodes whether $x_i \ge x_j+1$ or $x_j \ge x_i+1$. Add the inequalities $$x_i \ge x_j + (1-b) - 100(b) \qquad x_j \ge x_i + (b) - 100(1-b).$$ When $b=0$, the first inequality becomes $x_i \ge x_j+1$, and the second becomes $x_j \ge x_i - 100$, which is harmless. When $b=1$, the same thing happens but with $x_i$ and $x_j$ reversed. Since $b$ must be either $0$ or $1$, exactly one of the two situations ($x_i > x_j$ or $x_j > x_i$) must occur but it doesn't mandate a particular side.

This is a more scalable solution when the range of values taken by $x_i$ is much larger than the number of variables. The crossover point is when the range of possible values for $x_i$ is proportional to the square of the number of variables: if the range is significantly less populous than this, then the first solution may be a bit more efficient.

Answer 2

For every pair of variables $x_i,x_j$, define a new variable $z_{ij} = |x_i-x_j|$.

Note that the conditions $$z_{ij} \ge x_i-x_j \\z_{ij} \ge x_j-x_i$$ are enough to define $z_{ij}$.

Now, impose the extra condition $z_{ij}>0$ to keep $x_i,x_j$ distinct. You have to do this for all possible pairs if you want no duplicates.

Answer 3

I found a workaround by adding the following constraints, to ensure that the sum of every 2 numbers, every 3 number, and every 4 numbers is at the least their minumum sum if they are to be distinct. For the above problem, the following additional constraints ensured that values are distinct.

+x1 +x2 >= 3
+x1 +x3 >= 3
+x1 +x4 >= 3
+x2 +x3 >= 3
+x2 +x4 >= 3
+x3 +x4 >= 3
+y1 +y2 >= 3
+y1 +y3 >= 3
+y1 +y4 >= 3
+y2 +y3 >= 3
+y2 +y4 >= 3
+y3 +y4 >= 3
+x1 +x2 +x3 >= 6
+x1 +x3 +x4 >= 6
+x2 +x3 +x4 >= 6
+x1 +x2 +x3 +x4 >= 10