How to formulate Unique value constraint in Integer Programming?

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


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.

• thanks for your time :) , and this can be done with a single inequality. Then another to prevent 2 from being repeated, etc. can you please show an example? – Is7aq Feb 10 '13 at 13:39
• @Is7aq Hint: what inequality prevents more than one of $b_{11}, b_{21}, b_{31}, b_{41}$ from being $\ge 1$? – Erick Wong Feb 10 '13 at 16:43
• thanks for your help, I ended up taking your second suggestion! good stuff :) – Is7aq Feb 11 '13 at 16:37

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.

• This doesn't work, as it's certainly possible to satisfy all the inequalities when $x_i = x_j$. The problem is that your conditions only imply $z_{ij} \ge |x_i-x_j|$, not equality. – Erick Wong Feb 10 '13 at 3:47
• Have you tried coding it? I have used this trick a couple of times. It would be great if you could give a counter-example. – dexter04 Feb 10 '13 at 3:58
• Sure thing. How about maximize $x_1+x_2$ subject to $0\le x_1,x_2 \le 1$, $x_1 \ne x_2$? If we replace $x_1 \ne x_2$ with $z > 0, z \ge x_1-x_2, z \ge x_2-x_1$, then I get a maximum at $x_1 = x_2 = z = 1$. – Erick Wong Feb 10 '13 at 4:02

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

• This might work for your particular minimization problem, but as you probably suspect it doesn't work in general, as it allows $x_1 = x_2 = x_3 = x_4 = 4$. (One could add the corresponding upper bound inequalities, but I think this still wouldn't rule out $x_1 = 1, x_2 = x_3 = x_4 = 3$.) – Erick Wong Feb 10 '13 at 4:10