12

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?
Jasper
  • 221
  • 2
  • 5

1 Answers1

5

The implied cuts may not be worth adding. Depending on how the solution process goes (solving the master to "optimality" each time before solving the subproblem, versus a "one tree" approach), it might be better to just let the master problem identify the relevant cuts (by generating solutions that violate them).

That said, if you are using a solver, it may have some provision for adding extra cuts to a pool, where they are used to test solutions (before the solutions are passed to your subproblem) but are not part of the matrix calculations until they become relevant. CPLEX, for instance, has "lazy constraints".

If your subproblem is moderately slow to solve, you might cache the cuts it produces (along with the transitive relation) in your code. When your code receives a solution from the master problem, it can test whether the combination of dominance and a previous cut blocks the solution, and if so return the corresponding cut without actually solving the subproblem. Testing all possible "dominating" combinations could be pretty slow, in which case perhaps some compromise would be best (e.g., try up to five dominating combinations, and if none produce violated cuts, go ahead and solve the subproblem).

prubin
  • 39,078
  • 3
  • 37
  • 104
  • I'm using Gurobi, and I'm adding these cuts as lazy cuts at incumbent nodes that yield subproblem-infeasible solutions. I did store the cuts and dominance relations in the sub-problem before, but the subproblem is sufficiently fast to be about as fast as a simple lookup data-structure. My goal is not to test for all dominating combinations, but to capture this dominance in the variables of the MP. – Jasper Jan 24 '20 at 08:22
  • I now often find that we have -- say -- 50 entities {1, ..., 49, 50}. The sub-problem may induce a cut that only two of {1, 2, 3} could be feasible. But that also applies to many other triplets in {1, ..., 50}. So when adding the first cut, the MP comes with a new solution {1, 2, 4}, {1, 2, 5}, ... time after time. This number could already explode. – Jasper Jan 24 '20 at 08:22