# Implementing Logic-based Benders decomposition on a single search tree

Currently, I am working on a scheduling problem and trying to approach it by the logic-based Benders decomposition method. Theoretically, I have everything, i.e., the master and sub problem(s), the feasibility and optimality cuts (or as in logic-based context: combinatorial cuts) and implemented the algorithm in a traditional way: solve the master problem [in my case by the CPLEX in Python API], find the cuts, add the cuts to the master problem, solve the master problem again and ... .

I found out that there is a general trend in literature in using the Benders decomposition approach in "one tree" branch and cut structure. I have read several materials and grasped the general concept, but still have some questions. I would be grateful if anyone could please help me:

1. I still don’t get how the branch and cut with the lazy or user constraints procedure works. I especially can’t understand how the CPLEX expands the tree as it generates a new cut at each node and updates the constraints pool. For example, in my problem, at any incumbent node of the master problem, a specific type of cut can be inferred. This cut is supposed to be added to the cut pool and checked on the other nodes. My puzzlement is regarding the tree. Assume that one of the early nodes of the master is pruned/disregarded due to the fact that its lower bound is worse than the initial best bound (we have a min problem). However, later on and after adding several sets of cuts- and lifting the lower bound, it turns out that the node was actually the optimal solution. What would happen now? How the CPLEX treat this case? For more clarification: I do understand the mechanism of the callbacks (and the difference between lazy and user cuts), but what I am struggling with is how the cuts are generated and put into the pool. Based on the algorithm, no cut is known at the beginning, but rather, the cut might be introduced as the master problem is solved and the solution checked in the subproblems. Therefore, the pool starts empty, and grows dynamically, as a solution to the master problem is found. I can't see how it works in a single-tree structure. In my eyes, the CPLEX should work as follows: It generates the tree of the master problem, whenever it reaches an incumbent, the subproblems are checked and some cuts are generated and added to the pool. Then the new cuts must be checked also on the other [already visited] nodes and the tree gets updated anytime a cut is found. Do I understand it correctly? Have I misunderstood something?

2. I also face programming problems in implementing the algorithm on a single tree in Python using CPLEX. I face some nonsensical errors which can't debug effectively. Unfortunately, I can’t trace the errors from the IBM community, or find any simple but accurate implemented template or resource.

• "Assume that one of the early nodes of the master is pruned/disregarded due to the fact that its lower bound is worse than the initial best bound": if a node is pruned, then it means that a feasible solution with better cost is known. Feasible means feasible after the lazy check. So the optimal node can't the lost that way Jan 3 at 20:48