7

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.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
Vogtster
  • 205
  • 1
  • 3
  • 3
    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$$ – RobPratt Jul 28 '22 at 14:12

2 Answers2

12

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}

Kuifje
  • 13,324
  • 1
  • 23
  • 56
  • A classic use case is Sudoku: https://jump.dev/JuMP.jl/stable/tutorials/linear/sudoku/ – Max Jul 30 '22 at 13:37
5

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

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • interesting, although the formulation requires an exponential number of constraints. – Kuifje Jul 28 '22 at 19:14
  • 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." – RobPratt Jul 28 '22 at 20:14