Breaking symmetry of permutations in LIP

Question

Setup

I have a $N \times M$ matrix with integer values and I need to group it into $K$ groups (subject to constraints). Internally I work with a flattened 1D list as I don't see any benefits of using this two-dimensionality, but I can change this if needed.

I have already a working solution to create these different groups and I would like to improve this model via symmetry breaking.

Edit:

I have a binary matrix $x_{i,j} \in \{0,1\}$ that takes value 1 if the matrix value i is assigned to group j, as asked by @Kuifje. An additional constraint I didn't mention is that the group have to be roughly in equal size.

Example:

I have a $2 \times 4$ matrix, thus $8$ elements, and I want to group them into $3$ groups named $A, B$ and $C$.

One possible way to create these group is:

matrix value	-4	1	-4	5	1	-1	4	3
group	A	A	C	B	C	B	B	C

Which is the same as saying (group $A$ and $B$ flipped, marked in bold):

matrix value	-4	1	-4	5	1	-1	4	3
group	B	B	C	A	C	A	A	C

The only thing which matters is how these fields are grouped, not to which particular group they belong.

Ideas:

I already have a symmetry breaking constraint which fixes field $0$ to group $A$, this removes already a few of the possible permutations. But I believe there is more performance gain possible.

Question

How can I extend my idea above to create more symmetry breaking constraints? Alternatively: is there a better way to model this, so that no symmetry breaking is needed?

Answer 1

Let $V_i$ be the $i$-th matrix value. One way to break symmetry would be to require that the groups be labeled in ascending order of their sum. The constraints would be $$\sum_i V_i x_{i1} \le \sum_i V_i x_{i2} \le \dots \le \sum_i V_i x_{iG}$$ where $G$ is the desired number of groups. This has a better chance of helping when there is substantial diversity in the matrix entries (and thus, hopefully, the group sums).

Answer 2

It would help a little if you detailed the formulation of the model you are using.

Assuming you are using binary variables $x_{i,j} \in \{0,1\}$ that take value $1$ if matrix value $i$ is assigned to group $j$, you could add the following ordering constraints: $$ \sum_{i}x_{i,j} \ge x_{k,j+1} \quad \forall k,\; \forall j \tag{1} \label{1} $$ This ensures that group $j+1$ is not used until group $j$ is. Then you can order the groups by non increasing size with: $$ \sum_{i}x_{i,j} \ge \sum_{i}x_{i,j+1} \quad \forall j \tag{2} \label{2} $$

As noted by @RobPratt in the comments below, constraints \eqref{1} are dominated by constraints \eqref{2}, and can therefore be eliminated.

Depending on the nature of your problem (the other constraints), you could maybe adapt cover/clique/knapsack cuts.

Alternatively, you could decompose the problem with a Dantzig-Wolfe formulation as follows. Let $\lambda_u \in \{0,1\}$ be a binary variable that takes value $1$ if and only if predefined group $u \in \Omega$ is selected. Let $c_u$ be the cost of group $u \in \Omega$. You want to minimize the cost of your selection: $$ \min \; \sum_{u \in \Omega}c_u \lambda_u $$ subject to set covering constraints (a matrix item is selected exactly once): $$ \sum_{u \in \Omega, j\in u} \lambda_u = 1 \quad \mbox{for each matrix value }j $$ You can, depending on your initial problem, limit the number of groups with convexity constraints (or impose a number of groups): $$ \sum_{u \in \Omega} \lambda_u \le K $$ where $K$ is an upper bound on the number of groups.

Of course, this is only part of the problem, as you need to either predefine all possible groups (this may be an option depending on your problem) or define them dynamically with a column generation approach. Without more knowledge of your problem, it is not possible to detail any more.