## Monday, May 30, 2016

### All-different and mixed integer programming

There are quite a few models that use the ‘all-different’ constraint, i.e. a set of integer variables $$x_i$$, $$i=\{1,...,n\}$$ is feasible only if they are all different, i.e. $$x_i\ne x_j$$ for $$i\ne j$$. We can probably say that most of these models are of the “educational” type and are not practical production models.

Constraint programming solvers have typically a built-in “all-different” global constraint. This makes it easy to write down such a constraint and the solver will have knowledge about the constraint which it can exploit. That means we can expect better performance than for instance a bunch of pairwise not-equal constraints. So the first observation is: if you have a model that is largely built around an all-different constraint, consider to implement the model using a constraint programming solver.

#### Approach 1

One way to implement this construct for use in a MIP model is to use pairwise comparison: $$x_i\ne x_j$$ for $$i\ne j$$. In a MIP we need binary variables for this:

 (I) \boxed{\begin{align}&x_i \le x_j - 1 + M^{(1)}_{i,j}\delta_{i,j}\\ &x_i \ge x_j + 1 – M^{(2)}_{i,j}(1-\delta_{i,j})\\ &\delta_{i,j} \in \{0,1\} \end{align}} for all $$i\lt j$$

Note that we only need to compare $$x_i$$ and $$x_j$$ if $$i<j$$. This means we need $$\frac{n(n-1)}{2}$$ binary variables. It is important to choose good values for $$M$$ so let’s work on that for a minute (see here for an example where things go wrong if we don’t pay attention to this). Note that instead of using a single $$M$$ we use different values $$M^{(1)}_{i,j}$$ and $$M^{(2)}_{i,j}$$.

The value of $$M^{(1)}_{i,j}$$ should be chosen as small as possible subject to $$x_j-1+M^{(1)}_{i,j}\ge x^{up}_i$$. This means $$M^{(1)}_{i,j}\ge x^{up}_i +1 – x_j$$. This yields the following optimal value: $$M^{(1)}_{i,j} = x^{up}_i +1 – x^{lo}_j$$. Similarly we want to choose the smallest value $$M^{(2)}_{i,j}$$ such that $$x_j+1-M^{(2)}_{i,j} \le x^{lo}_i$$. This gives us: $$M^{(2)}_{i,j} = x^{up}_j +1 - x^{lo}_i$$.

#### Approach 2

Here we consider the special case where each $$x_i \in \{1,…,n\}$$ where $$i=\{1,..,n\}$$.  Now we can write:

 (II) \boxed{\begin{align}&\sum_j \delta_{i,j} = 1 \> \forall i\\ &\sum_i \delta_{i,j} = 1 \> \forall j \\ &x_i = \sum_j j \delta_{i,j} \\ &\delta_{i,j} \in \{0,1\} \end{align}}

The matrix $$\delta$$ can be looked at as a permutation matrix. This permutation matrix $$\delta$$ is a row- and column-permuted identity matrix, i.e. it has a single entry equal to one in each row and in each column. Another way of looking at the first two equations is as an assignment problem. Note that we have $$n^2$$ binary variables here, but no big-M’s.

We can make one extra simplification: we can drop the first assignment constraint. The resulting equations are:

 (III) \boxed{\begin{align}&\sum_j j \delta_{i,j} = x_i\> \forall i\\ &\sum_i \delta_{i,j} = 1 \> \forall j \\ &\delta_{i,j} \in \{0,1\} \end{align}}

This simplification in only possible in this special case. We see below that some minor extensions make this simplification fail.

##### Extension 1

The second approach was tailored to a very special case. Instead of $$x_i \in \{1,…,n\}$$ where $$i=\{1,..,n\}$$ now consider a slightly more general problem, where $$x_i \in \{a_1,…,a_n\}$$ with $$a_{i+1} \gt a_i$$ (that is: no duplicates in the set). This problem is easily handled by a simple extension to model II:

 (IIa) \boxed{\begin{align}&\sum_j \delta_{i,j} = 1 \> \forall i\\ &\sum_i \delta_{i,j} = 1 \> \forall j \\ &x_i = \sum_j a_j \delta_{i,j} \\ &\delta_{i,j} \in \{0,1\} \end{align}}

Can we use the same trick as in model III? The answer is no. For example take $$x_i \in \{0,1,3,5\}$$. Then a model using:

 (IIIa) \boxed{\begin{align}&\sum_j a_j \delta_{i,j} = x_i\> \forall i\\ &\sum_i \delta_{i,j} = 1 \> \forall j \\ &\delta_{i,j} \in \{0,1\} \end{align}} Incorrect!
would allow solutions like $$x=(4,5,0,0)$$ where we actually see both duplicates and inadmissible values.
##### Extension 2

We can allow explicit duplicates by saying: $$x_i \in \{a_1,…,a_n\}$$ with $$a_{i+1} \ge a_i$$. E.g. the data array $$a=\{1,2,2,3,3,3\}$$ would allow 1 one, 2 twos, and 3 threes. This can be handled directly by model IIa.

##### Extension 3

Allow a subset. I.e. consider  $$x_j \in \{a_1,…,a_n\}$$ where $$j=\{1,..,m\}$$ and $$m<n$$. For example choose two different values $$x_j$$ from the set $$\{1,2,3\}$$. To model this let’s use $$i$$ as the index of $$a_i$$. So we have $$j$$ being a subset of $$i=\{1,…,n\}$$. We need to revise model II as follows:

 (IIb) \boxed{\begin{align}&\sum_j \delta_{i,j} \le 1 \> \forall i\\ &\sum_i \delta_{i,j} = 1 \> \forall j \\ &x_j = \sum_i a_i \delta_{i,j} \\ &\delta_{i,j} \in \{0,1\} \end{align}}

If the range of integer variables $$x_j$$ is somewhat small (i.e. we don't have $$x^{up}_j \gg x^{lo}_j$$), we can solve the same problem as handled by approach 1.

##### References
1. H.P. Williams, Hong Yan, "Representations of the all-different Predicate of Constraint Satisfaction in Integer Programming," INFORMS Journal on Computing, Vol. 13 (2001) 96-103
2. W.J. van Hoeve, “The alldifferent Constraint: A Survey,” 6th Annual workshop of the ERCIM Working Group on Constraints, 2001, [link]
3. http://yetanothermathprogrammingconsultant.blogspot.com/2016/10/mip-modeling-from-sudoku-to-kenken.html