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! |
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
- 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
- W.J. van Hoeve, “The alldifferent Constraint: A Survey,” 6th Annual workshop of the ERCIM Working Group on Constraints, 2001, [link]
- http://yetanothermathprogrammingconsultant.blogspot.com/2016/10/mip-modeling-from-sudoku-to-kenken.html
No comments:
Post a Comment