Originally posted by: Eumpfenbach

So I am not experienced with object oriented programming and new to the callbacks. I am trying to learn this through trial and error and the guides, but it's difficult. My professors have not done this. I am wondering if this psuedocode is right. I am trying to solve an MIP in python with Bender's Cuts. I have the code written for generating the cuts, just need to figure out how to add cuts on the fly.

So how do I add a cut everytime I find a new incumbent? My initial thought is that I have to register both the incumbent callback and the Cut callback, then have the incumbent callback be an input to the cut callback. Is this correct? So it would be something like this (realizing I am leaving out a lot of the code details. I don't want to dump more info than is necessary for answering my question).

class Incum(IncumbentCallback):

class MyCut(CutCallback):

def __call__
{
solve dual and generate a cut
}
lhs = ...
rhs = ...
self.add(cut = ...)

master = cplex.Cplex()
master.register_callback(Incum)
master.register_callback(MyCut)
master.solve()

More than anything, I am just trying to get my method out there as soon as possible so that if my thought process is wrong, someone experienced can suggest the right path. All help is greatly appreciated! A Bender's Cut example distributed with future versions of Cplex would be awesome too, just like the column generation one. I'm sure it's a common problem type.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

reposted as code

class Incum(IncumbentCallback):
 
         class MyCut(CutCallback):
 
              def __call__
                  {
                  solve dual and generate a cut
                  }
                  lhs = ...
                  rhs = ...
                  self.add(cut = ...)
 
 
master = cplex.Cplex()
master.register_callback(Incum)
master.register_callback(MyCut)
master.solve()

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

What version of CPLEX are you using? Since version 12.3 there is the bendersatsp.py example that illustrates how to do Benders decomposition using lazy constraint callbacks. In CPLEX 12.3 it is also sufficient to use a lazy constraint callback to do what you want (add a cut whenever you find an incumbent).
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

I have been using version 12.2. That example sounds great.

I am traveling for the next couple days so it would be difficult to download 12.3 but I would like to see this example soon. If it is not too much trouble, could you email just the python example to Eumpfenbach at Wayne dot edu?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The problem is that the example only works for CPLEX 12.3 and newer.
In CPLEX 12.3 we did some changes to the cut and lazy constraint callbacks that make implementation of Benders decomposition a lot easier. The example I mentioned builds on these changed implementations.
In previous versions you have to use a mix of incumbent callbacks and lazy constraint callbacks.
The strategy there is as follows:

• Have a global queue that stores the cuts you found.
• In an incumbent callback check the incumbent for feasibility. If you find any violated cut then add that cut to the global queue and reject the incumbent.
• In the lazy constraint callback dequeue all the cuts from the global queue and inject them.

The python examples in 12.2 for lazy constraint callbacks and incumbent callbacks can show you how to implement such callbacks.
Moreover, there are several threads on this Forum (mostly for C++ or Java but the concepts are the same) that discuss the details of the approach outlined above.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

I'm working to learn the example and adapt my formulation to it. I am sure I will have a series of questions, but to start:

I'm fairly sure the example only uses the solution of the dual problem to remove infeasible solutions ("ray cuts"), not to remove feasible but inferior solutions ("point cuts"). Can point cuts also be added? I am wondering if they are redundant given that their information is contained in the branching process, or something like that? Or were they just left out by choice?

You guys have been very helpful so far and I appreciate all the help...
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

'Point cuts' are not contained in the branching process and are not left out by choice. Simply, in this example, they do not exist.

As you can see in the description of the example bendersatsp.py (i.e., in the comments to the code), the model that is decomposed and solved with Benders' cuts is a flow formulation for the Asymmetric Traveling Salesman Problem (ATSP). This model has a set of binary variables x and a set of continuous variables y.
The variables y that are removed by the decomposition do not appear in the objective function. Therefore, the dual of the flow constraints that are removed by the decomposition is defined on a cone.
This means that, whenever you solve the dual to find a violated cut, you have only two possibilities:
1. The optimal solution value of the dual is 0 --> no violated cut exists
2. The dual is unbounded --> you can find a 'ray cut' (also called a feasibility cut) by reading the unbounded ray of the dual.
You will never find a 'point cut' (also called an optimality cut) simply because the dual is defined on a cone.

In a more general context (maybe in your case), the dual is not defined on a cone, but on a polyhedron, with both vertices and rays. In such a case you have both 'ray cuts', associated with the extreme rays of the dual, and 'point cuts', associated with the vertices of the dual.
When you solve the dual you will have therefore these two possibilities:
1. The dual is bounded and the optimal solution is therefore a vertex.
In this case you need to check if the optimal solution value of the dual gives you a violated cut.
If it is the case, you can get the optimal solution of the dual and construct a 'point cut' from it.
2. As before, the dual is unbounded. In such a case you can get the unbounded ray of the dual that corresponds to a violated 'ray cut'.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

Andrea,

I am very appreciative of your response. I follow what you are saying. You say it in better mathematical terms, but some of this I figured out on my own (see the other thread I created recently). Sometimes I ask a question when I am stuck and then find the answer on my own. I won't keep two threads up for the same purpose so I will let this one go.

I now feel I understand the example pretty well. I still have unanswered questions in my other thread (just mentioning in case you are still feeling generous with your knowledge...)
#CPLEXOptimizers
#DecisionOptimization