Constraint programming to ensure uniqueness of tuples of variables while minimizing number of distinct values

Question

I would like to solve the following optimization problem :

I have integer variables P[r][c][s] in -k,k with :

• r in 0, 9
• c in 0, 9
• s in 0, 3

Contraints

Those variables are under the following constraints:

• Each variable has either of the following constraints :
  • is 0 : e.g P[0][0][0]=0
  • is the opposite of an other variable : e.g. P[0][0][1]= - P[0][1][3]
• Uniqueness of tuples of variables : There are sets of tuples of variables S_i= {T_i=(P_i_0, P_i_1,…, P_i_j)} e.g.

S_0={(P[0][0][0], P[0][0][1],P[0][0][2],P[0][0][3])
,(P[1][0][0], P[1][0][1],P[1][0][2],P[1][0][3])
,…}

The tuples in each set must be all different.

Tuples sizes would be between 4 and 10^2.

Nb of tuples per set would be in the 10^3

Nb of set would be, as large as implementation permits ?, 10^6 ? I would generate those by enumerating some circuits on a graph of the variables.

Objective function

The constraints could be easily met be ensuring that each non zero variable gets a unique value, with a large enough k.

However, the true goal would be the have the tuples in each sets all different BUT as similar as possible. Similarity being defined by the number of elements with same values.

E.g. instead of having a set with {(1,2,3,4),(5,6,7,8), (9,10,11,12)}, I'd rather have {(1,1,1,1),(1,1,1,2),(2,1,1,2)}.

I assume that this kind of objective function cannot be implemented efficiently, so I'd settle for minimizing k, i.e. the range of values.

For a hand-coded solution, I'd probably try to recycle values as much as possible, backtracking until uniqueness constraints are met.

However, I was hoping that a generic solver could be more efficient. Any pointer ?

I'm open to anything that can be used from C/C++, Java, Python,…

Thanks in advance,

Answer 1

One of the most efficient CP solvers, that could be used in this problem, is OR-Tools CP-SAT solver. You can use it in several programming languages.

However, I suggest to use the CPMpy modeling library in python, which provides access to it, and has a pretty straightforward way to add constraints to your model. You basically simply write it as you wrote it here.