# Logic-based Benders decomposition with integer master variables

I am looking for a paper/study in which a Logic-based Benders decomposition (LLBD) framework is used when the master problem is associated with integer variables (not specifically binary).

In general LBBD, we often send fixed binary solutions to the subproblem and the Benders cuts aim to alternate the previous solutions as "combinatorial cuts". I am just curious if LLBD could be utilized in the case of having integer master variables. I have gone through a lot of recent LBBD papers, but it seems like the master problem is always associated with binary variables.

In a previous post, it is discussed that there exist no-good cut strategies, but in general, no-good cuts are not really effective to converge the optimal solution. That is why I am curious if there exists a study where authors design effective LBBD cuts when the master variables are integer.

The state-of-the-art method for solving the vehicle routing problem with split deliveries is in fact LBBD as can be seen in the following papers:

Although the authors do not refer to their algorithms as LBBD, their methods can be seen as LBBD. The master problem employs general integer variable $$x_{ij}$$ which counts the number of times edge/arc $$(i,j)$$ is visited by any vehicles. The cut they employ has the form

$$\sum_{(i,j) \in S} x_{ij} \ge 1,$$

in which $$S$$ corresponds to the set of edges that setting their corresponding $$x$$ variables to zero (all at the same time) will certainly result in an infeasible solution. See the papers for more details.

I have been stuck in similar problem before I found out that logic-based Benders decomposition (LBBD) is nothing but an outer-approximation technique. Consider a (continues / general integer) Benders master problem:

\begin{align} \min_{X \in \mathcal{X}, \theta \geq 0} c^\top X + \theta \end{align}

where $$\theta$$ is an estimator for the subproblem:

\begin{align} Q(X) = \min_{Y \in \mathcal{Y}} q(X, Y) \end{align}

where $$X \in \mathcal{X}$$ denotes master problem variables and $$Y \in \mathcal{Y}$$ denote sub problem varaibles. Then we have the logic-based Benders cut:

\begin{align} \theta \geq \hat{Q} - \nabla^\top \cdot (X - \bar{X}) \end{align}

where $$\hat{Q}$$ is the optimal objective of subproblem with given $$\bar{X}$$ and $$\nabla$$ is gradient of $$q(X, Y)$$ on $$X$$ (master variable). Unfortunately, it is non trivial to obtain $$\nabla$$, even when domain of $$X$$ is continues, consider that $$q(X, Y)$$ itself is an optimization problem. For your problem, $$X$$ is integer, you may compute $$\nabla$$ as sub gradient (reduced cost) by domain knowledge of your problem ("logic" in LBBD). The LBBD converges when $$q(X, Y)$$ is convex.

You may refer to:

Benders in a nutshell (page6, page7)

How to determine if a given problem seems to be a good fit to be solved using combinatorial Benders decomposition