7
$\begingroup$

So suppose I have integer variables $x_1,x_2,\dots,x_N$ and I enforce that the integer variables are bounded i.e $1 \leq x_i \leq N$

I was interested in posing a constraint so that in the collection $\{ x_i\}$ I would see all values $1,\dots,N$. This is to say that each variable $x_i$ is assigned uniquely a value in the interval $1,\dots,N$.

One way to do this constraint I thought was to just do:

$$\prod_{i=1}^{N} x_i = N! = N(N-1)(N-2)\cdots(2)(1)$$

I believe this fits the bill, but is there a better way of how to pose this constraint? I would suspect integer solvers would have difficulty with this constraint - perhaps there is a better formulation? I could not figure out a straightforward linear representation, and would be interested in seeing if one exists. I know from linear programming I could do $|x_i-x_j| =|e_{i,j}|\geq 1, i\neq j$, but I think this eventually will lead to a similar constraint $e^+e^-$=0.

$\endgroup$
1
  • 3
    $\begingroup$ Note that your product constraint is necessary but not sufficient. For $N \ge 6$, factorization of $N!$ into $N$ factors from $\{1,\dots,N\}$ is not unique. For example, $$6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 6 \cdot 6 \cdot 5 \cdot 4 \cdot 1 \cdot 1$$ $\endgroup$
    – RobPratt
    Jul 28, 2022 at 14:12

2 Answers 2

12
$\begingroup$

Introduce binary variables $y_{ij}\in \{0,1\}$ that take value $1$ if and only if $x_i$ is assigned to value $j\in \{1,...,N\}$, and use the following constraints: \begin{align} x_i &= \sum_{j=1}^N j \cdot y_{ij} \quad &\forall i \in \{1,...,N\}\\ \sum_{j=1}^N y_{ij} &= 1 \quad &\forall i \in \{1,...,N\}\\ \sum_{i=1}^N y_{ij} &= 1 \quad &\forall j \in \{1,...,N\} \\ \end{align}

$\endgroup$
1
5
$\begingroup$

This is called an alldifferent constraint and is supported directly by constraint programming solvers. @Kuifje gave a traditional linear formulation (+1) that uses binary variables, but it is worth pointing out that there is another linear formulation that uses only the original variables. See Theorem 19 here: https://www.andrew.cmu.edu/user/vanhoeve/papers/alldiff.pdf

$\endgroup$
2
  • $\begingroup$ interesting, although the formulation requires an exponential number of constraints. $\endgroup$
    – Kuifje
    Jul 28, 2022 at 19:14
  • $\begingroup$ Yep: "Unfortunately, the number of inequalities to describe the convex hull grows exponentially with the number of variables. In practice it may therefore be profitable to generate these inequalities only when they are violated by the current relaxation." $\endgroup$
    – RobPratt
    Jul 28, 2022 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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