2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ "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 $\endgroup$
    – fontanf
    Jan 3 at 20:48

1 Answer 1

0
$\begingroup$

The first thing to understand is that in CPLEX "lazy constraints" and "user cuts" are very different thing. Long ago I wrote about the difference. The important thing here is that you use lazy constraints for the Benders cuts.

The next thing to understand (expanding on the comment from @fontanf) is that the lazy constraint callback is triggered whenever CPLEX thinks it has a new incumbent. Before the incumbent takes effect, CPLEX calls the callback. If your callback introduces a cut violated by the incumbent, the incumbent is discarded. If your callback does not produce a violated cut, then you are telling CPLEX that the new incumbent is feasible. So CPLEX will never prune nodes based on an invalid incumbent, because the incumbent will not be an incumbent until it is validated by the lazy constraint callback.

Finally, regarding your problems with the code, CPLEX ships with a number of examples of Benders decomposition. If X is the directory where CPLEX Studio is installed, then X/cplex/examples/src/python is where the Python examples are stored. The ones that implement Benders decomposition are bendersatsp2.py, bendersatsp.py, benders.py and facility.py.

$\endgroup$
2
  • $\begingroup$ Isn't the lazy constraint callback called each time a new LP subproblem is solved? since sometimes it is possible to find violated lazy constraints for fractional solutions $\endgroup$
    – fontanf
    Jan 4 at 10:20
  • 1
    $\begingroup$ With the new generic callbacks, you can set the contexts in which the callback should be called. You can add user cuts when solving node LPs and also when contemplating a new candidate, but you can only add lazy constraints (via one of the "reject" methods) in the context of a new candidate solution. What you can do, though, is find a violated lazy constraint during a node LP solve, queue it somewhere in your program's memory, and add it the next time you reject a candidate. $\endgroup$
    – prubin
    Jan 4 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.