Logic-based Benders decomposition with integer master variables

Question

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.

Answer 1

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:

https://www.sciencedirect.com/science/article/abs/pii/S037722171400352X https://pubsonline.informs.org/doi/abs/10.1287/trsc.2018.0825

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.

Answer 2

Update (2023-06-06):

Our recent work introduces a logic-based Benders decomposition method with sub gradient cut, which can handle general integer (not binary) master variables.

• Guo, P., & Zhu, J. (2023). Capacity reservation for humanitarian relief: A logic-based Benders decomposition method with subgradient cut. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2023.06.006

---

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