5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.