7
$\begingroup$

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
$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Is7aq Feb 10 '13 at 13:39
  • $\begingroup$ @Is7aq Hint: what inequality prevents more than one of $b_{11}, b_{21}, b_{31}, b_{41}$ from being $\ge 1$? $\endgroup$ – Erick Wong Feb 10 '13 at 16:43
  • $\begingroup$ thanks for your help, I ended up taking your second suggestion! good stuff :) $\endgroup$ – Is7aq Feb 11 '13 at 16:37
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Erick Wong Feb 10 '13 at 3:47
  • $\begingroup$ 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. $\endgroup$ – dexter04 Feb 10 '13 at 3:58
  • 1
    $\begingroup$ 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$. $\endgroup$ – Erick Wong Feb 10 '13 at 4:02
0
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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$.) $\endgroup$ – Erick Wong Feb 10 '13 at 4:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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