Function 'distinct2' for 2D coordinates

[yurivict]

Is your feature request related to a problem? Please describe.

Optimize objects placed in 2-D slots. Each slot can be occupied by at most one object from a set of objects.

Describe the Feature

Similarly to distinct(home, x); introduce function distinct2(home, x, y); that would ensure that all pairs of coordinates (xᵢ,yᵢ) are pairwise different.

Why Is the Requested Feature Useful?

Very often objects that the optimization problem deals with are in a multi-dimensional space. (xᵢ,yᵢ) can represent coordinates in a 2-dimensional space. It is natural to constraint objects' occupancy to 0 or 1.

distinct2(home, x, y); is also a natural extension of distinct(home, x); - it does exactly the same but with pairs of integer coordinates instead of single integer values.

Alternatively or additionally, distinctn(home, n, x, y, z, ..., k); can be introduced that generalizes distinct to a multi-dimensional space of dimensionality n.

Currently the same distinct2 constraint can be achieved with:

        // all coordinates are distinct
        for (Object obj1 = 0; obj1+1 < Nobj; obj1++)
                        for (Obj obj2 = obj1+1; obj2 < Nobj; obj2++)
                                rel(*this,
                                        (varX[obj1] != varX[obj2])
                                        ||
                                        (varY[obj1] != varY[obj2])
                                );

However, this code combined with some linear constraints over coordinates is very slow to arrive at a first solution while distinct2 should ensure that the first solution is computed immediately, because it's very easy to find some object placement (xᵢ,yᵢ) when distinct2 is in place.

[Dekker1]

Maybe I'm not understanding correctly, but to me this sounds like you are trying to enforce a requirement very similar to Gecode's nooverlap constraint with all heights and widths set to be 1.

You might however be right that an all_different propagator might work well when all the sizes are 1, but I'm not sure if you would need any specific propagator for tuples (although it wouldn't hurt). Instead you might try arithmetic operations to combine the two coordinates into a single value. For example, something equivalent to the following MiniZinc fragment:

int: mult = ub_array(y);
constraint all_different([ x[j]*mult + y[j] | j in index_set(x)]);

[yurivict]

[...] you are trying to enforce a requirement very similar to Gecode's nooverlap constraint with all heights and widths set to be 1.

nooverlap should be similar. However, for 1-dimensional optimization problem with distinct and several linear constraints the first solution is found immediately, as it should be. For the equivalent 2-dimensional problem with nooverlap with all widths/heights equal to one the first solution isn't found immediately. Finding some solution of such problems is trivial: any placement of objects is ok as long as they don't intersect.

So nooverlap doesn't work quite as distinct in that it doesn't find the first solution instantly,

[zayenz]

It is worth noting that propagation for multi dimensional indexes can never be as good as for single dimensional indexes. Consider a case with 9 potential places to allocated your objects arranged in a 3 by 3 grid, with 4 objects allocated

      j
      0 1 2
     -------
i  0 |X| | |
     -------
   1 | | |X|
     -------
   2 |X|X| |
     -------

Even though four places are occupied (indicated with X), no propagation can be done since all values are still valid for both iand j.

If you need strong propagation, encoding the grid positions into 1-dimensional values as Dekker1 shows in his comment is probably the best way to achieve this.

[zayenz]

Considering further, I will close this issue. Not because a distinct2 wouldn't be nice for modelling, but for the reason above: it would have worse propagation than expected and thus lead people into models with surprising behaviour. This is already evident with models that use multi-dimensional element which has the same issue.

And as said, nooverlap is the most straight forward idea, and turning the grid into a single dimensional array for the purposes of placements will give the best propagation.