10
$\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$

3 Answers 3

Reset to default
12
$\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. 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.

$\endgroup$
7
  • $\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$ Commented Feb 10, 2013 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$ Commented Feb 10, 2013 at 16:43
  • $\begingroup$ thanks for your help, I ended up taking your second suggestion! good stuff :) $\endgroup$ Commented Feb 11, 2013 at 16:37
  • 2
    $\begingroup$ @makansij You can use $=$ instead of $\le$ in this very specific case, but I prefer to use $\le$ so that it works in the more general case that there may be more possible values than variables to occupy them (e.g. 4 distinct numbers between $1$ and $10$). In that case you want to allow for the possibility that $1$ is unused by any variable. $\endgroup$ Commented Jun 4, 2021 at 2:23
  • 1
    $\begingroup$ How can this idea generalize to points in Z^2? Like suppose (x_i, y_i) are unbounded (positive) integer pairs and we want (x_i, y_i) ≠ (x_j, y_j), but it's okay if x_i = x_j OR y_i = y_j. $\endgroup$ Commented Oct 23, 2024 at 21:02
3
$\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$
4
  • $\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$ Commented Feb 10, 2013 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$ Commented Feb 10, 2013 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$ Commented Feb 10, 2013 at 4:02
  • $\begingroup$ Although this answer is not correct, it does contain a useful idea at its core, so I declined to downvote it. $\endgroup$ Commented Jun 3, 2021 at 18:15
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$
1
  • $\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$ Commented Feb 10, 2013 at 4:10

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.