# Improving cuts from sub-problem with problem-specific hierarchical information

I'm solving an assignment-alike problem with a Logic-based Benders decomposition-alike (LBBD) method. The master problem provides an assignment, which is checked in the sub-problem.

Define the set of binary variables $$x_i \in \{ 0, 1 \}$$ representing the assignment of entities $$i \in X$$ in the problem.

The Benders sub-problem generates various (feasibility) cuts $$\sum_{i \in S} x_i \leq k$$ with $$1 < k \in \mathbb N$$ some constant, where $$S \subseteq X$$ is a subset of entities featured in the sub-problem.

These generated cuts are often not strong, because they are too specific on a small set of entities, of which many may exist. This slows down the convergence of the method significantly.

I have external information regarding the sizes of the entities, which is not yet captured in the master problem. For every pair of entities $$i, j \in X$$ it is known which is the larger entity. Being "larger" ($$\succeq$$) is a transitive relation. Given a constraint $$\sum_{i \in S} x_i \leq k$$ it is possible to interchange variables $$x_i$$ (or a set of variables $$x_i$$) with variables $$x_j$$ with $$j \succeq i$$, as long as $$j \notin S$$. This gives a new valid cut. The problem is that there may exist too many of these to add them practically.

As an example: If I have a certain cut $$x_1 + x_2 + x_3 \leq 1$$ and know that $$1 \prec 2 \prec 3 \prec 4$$ and $$3 \prec 5$$, then the following cuts are also valid: $$\begin{gather} x_1 + x_2 + x_3 \leq 1 \\ x_2 + x_3 + x_4 \leq 1 \\ x_1 + x_2 + x_5 \leq 1 \\ x_1 + x_4 + x_5 \leq 1 \\ \dots \end{gather}$$

Because from a single generated sub-problem cut many other cuts can be generated, I am looking for a method to capture adding general cuts in the master problem without adding them explicitly.

My attempt was to introduce new variables $$\xi_i$$ for $$i \in X$$ that impose an upper bound on the variables $$x_j$$ with $$i \preceq j$$ in some way. Then the cuts are added on the $$\xi$$-variables rather than the $$x$$-variables.

The simplest master problem constraint $$x_j \leq \xi_i$$ does certainly not work, because if $$1 \prec 2$$ the cut $$\xi_1 + \xi_2 \leq 1$$ implies $$2x_2 \leq 1 \Rightarrow x_2 = 0$$. Simple extensions like $$x_j \leq \xi_i + x_i$$ and $$x_i \leq \xi_i$$ introduce other limitations.

I would be helped with suggestions in the following directions:

• In many papers applying LBBD such symmetry breaking is not discussed. Is there any name for such symmetry breaking that I can look at in other literature?
• Is there a structure that I can use?