Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
share|improve this question
add comment

3 Answers 3

up vote 2 down vote accepted

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. 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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

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
share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.