6
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Try FICO Xpress with NO symmetry breaking constraints.. It often does a better job of recognizing and exploiting/dealing with symmetry than you do by incorporating symmetry breaking constraints. $\endgroup$ Dec 3, 2022 at 15:49
  • $\begingroup$ I have to use Gurobi for this model. $\endgroup$
    – armset
    Dec 3, 2022 at 19:03
  • $\begingroup$ Too bad. FICO Xpress is the symmetry detection and exploitation king. Gurobi benefits from good symmetry breaking constraints, as do most MILP solvers. $\endgroup$ Dec 3, 2022 at 21:24

2 Answers 2

5
$\begingroup$

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).

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ Your first constraint is dominated by your second one and can be eliminated. $\endgroup$
    – RobPratt
    Dec 3, 2022 at 14:10
  • $\begingroup$ @Kuifje Thanks for your answer, I also have edited my question. Indeed I use a binary matrix to represent which matrix value belongs to which group like you asked. Regarding (1): I don't quite understand why you propose using $x_{k,j+1}$, why index it with k? Regarding (2): This works, but sadly this takes a lot more iterations to solve the model. Still it's a good consideration and I can see where I can work from this. The rest of the answer is a bit over my skill level at the moment. I will need to take a bit more time to really digest that. $\endgroup$
    – armset
    Dec 3, 2022 at 19:44
  • $\begingroup$ Regarding (1), $k$ is just a symbol, it has absolutely no impact. I did not want to use $i$ again, as it appears on the LHS. $\endgroup$
    – Kuifje
    Dec 3, 2022 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.