Originally posted by: razorgator

I'm working on a Bender's decomposition implementation. From reading this forum, it appeared that utilizing lazy constraints (via callbacks) was appropriate. Therefore, I have a "LazyConstraintCallback" that first checks to see if the solution at each node is feasible with respect to integrality. If that node's solution is 'feasible', then a subproblem is solved to determine the appropriate Bender's cut to add (if necessary).

My key question is (assuming that you agree with this implementation of Bender's), is there any problem with using a "LazyConstraintCallback" to add a constraint that contains a continuous variable (which is true in my case)?

Currently, the implementation yields correct results for some experiments and incorrect results in others. Interestingly, the 'incorrect' results consistently have an objective value 'inferior' to the true optimal.

Thanks for any help that anyone can lend.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> razorgator wrote:
> I'm working on a Bender's decomposition implementation. From reading this forum, it appeared that utilizing lazy constraints (via callbacks) was appropriate. Therefore, I have a "LazyConstraintCallback" that first checks to see if the solution at each node is feasible with respect to integrality. If that node's solution is 'feasible', then a subproblem is solved to determine the appropriate Bender's cut to add (if necessary).
>
> My key question is (assuming that you agree with this implementation of Bender's),

Not entirely -- see below.

> is there any problem with using a "LazyConstraintCallback" to add a constraint that contains a continuous variable (which is true in my case)?

No, this looks okay. I generally use a plain cut callback, but in the Java API I don't think there's any difference between a CutCallback and a LazyConstraintCallback. As I understand the CPLEX nomenclature, you do not want a UserCutCallback. As far as including a continuous variable in the cut, there are no restrictions on what types of variables are included in the cuts (nor in how many cuts you add at one time).
>
> Currently, the implementation yields correct results for some experiments and incorrect results in others. Interestingly, the 'incorrect' results consistently have an objective value 'inferior' to the true optimal.

Which suggests that you are somehow cutting off the true optimal solution. It's possible your approach is failing to add "objective support" cuts that would flag a new incumbent as actually worse than it looks (and hence suboptimal).

My first reservation with your approach is the fact that you are testing the solution and generating a Benders cut in a cut callback. CPLEX calls the cut callback early in the processing of a node, after it has solved the node LP. After it is done with the node LP (and any iterations of the cut callback), it may invoke various heuristics that may result in an "incumbent" being found. If that incumbent is actually infeasible in the original problem, you won't have a chance to generate the corresponding Bender's cut, because the cut callback will not be called again at that node.

When I do Benders, I typically generate cuts only from new incumbents (integer-feasible solutions to the master problem with better objective values than any previously accepted solutions). Other people will sometimes generate Benders cuts from non-incumbents (which usually means solutions that are optimal in the node LP but not integer-feasible). If you're doing what I do, the safest way IMHO is to use an incumbent callback to test every incumbent. If the incumbent is infeasible (or if it's feasible but has a misstated objective value in the master), the incumbent callback generates and queues the requisite Benders cut(s) and then rejects the incumbent. This is paired with a cut callback that does not inspect the node solution but simply checks whether there are cuts queued; if there are, it adds any queued cuts and clears the queue.

I also use a branch heuristic. (This is the tricky part.) It can happen that I reject an incumbent, the cut callback is not called again at the current node, and CPLEX does not know how to branch. (I'd rather not squeeze the gory details into this message.) So the branch callback (which is called at every node) looks at the cut queue. If no cut is queued, it returns without doing anything (and CPLEX branches as usual). If it sees a non-empty queue, the branch callback creates a single child node by adding those cuts (but does not clear the queue). The same cuts will be added globally the next time the cut callback is invoked. Meanwhile, the child node is essentially the parent node plus the Benders cut(s), and is processed normally.

HTH,
Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: ORman

Paul,

I have a similar problem with my Benders implementation.
Actuaaly, I tried two test intances.
For the first one, my (branch & cut) Benders code works till searching 180000 nodes, the it quit.
For the second, which is a pretty small problem, it goes into my cut callbacck function for the root node, and then it does not go to my cut call back function anymore, and produces some wrong optimal solution as output of my code.
I thought it might be related to what you have written here: "My first reservation with your approach is the fact that you are testing the solution and generating a Benders cut in a cut callback. CPLEX calls the cut callback early in the processing of a node, after it has solved the node LP. After it is done with the node LP (and any iterations of the cut callback), it may invoke various heuristics that may result in an "incumbent" being found. If that incumbent is actually infeasible in the original problem, you won't have a chance to generate the corresponding Bender's cut, because the cut callback will not be called again at that node."

I did not get exactly what you mean? could you describe it in further details?

Thanks so much for you time and help in advance!
Jim
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: ORman

By saying "wrong optimal solution", I mean a solution which does not satisfy the subproblems.

Thanks again!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The comment you cited applies to earlier versions of CPLEX. If you are using 12.3 (or higher, when hight becomes available), you can ignore it. As of 12.3, all you need is a LazyConstraintCallback that tests the proposed incumbent and, if it found wanting, adds a Benders cut that makes the proposed solution infeasible.

With earlier versions, I had to use three callbacks (cut, incumbent and branch). I'll skip the details unless they are necessary (meaning you're on an older version and can't upgrade).

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Thanks for your answer Paul!

I am using CPLEX 12.2 callable library.
Now because of incorrect answer of my code, I see why I need to use incumbent, but I can't see why I should use branch callback?

Thanks!
Jim
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> amindehghanian wrote:
>
> I am using CPLEX 12.2 callable library.
> Now because of incorrect answer of my code, I see why I need to use incumbent, but I can't see why I should use branch callback?

I'm not 100% sure it's necessary. Let's say that, at node that contains the optimal solution, the LP relaxation does not produce an incumbent but one of the heuristics does, and let's say that you want to reject that incumbent. So the incumbent callback does the Benders magic and queues a cut, and then rejects the incumbent. In CPLEX versions < 12.3, the cut callback will not be called again at this node; so the new Benders cut will be applied to existing nodes, and to any offspring of the current node, but not to the current node itself. You've rejected the incumbent, so the question now is what does CPLEX do with the current node? Does it branch and, if so, how? I'm not positive, but I think some of the heuristics might tighten bounds so that the proposed incumbent is now a corner of the modified LP. If the LP solution remains non-integer, CPLEX can branch as normal (and the queued Benders cut should be applied to the children when the cut callback is called next); but if the LP solution is not integer (but not correct according to the subproblems), will CPLEX branch in a "random" manor (partition the node arbitrarily), or will it prune the node (undesirable if the true optimum is lurking in it), or what?

Again, let me emphasize that I'm not sure the branch callback is needed. It can't hurt, though, and I seem to recall having a reason (circa CPLEX 9.x) to think it was needed if some specific combination of events occurred. I used the branch callback just to add the Benders cut to the current node, but I may have been wasting my time doing so. According to informed sources, it is definitely not needed in 12.3, because new incumbents in 12.3 automatically trigger the lazy constraint callback before they trigger the incumbent callback.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Thanks Paul!
I just heard from CPLEX. It seems CPXsetcutcallbackfunc does the job, so we don't need anything else.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: razorgator

Thanks, Paul. That helps a lot.

I started a new implementation, based on your suggestions. I think I have kind of an amateur problem, so I guess I'll ask an embarrassing question.

How do you recommend developing the 'flag' that the cutCallBack looks at to see if any cuts should be added? I want to set this 'flag' to true if a new incumbent is found and a new cut is added to the queue. However, when I get into the cutCallBack, the updated value for 'flag' (as well as the queue of cuts) hasn't been updated. Do you create a separate class or function? FYI...I'm using Java for the first time with Concert (typically a C++ person, but my collaborator had already developed a large amount of code in Java).

Thanks again for your help.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> razorgator wrote:
> Thanks, Paul. That helps a lot.
Welcome.
>
> I started a new implementation, based on your suggestions. I think I have kind of an amateur problem, so I guess I'll ask an embarrassing question.
>
> How do you recommend developing the 'flag' that the cutCallBack looks at to see if any cuts should be added? I want to set this 'flag' to true if a new incumbent is found and a new cut is added to the queue. However, when I get into the cutCallBack, the updated value for 'flag' (as well as the queue of cuts) hasn't been updated. Do you create a separate class or function? FYI...I'm using Java for the first time with Concert (typically a C++ person, but my collaborator had already developed a large amount of code in Java).

I went from FORTRAN to C (gun pointed at my head) to C++ (large caliber gun pointed at my head) to Java, where I've found considerable relief.

I usually have the instance of IloCplex belong to an instance of some Java class I created (call it A). The callbacks are instances of classes I create that extend the respective CPLEX classes (so for instance I may have a class C that extends IloCutCallback, and attach a new instance of C to my IloCplex object). The callback classes may be standalone (globally visible) classes or local classes (within A).

Now A maintains the cut queue (the cut queue is a member field of A). I don't use a separate flag for "something is waiting"; the cut and branch callbacks just check for queue size > 0.

So all that's left is to tell the callback instances where to find the queue. That's one reason I extend IloCutCallback rather than using it directly. The constructor for class C (my extension of IloCutCallback) takes the queue as an argument and stores it as a member field of C. (Something to keep in mind is that, in Java, passing an object as an argument automatically passes a pointer. So I'm not literally storing another queue in the callback object, I'm just storing a pointer to the queue maintained in A. None of that C++ referencing/dereferencing nonsense.)

I hope that makes sense.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: razorgator

Paul,

Most of this makes sense, thank you. I've been working on the new implementation today. I have created a class called "CallbackInfo" that has the queue as a member. In my Master Problem code (creating the cplex model) I create a new CallbackInfo object. Then, when I tell cplex.use which about the callbacks to use, I pass along this newly created object (which I hope to (i) change in the IncumbentCallback and (ii) use in the cutCallback).
In addition to the Incumbent Callback, I have a Cut Callback defined below. Am I passing this appropriately? While I believe I've added the cut(s) to CBI.cutVectordelta (which stores the cuts), my debugging efforts suggest that CBI.cutVectordelta has a size of 0 when the cutCallBack is triggered (I can add the Incumbent code, if this is useful, but I pass CBI in the same way).

Thanks again!

static class cutCallBack extends IloCplex.CutCallback{

CallbackInfo cbinfo;

cutCallBack(CallbackInfo CBI) {cbinfo=CBI; }

public void main() throws IloException {

System.out.println("Size"+cbinfo.cutVectordelta.size());
\\Add appropriate cut(s) from queue
}
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I assume cbinfo.cutVectordelta is declared public, else I don't think this would compile. Personally, I don't think I would declare the cutCallBack class static, but I don't think that would create a problem. So what you're showing so far looks okay, I think.

It might help if you posted the skeleton of all relevant classes: the own that owns the IloCplex instance; CallbackInfo; the class that extends IloCplex.IncumbentCallback; and what you've shown above. Seeing any statements that declare/create relevant objects, and the IloCplex.use statements, might be beneficial. There's no need to post the bulk of the code, of course.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: razorgator

Hi Paul,

The skeleton below does seem to be adding cuts now (I changed it a great deal since my last post), but my implementation is not getting the correct answer. I'm concerned that either (i) I'm not doing the branchcallback correctly or (ii) I'm incorrect in believing that getObjValue() in the incumbent function returns the objective of the current incumbent being considered.

Please let me know if you have any words of wisdom :).

Thanks again!
//Class containing IloCplex instance and Vector containing cut (I only generate one at a time)
public class CallbackInfo {

public IloCplex cplexBenders;
public Vector<IloRange> cuts =new Vector<IloRange>();
}

---

static class IncCallBack extends IloCplex.IncumbentCallback{
IloNumVar[] Z_sp; //Master problem variable
IloNumVar][ delta_sp; //Master problem variable
IloNumVar theta; //Master problem variable
IncCallBack(IloNumVar] z, IloNumVar[[] delta, IloNumVar thetaCur) { Z_sp=z; delta_sp=delta; theta = thetaCur; }

public void main() throws IloException {
//Solve subproblem

double subObj_callback = mySP2.get_subObj(); //objective of subproblem
double thetaVal_callback = getValue(theta);
double UB_callback = getObjValue(); //this represents the objective of the incumbent solution being considered
double LB_current_callback = UB_callback - thetaVal_callback + subObj_callback; //lower bound
if((UB_callback-LB_callback)>.0001)//(the solution from the Master has an 'incorrect' objective, so add cut/reject incumbent)
{

//code for generating cut is here
CBI2.cuts.add(cut); //add cut to vector
reject(); //reject incumbent
}
}
}

---

public class cutCallBack extends IloCplex.CutCallback{

cutCallBack() { }
public void main() throws IloException {

if(CBI2.cuts.size()>0)
{
add(CBI2.cuts.firstElement()); //add cut
CBI2.cuts.clear(); //clear cut
}
}
}

---

public class branchCallBack extends IloCplex.BranchCallback{

branchCallBack() { }

public void main() throws IloException {

if(CBI2.cuts.size()>0)
{
makeBranch(CBI2.cuts.firstElement(),getBestObjValue()); //create single branch with cut

}
}

}

---

CBI2 is declared publicly in the class in which the master problem resides
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Paul,

would please correct me if I am wrong but I am not sure if the cutcallback and branch callback implementation are correct.
There might be more than one cut in the queue, isnt it? ???!?

I put some more comments here which might be helpful.

One thing I am experiencing is that, rejecting an incumbent is tricky! There are cases where you reject the incumbent but it again returns especially if it is found by heuristic!!! you reject an incumbent then cplex chooses to branch on one of the variables which is already integer! This combined with the branch callback will push you in a trap and stalling condition for a while!

This is specially the case when you have a continuous variable whose bound is significantly larger than the others and objective function motivates it to be closer to upper bound.
Another thing which is worth mentioning is that, detecting the optimal solution is not always trivial. Which one you would choose:
1) the integer solution which cplex terminates on with zero optimality gap?
2) or the one you record by yourself?

I would rely on the second one!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Shahin,

> Shahin G wrote:
> Paul,
>
> would please correct me if I am wrong but I am not sure if the cutcallback and branch callback implementation are correct.
> There might be more than one cut in the queue, isnt it? ???!?

In general, yes; but the comment in razorgator's first line of code says he's generating one cut at a time.
>
> I put some more comments here which might be helpful.
>
> One thing I am experiencing is that, rejecting an incumbent is tricky! There are cases where you reject the incumbent but it again returns especially if it is found by heuristic!!!

That's certainly possible, unless in rejecting the incumbent you add a global cut that makes the incumbent infeasible. The nature of what I've been working on is that all my Benders cuts are feasibility cuts. If I were sometimes adding optimality cuts (the proposed incumbent really is integer-feasible, but the master problem variable z that represents the subproblem objective contribution is wrong), then the same integer solution could reasonably repeat immediately (with a tightened value of z ).

> you reject an incumbent then cplex chooses to branch on one of the variables which is already integer! This combined with the branch callback will push you in a trap and stalling condition for a while!

If you reject an incumbent without necessarily adding a cut that cuts it off, that's possible. I wondered what would happen if you rejected an incumbent, without adding a cut that invalidated it, when the incumbent was an integer-feasible node LP solution. Someone at IBM told me that CPLEX would attempt to branch by arbitrarily picking an integer variable with an integer value at that node and then branch on it (I guess by bounding it >= value + 1 in one child and <= value - 1 in the other). The choice of variable is apparently rather arbitrary. It's never been a problem for me, again perhaps because all my cuts are feasibility cuts.

> This is specially the case when you have a continuous variable whose bound is significantly larger than the others and objective function motivates it to be closer to upper bound.
>
>
> Another thing which is worth mentioning is that, detecting the optimal solution is not always trivial. Which one you would choose:
> 1) the integer solution which cplex terminates on with zero optimality gap?
> 2) or the one you record by yourself?
>
> I would rely on the second one!

I don't follow you here. Are you saying that you record incumbents along the way and then reject them? I don't (if I reject them, they're not feasible). I sometimes record accepted incumbents (if I'm not sure I'm going to let CPLEX run to optimality), but CPLEX's final incumbent is always at least tied for optimal in my experience.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

>>In general, yes; but the comment in razorgator's first line of code says he's generating one cut at a time.

Is that under our control how many times an incumbent callback is called before a cutcallback? what if p consecutive incumbents are found by heuristic? Then dont you generate cut for that?

>
> I put some more comments here which might be helpful.
>
> One thing I am experiencing is that, rejecting an incumbent is tricky! There are cases where you reject the incumbent but it again returns especially if it is found by heuristic!!!

>>That's certainly possible, unless in rejecting the incumbent you add a global cut that makes the incumbent infeasible.
This is in fact true; To my experience which I have carefullly inestigated it (I believe) there are cases where you add the benders cut but the solution is not cut off because of bound on the linking variable; think of a minimization problem which has a negative linking variable and always-positive subproblem. You cut the solution once but it comes back again with same values for integer solutions but a different value for linking variable.

>> The nature of what I've been working on is that all my Benders cuts are feasibility cuts. If I were sometimes adding optimality cuts (the proposed incumbent really is integer-feasible, but the master problem variable z that represents the subproblem objective contribution is wrong), then the same integer solution could reasonably repeat immediately (with a tightened value of z ).

May I ask whatdo you do with the optimality cuts because you say you alsways do with feasibility ones? when do you add them? As far as I know once the feasibility cuts are finished then you have to start generating optimality ones; of course there are cases where you are lucky enough for proving the optimality with feasibility ones. What if not?
In the later case, the same solution with tightened z: what is your solution for that ?

>> If you reject an incumbent without necessarily adding a cut that cuts it off, that's possible. I wondered what would happen if you rejected an incumbent, without adding a cut that invalidated it, when the incumbent was an integer-feasible node LP solution. Someone at IBM told me that CPLEX would attempt to branch by arbitrarily picking an integer variable with an integer value at that node and then branch on it (I guess by bounding it >= value + 1 in one child and <= value - 1 in the other). The choice of variable is apparently rather arbitrary. It's never been a problem for me, again perhaps because all my cuts are feasibility cuts.

If I am lucky enough to have binary variables perhaps I can use combinatorial cuts to avoid thus loop but for geeneral integer I dont have any solution for that.

>> I don't follow you here. Are you saying that you record incumbents along the way and then reject them? I don't (if I reject them, they're not feasible). I someti>>mes record accepted incumbents (if I'm not sure I'm going to let CPLEX run to optimality), but CPLEX's final incumbent is always at least tied for optimal in my experience.

I was wrong in part of this comment but the second part my question is what is the relation betweek the objective function values of the convergence node of branch-and-bound and the optimal solution of the problem. I can see the cases where there is NO relationship. Would you confirm that?
In certain case with + - coeffs in the objective this way of impelemting Benders terminates with objective like -10e15 (influenced by z) while the optimal solution is much less something line -10e8.

In general what I wasn to say is that when signs do not follow the textbook examples then we are in trouble with the callback implementation of Benders.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> Shahin G wrote:
> >>In general, yes; but the comment in razorgator's first line of code says he's generating one cut at a time.
>
> Is that under our control how many times an incumbent callback is called before a cutcallback? what if p consecutive incumbents are found by heuristic? Then dont you generate cut for that?

Those p incumbents would all have to be found at a single node, since the cut callback is called at the next node. My impression is that an incumbent callback is called at most once at a node -- if CPLEX finds an incumbent, it stops looking at that node, even if the incumbent is rejected -- but I'm not positive that is true. I'm looking into it more carefully. If multiple incumbents can be found at a single node, then you are right: multiple cuts may need to be generated. I always use a queue and never assume there is just one cut, just to be safe.
>

> >> The nature of what I've been working on is that all my Benders cuts are feasibility cuts. If I were sometimes adding optimality cuts (the proposed incumbent really is integer-feasible, but the master problem variable z that represents the subproblem objective contribution is wrong), then the same integer solution could reasonably repeat immediately (with a tightened value of z ).
>
> May I ask whatdo you do with the optimality cuts because you say you alsways do with feasibility ones? when do you add them?

There are no optimality cuts in the problems I've been working on lately, because the subproblem has no objective contribution. Basically the master problem is a set covering problem with all binary variables. The subproblem tests whether a proposed cover is actually valid and, if not, generates a Benders cut that equates to another set to be covered.

>As far as I know once the feasibility cuts are finished then you have to start generating optimality ones; of course there are cases where you are lucky enough for proving the optimality with feasibility ones. What if not?

In general cases, you are correct -- you will need both optimality and feasibility cuts (and even after you start generating optimality cuts, you may still generate more feasibility cuts).

> >> If you reject an incumbent without necessarily adding a cut that cuts it off, that's possible. I wondered what would happen if you rejected an incumbent, without adding a cut that invalidated it, when the incumbent was an integer-feasible node LP solution. Someone at IBM told me that CPLEX would attempt to branch by arbitrarily picking an integer variable with an integer value at that node and then branch on it (I guess by bounding it >= value + 1 in one child and <= value - 1 in the other). The choice of variable is apparently rather arbitrary. It's never been a problem for me, again perhaps because all my cuts are feasibility cuts.
>
> If I am lucky enough to have binary variables perhaps I can use combinatorial cuts to avoid thus loop but for geeneral integer I dont have any solution for that.

If you are adding optimality cuts, it may very well be that you do not want CPLEX to abandon the integer portion of the solution at the current node. That's one reason why I use the branch callback -- it creates what is in essence a clone of the current node with the optimality cut added, and lets CPLEX solve the expanded LP again. The new solution may just be the old solution with a tighter value for the linking variable, in which case maybe it will actually be feasible. If it's not the same solution, and it's not a valid incumbent, maybe the new LP solution will have fractional values that give CPLEX a meaningful place to pivot. Or maybe the tighter linking value will cause CPLEX to prune the node.
>
> >> I don't follow you here. Are you saying that you record incumbents along the way and then reject them? I don't (if I reject them, they're not feasible). I someti>>mes record accepted incumbents (if I'm not sure I'm going to let CPLEX run to optimality), but CPLEX's final incumbent is always at least tied for optimal in my experience.
>
> I was wrong in part of this comment but the second part my question is what is the relation betweek the objective function values of the convergence node of branch-and-bound and the optimal solution of the problem. I can see the cases where there is NO relationship. Would you confirm that?

I cannot recall ever having a problem where CPLEX decided the gap (relative or absolute) was small enough to declare victory but the objective was incorrect, other than in one fairly specific instance (with an older version of CPLEX) where I tripped over a bug. The bug has since been fixed.

> In certain case with + - coeffs in the objective this way of impelemting Benders terminates with objective like -10e15 (influenced by z) while the optimal solution is much less something line -10e8.

My objective values are always much smaller than that in magnitude. I wonder if there could be numerical conditioning issues in play?
>
> In general what I wasn to say is that when signs do not follow the textbook examples then we are in trouble with the callback implementation of Benders.

I don't really see why negative linking values or a mix of addition and subtraction in the objective would cause problems. I'll confess that my set covering master problem has quite a simple objective function, but logically I don't see why a mix of signs would cause Benders any indigestion.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> Paul Rubin wrote:
> > Shahin G wrote:
> > >>In general, yes; but the comment in razorgator's first line of code says he's generating one cut at a time.
> >
> > Is that under our control how many times an incumbent callback is called before a cutcallback? what if p consecutive incumbents are found by heuristic? Then dont you generate cut for that?
>
> Those p incumbents would all have to be found at a single node, since the cut callback is called at the next node. My impression is that an incumbent callback is called at most once at a node -- if CPLEX finds an incumbent, it stops looking at that node, even if the incumbent is rejected -- but I'm not positive that is true. I'm looking into it more carefully. If multiple incumbents can be found at a single node, then you are right: multiple cuts may need to be generated. I always use a queue and never assume there is just one cut, just to be safe.

I just heard back from someone at IBM. It turns out that the incumbent callback can indeed be called multiple times at the same node, whether or not the incumbents are rejected. So you're right, Shahin -- razorgator needs to cover the possibility of multiple cuts being generated at one node. I suspect that it's also possible that multiple heuristics might find the same incumbent at the same node; if so, you might end up rejecting it more than once and adding redundant constraints. I don't think that is likely enough to warrant the effort of checking for redundant constraints, though.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Paul,

part of the thing I am saying is that, if you have a problem which has negative objective function then your linking variables if a negative variable. In the such case it is possible that when cplex terminates after the process you explained, there is not a known relationship between the objective function value upon which cplex terminated and the optimal objective value of the original problem.
Even, this might lean to a premature convergence to a non-optimal solution. At least that is what I am witnessing.

I can share an old piece of code of mine code with you to see that this is in fact the case there.
At some point one does not find the optimality/feasibility cuts for a while but the bound is in fact changing and cplex gets closer to optimality to a nonsense objective value.

My main argument is that, in most part of the theory and practice, what you are saying is in fact correct. But there is something going on in cplex which avoids it to be valid for all the cases.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Shahin,

> Shahin G wrote:
> part of the thing I am saying is that, if you have a problem which has negative objective function then your linking variables if a negative variable. In the such case it is possible that when cplex terminates after the process you explained, there is not a known relationship between the objective function value upon which cplex terminated and the optimal objective value of the original problem.
> Even, this might lean to a premature convergence to a non-optimal solution. At least that is what I am witnessing.

So you are experiencing a failure to generate necessary optimality cuts?
>
> I can share an old piece of code of mine code with you to see that this is in fact the case there.
> At some point one does not find the optimality/feasibility cuts for a while but the bound is in fact changing and cplex gets closer to optimality to a nonsense objective value.

Is this a minimization problem, and is CPLEX producing an "optimal" solution that is to low (meaning the contribution of the linking variable is too negative)?

Assuming minimization, the bound will of course be lower than the true optimum until CPLEX completes. Are you saying that CPLEX actually terminates with an artificially low objective value, or just that the bound appears to be converging to something too low? To me, that latter is not a sign of a problem -- in all sorts of problems, not just Benders, I see lower bounds that I know are much lower than the true optimum and either look like they're converging to something to low or simply stall out (and look as if they've already converged).
>
> My main argument is that, in most part of the theory and practice, what you are saying is in fact correct. But there is something going on in cplex which avoids it to be valid for all the cases.

If CPLEX is terminating with incorrect solutions, obviously that is cause for significant concern. I'd still be inclined to suspect a bug in my own code first and a bug in CPLEX second. Unfortunately, I'm too busy now to look at anything, but perhaps toward the end of the year I could look at it if you are still experiencing the symptoms.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Paul, thanks for comment.
>>Is this a minimization problem, and is CPLEX producing an "optimal" solution that is to low (meaning the contribution of the linking variable is too negative)?

yes, true.

>>Assuming minimization, the bound will of course be lower than the true optimum until CPLEX completes. Are you saying that CPLEX actually terminates with an artificially low objective value, or just that the bound appears to be converging to something too low? To me, that latter is not a sign of a problem -- in all sorts of problems, not just Benders, I see lower bounds that I know are much lower than the true optimum and either look like they're converging to something to low or simply stall out (and look as if they've already converged).

This was quite complicated but a short answer is that: yes, terminates with an artificially low objective value. Let say the true objective is -100 but cplex terminates to optimality by -1000. I always thought that if the objective function is too low then bounds have converged to a something too low.

>>I'd still be inclined to suspect a bug in my own code first and a bug in CPLEX second.
Yeah but there are ways to ensure that the code is correct especially after cleaning re-writing it for 5 times.
I am not blaming cplex for something, what I am saying is that when I do benders for positive objective value minimization problems, I have to turn of the PreDual and PreInd otherwise it might happen that the LP node was already integer and we dont get to an incumbent. There might be some other options for the case I mentioned that must also be turned off. That is what I searched for.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Shahin,

> Shahin G wrote:
> Paul, thanks for comment.

Interesing discussion, as always.

> This was quite complicated but a short answer is that: yes, terminates with an artificially low objective value. Let say the true objective is -100 but cplex terminates to optimality by -1000. I always thought that if the objective function is too low then bounds have converged to a something too low.

No, the problem would not be bound convergence; the problem would be CPLEX finding an "incumbent" with (alleged) objective value -1000 which somehow was not rejected. CPLEX stops either because the tree is exhausted (which has nothing to do with bounds) or because the MIP gap is small enough. If you're getting termination before exhaustion with a lower bound of -1000, then it must be one of the gap criteria, which implies an incumbent with objective value near -1000.
>
> >>I'd still be inclined to suspect a bug in my own code first and a bug in CPLEX second.
> Yeah but there are ways to ensure that the code is correct especially after cleaning re-writing it for 5 times.

Your experience is different than mine. If I rewrite my code five times, it just means that I've gone through five generations of bugs (and usually the bugs are developing survival skills due to selective breeding). :-)

> I am not blaming cplex for something, what I am saying is that when I do benders for positive objective value minimization problems, I have to turn of the PreDual and PreInd otherwise it might happen that the LP node was already integer and we dont get to an incumbent. There might be some other options for the case I mentioned that must also be turned off. That is what I searched for.

The existence of a cut callback should automatically turn off certain dual reductions; I'd have to rummage through notes to figure out which (it's one of those things I should know but keep forgetting). I don't routinely turn off PreDual and PreInd explicitly. In fact, I just checked some library code I wrote for solving certain types of combinatorial Benders problems, and the only thing I explicitly turn off is symmetry reduction -- and that is supposed to be unnecessary as of CPLEX 10.2 or so. (I ran into a bug -- might have been 10.1 -- where CPLEX failed to automatically turn off symmetry reduction in the presence of a cut callback, and I ended up getting incorrect results because symmetry reduction on an early version of the master problem cut off the optimal branch of the tree.)

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I want to say up front that I didn't read all the code you posted -- I stopped as soon as I saw something fishy. If what follows below is not the problem, perhaps you could repost the code using code markup tags (see markup help to right of screen -- code tags are at the bottom). One or two glitches (probably inconsequential, but you never know) occurred in your code due to the forum software mistaking part of it for markup.

> razorgator wrote:

>                IncCallBack(IloNumVar[] z, IloNumVar[][] delta, IloNumVar thetaCur) { Z_sp=z; delta_sp=delta; theta = thetaCur; }
> 
>            public void main() throws IloException {
>       
> 
>            //Solve subproblem
>            
>            double subObj_callback = mySP2.get_subObj(); //objective of subproblem
>            double thetaVal_callback = getValue(theta);                     
>            double UB_callback = getObjValue(); //this represents the objective of the incumbent solution being considered
>            double LB_current_callback = UB_callback - thetaVal_callback + subObj_callback; //lower bound
> 
>                    
>            if((UB_callback-LB_callback)>.0001)//(the solution from the Master has an 'incorrect' objective, so add cut/reject incumbent)
>            {

First issue: You declare LB_current_callback but use LB_callback in the comparison part of the if statement. I don't see a definition of 'LB_callback'.

Second issue: If you meant it to be 'LB_current_callback' in the if statement, then by including UB_callback in the definition of LB_current_callback and then subtracting LB_current_callback from UB_callback in the comparison, you've canceled out UB_callback. In other words, the comparison is not looking at the incumbent objective value.

/Paul
Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: razorgator

Paul,

Thanks for pointing the LB_current_callback issue to correct. I fixed that mistake. My comparison (between UB_callback and LB_current_callbackn is looking at the the difference between the theta value (from the MP) and the subproblem objective. That doesn't seem to be causing a problem (perhaps I'm misunderstanding your comment), since after I fixed a separate issue in the subproblem code, the implementation appears to be working (knocking on wood). Let's put it this way, it works on the set of instances that it didn't work on previously :).

The issue you raise below about the incumbent callback being called multiple times is definitely something I need to address (even though it hasn't bitten me in the runs I've looked at thus far, it is sure to do so).

Thanks again for everyone's assistance on this.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> razorgator wrote:
> Paul,
>
> Thanks for pointing the LB_current_callback issue to correct. I fixed that mistake. My comparison (between UB_callback and LB_current_callbackn is looking at the the difference between the theta value (from the MP) and the subproblem objective. That doesn't seem to be causing a problem (perhaps I'm misunderstanding your comment), since after I fixed a separate issue in the subproblem code, the implementation appears to be working (knocking on wood). Let's put it this way, it works on the set of instances that it didn't work on previously :).\

Well, if it ain't broke, don't fix it. :-)
>
> The issue you raise below about the incumbent callback being called multiple times is definitely something I need to address (even though it hasn't bitten me in the runs I've looked at thus far, it is sure to do so).

It's actually simple enough to fix:

• In the incumbent callback (or wherever it is you generate the cuts), you just generate a single cut and add it to the end of the queue.

• In the cut callback, loop through the queue, calling add() on each queued cut. Then clear the queue. The cut callback allows you to call add() more than once.

• In contrast, the branch callback only lets you call makeBranch() a maximum of twice (once per child), and in this case you only want one child. The good news is that it lets you specify a range argument. So convert your queue to an IloRange] array (or just implement it as an IloRange[ array in the first place), and pass it as the first argument to a single call to makeBranch().

Glad to hear you've got it working now.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: razorgator

Thanks again, Paul.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: napoleao

Hi Paul,

I am using this basic framework IncumbentCallback paired with a BranchCallback, and a LazyConstraintCallback, and I am facing a problem...
in a certain point of the execution, the current node presents the optimal solution. So CPLEX finds this optimal solution (which is optimal feasible but has a misstated objective value in the master because Z = 0). So the framework generates the benders optimality cut and reject the incumbent. But instead of calling the BranchCallback (that will certainly provide the optimal solution and Z values), the framework calls once again the IncumbentCallback (CPLEX finds another incumbent solution in the same node, but this time suboptimal, before branching). In this case, since we have rejected the optimal incumbent without branching on it, the framework ends with a suboptimal solution. Do you have any idea how I could fix it?

Best regards,

Napo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Napo,

When the incumbent callback sees the optimal solution (with the wrong value of z), does it queue a bound tightenting cut? Here is what I think should happen:

1. Incumbent callback detects overly optimistic value of z, queues a bound tightening cut and rejects the incumbent.

2. Either

2a. The lazy constraint callback is called immediately (I think this will happen if the first incumbent was the solution to the LP relaxation at the node), adds the cut and deletes it from the queue. In this case the new LP solution should be the same but with tighter z.

or

2b. The lazy constraint callback is not immediately called because a heuristic found the rejected incumbent. In this case, the same heuristic or a different one might turn up a different "incumbent", which might or might not be acceptable to your incumbent callback. In this situation, I believe that the branch callback has to be called. It should see the queued cut and use it to a create a single new child in which the true optimal solution should "live".

Now in case 2b, there is no guarantee that the single child created is the next node processed. There is also no guarantee that, when the child is processed, the optimum will be found immediately (ie., with no further branching). If the optimum was initially detected by a heuristic, we cannot be sure that the heuristic will find it again here. We can be sure, though, that if the algorithm runs to completion (not stopped by a time or node limit), the optimum will be found in some node descended from the child.

Are you saying that the branch incumbent is never called at the node in question? Or that it is called but the subtree under the child node fails to disgorge the true optimum?

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: napoleao

Hi Paul,

I have just debugged the execution...

IncumbentCallback called
Master objValue: 40 Master bestObjValue: 40 Z value: 0 Subprob: 70
Cut queued / Incumbent rejected
IncumbentCallback called
Master objValue: 50 Master bestObjValue: 50 Z value: 0 Subprob: 70
Cut queued / Incumbent rejected
BranchCallback called
...

Optimal solution: 40 + 70
Deemed solution: 50 + 70

You are right (1) and (2b) are happening, and the BranchCallback is being called and adding the cuts while generating the single child. The problem is that unluckily CPLEX has updated the master's bestObjValue with the solution of the second incumbent and, therefore, the child does not contain the optimal solution anymore. So I don't see how to fix this.
By the way, more philosophically, what is the advantage to use this framework instead of doing all the job using only a LazyConstraintCallback?
Thanks a lot for your attention.

Best regards,

Napo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: napoleao

Sorry, the bound shouldn't discard the optimal solution. So I don't know why the subtree under the child node fails to find the optimum.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: napoleao

Here it is my implementation. The problem occurs when I use the "local" option. If you have any clue, please tell me.

public class BendersIncumbentCallback extends IloCplex.IncumbentCallback {
 
                private Subproblem subproblem;
 
                BendersIncumbentCallback() throws IloException {
                        subproblem = new Subproblem(data);
                        optimalityCuts = new Vector<IloRange>();
                }
                
                private double[] getContractValues() throws IloException {
                        double[] solution = new double[data.nContracts];
                        for (int j = 0; j < data.nContracts; j++) {                                
                                solution[j] = getValue(contracts[j]);
                        }
                        return solution;
                }
 
                public void main() throws IloException {
                        System.out.println("Node " + getNnodes() + ": IncumbentCallback called");
                        double[] contractValues = getContractValues();
                        int status = subproblem.solveModel(contractValues);
                        if (status == 1) {
                                // subproblem is optimal
                                System.out.println("MasterObj:" + String.format("%15.6f", getObjValue()) +
                                                String.format("%15s", "MasterLB:") + String.format("%15.6f", getBestObjValue()) +
                                                String.format("%15s", "Z:") + String.format("%15.6f", getValue(Z)) +
                                                String.format("%15s", "Subp:") + String.format("%15.6f", subproblem.cplex.getObjValue()));
                                if (subproblem.cplex.getObjValue() - getValue(Z) > 0.001) {
                                        // generate Benders' optimality cut to master problem
                                        System.out.println("Cut generated / Incumbent rejected");
                                        optimalityCuts.add(bendersCut(subproblem));
                                        reject(); //reject incumbent
                                }
                        } else if (status == 0){
                                // subproblem is unbounded
                                System.out.println("unexpected status 0");
                        } else {
                                //unexpected subproblem status
                                System.out.println("unexpected status -1");
                        }
                }
        }
        
        class BendersLazyConstraintCallback extends IloCplex.LazyConstraintCallback {
 
                BendersLazyConstraintCallback() {}
 
                public void main() throws IloException {
                        System.out.println("Node " + getNnodes() + ": LazyConstraintCallback called");
                        while ( ! optimalityCuts.isEmpty() ) {
                                System.out.println("Cut added");
                                System.out.println("Cut removed from list");
                                IloRange bendersCut = optimalityCuts.remove(0);
                                add(bendersCut);
                        }
                }
        }
 
        class BendersBranchCallback extends IloCplex.BranchCallback{
                
                private boolean local;
 
                public BendersBranchCallback(boolean local) {
                        this.local = local;
                }
 
                public void main() throws IloException {
                        System.out.println("Node " + getNnodes() + ": BranchCallback called");
                        if (! optimalityCuts.isEmpty()) {
                                IloRange[] cuts = new IloRange[optimalityCuts.size()];
                                for (int i = 0; i < optimalityCuts.size(); i++) {
                                        System.out.println("Cut added");
                                        cuts[i] = optimalityCuts.elementAt(i);
                                }
                                System.out.println("Child node with cuts");
                                makeBranch(cuts, getBestObjValue()); //create single branch with cuts
                                if (local) {
                                        System.out.println("Cut list cleared");
                                        optimalityCuts.clear();
                                }
                        }
                }
 
        }

Cuts added locally

IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ".
Warning: Control callbacks may disable some MIP features.
Node 0: IncumbentCallback called
MasterObj: 0,000000 MasterLB: 0,000000 Z: 0,000000 Subp: 404,399503
Cut generated / Incumbent rejected
Node 0: IncumbentCallback called
MasterObj: 0,000000 MasterLB: 0,000000 Z: 0,000000 Subp: 404,399503
Cut generated / Incumbent rejected
Node 0: IncumbentCallback called
MasterObj: 0,000000 MasterLB: 0,000000 Z: 0,000000 Subp: 404,399503
Cut generated / Incumbent rejected
Node 0: BranchCallback called
Cut added
404.39950289066843 <= 1.0*Z + 1091.5047619047618*CONTRACT_j1 + 1973.1047619047617*CONTRACT_j2 + 1511.3142857142857*CONTRACT_j3 + 1511.3142857142857*CONTRACT_j4 <= infinity
Cut added
404.39950289066843 <= 1.0*Z + 1091.5047619047618*CONTRACT_j1 + 1973.1047619047617*CONTRACT_j2 + 1511.3142857142857*CONTRACT_j3 + 1511.3142857142857*CONTRACT_j4 <= infinity
Cut added
404.39950289066843 <= 1.0*Z + 1091.5047619047618*CONTRACT_j1 + 1973.1047619047617*CONTRACT_j2 + 1511.3142857142857*CONTRACT_j3 + 1511.3142857142857*CONTRACT_j4 <= infinity
Child node with cuts
Cut list cleared
Node 1: BranchCallback called
Node 2: BranchCallback called
Node 3: BranchCallback called
Node 4: BranchCallback called
Node 5: IncumbentCallback called
MasterObj: 55,000000 MasterLB: 40,000000 Z: 0,000000 Subp: 70,000000
Cut generated / Incumbent rejected
Node 5: BranchCallback called
Cut added
70.0 <= 1.0*Z + 0.0*CONTRACT_j1 + 0.0*CONTRACT_j2 + 0.0*CONTRACT_j3 + 0.0*CONTRACT_j4 <= infinity]
Child node with cuts
Cut list cleared
Node 6: IncumbentCallback called
MasterObj: 125,000000 MasterLB: 40,000000 Z: 70,000000 Subp: 70,000000
Node 6: BranchCallback called
Node 7: IncumbentCallback called
MasterObj: 40,000000 MasterLB: 40,000000 Z: 0,000000 Subp: 70,000000
Cut generated / Incumbent rejected
Node 8: IncumbentCallback called
MasterObj: 50,000000 MasterLB: 50,000000 Z: 0,000000 Subp: 70,000000
Cut generated / Incumbent rejected
Node 8: BranchCallback called
Cut added
70.0 <= 1.0*Z + 0.0*CONTRACT_j1 + 0.0*CONTRACT_j2 + 0.0*CONTRACT_j3 + 0.0*CONTRACT_j4 <= infinity
Cut added
70.0 <= 1.0*Z + 0.0*CONTRACT_j1 + 0.0*CONTRACT_j2 + 0.0*CONTRACT_j3 + 0.0*CONTRACT_j4 <= infinity
Child node with cuts
Cut list cleared
Node 9: IncumbentCallback called
MasterObj: 120,000000 MasterLB: 50,000000 Z: 70,000000 Subp: 70,000000
Node 9: BranchCallback called
Node 10: IncumbentCallback called
MasterObj: 60,000000 MasterLB: 60,000000 Z: 0,000000 Subp: 70,000000
Cut generated / Incumbent rejected
Node 10: BranchCallback called
Cut added
70.0 <= 1.0*Z + 0.0*CONTRACT_j1 + 0.0*CONTRACT_j2 + 0.0*CONTRACT_j3 + 0.0*CONTRACT_j4 <= infinity
Child node with cuts
Cut list cleared
Default row names c1, c2 ... being created.

Objetive: 120,00
Status: Optimal
Contract1: 0,00
Contract2: 0,00
Contract3: 0,00
Contract4: 1,00

Contracts: 50,00

Cuts added globally

IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ".
Warning: Control callbacks may disable some MIP features.
Node 0: LazyConstraintCallback called
Node 0: IncumbentCallback called
MasterObj: 0,000000 MasterLB: 0,000000 Z: 0,000000 Subp: 404,399503
Cut generated / Incumbent rejected
Node 0: LazyConstraintCallback called
Cut added
404.39950289066843 <= 1.0*Z + 1091.5047619047618*CONTRACT_j1 + 1973.1047619047617*CONTRACT_j2 + 1511.3142857142857*CONTRACT_j3 + 1511.3142857142857*CONTRACT_j4 <= infinity
Cut removed from list
Node 0: BranchCallback called
Node 1: BranchCallback called
Node 2: BranchCallback called
Node 3: BranchCallback called
Node 4: LazyConstraintCallback called
Node 4: IncumbentCallback called
MasterObj: 55,000000 MasterLB: 40,000000 Z: 0,000000 Subp: 70,000000
Cut generated / Incumbent rejected
Node 4: BranchCallback called
Cut added
70.0 <= 1.0*Z + 0.0*CONTRACT_j1 + 0.0*CONTRACT_j2 + 0.0*CONTRACT_j3 + 0.0*CONTRACT_j4 <= infinity
Child node with cuts
Node 5: LazyConstraintCallback called
Cut added
70.0 <= 1.0*Z + 0.0*CONTRACT_j1 + 0.0*CONTRACT_j2 + 0.0*CONTRACT_j3 + 0.0*CONTRACT_j4 <= infinity
Cut removed from list
Node 5: LazyConstraintCallback called
Node 5: IncumbentCallback called
MasterObj: 125,000000 MasterLB: 40,000000 Z: 70,000000 Subp: 70,000000
Node 5: BranchCallback called
Node 6: LazyConstraintCallback called
Node 6: IncumbentCallback called
MasterObj: 110,000000 MasterLB: 40,000000 Z: 70,000000 Subp: 70,000000
Node 6: BranchCallback called
Default row names c1, c2 ... being created.

Objetive: 110,00
Status: Optimal
Contract1: 1,00
Contract2: 0,00
Contract3: 0,00
Contract4: 0,00

Contracts: 40,00
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

First, I see no virtue in clearing the cut queue in the incumbent callback, unless you are generating a cut that is not globally valid. Optimality cuts, at least in my experience, typically are globally valid. That said, clearing the queue should not result in a suboptimal final solution; it should just cause you to rediscover the same cut later on, in a different branch of the tree.

It's hard to diagnose the problem without knowing which nodes are children of which other nodes. In particular, I would like to know the lower bound of the node created by the branch callback at node 7 of the "local" run (which appears to be where the true optimum is discovered). It should be 110.

Paul
Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: napoleao

Hi Dr. Paul,
thanks a lot for your attention. I still haven't found the problem. Actually, I experience the same misbehavior even when I am using the "global" approach with heuristics option enabled. Then, when I set

cplex.setParam(IloCplex.IntParam.HeurFreq, -1);

, CPLEX can finally find the true optimal. I don't want you to lose much time on this, but if you have any clue please let me know. I am enclosing the log files for the global approach with/without heuristics.

p.s.: My implementation using only a LazyConstraintCallback, as in the BendersATSP.java example released with version 12.3, is working fine. But, as discussed here, this solution is not really safe since ...

"CPLEX calls the cut callback early in the processing of a node, after it has solved the node LP. After it is done with the node LP (and any iterations of the cut callback), it may invoke various heuristics that may result in an "incumbent" being found. If that incumbent is actually infeasible in the original problem, you won't have a chance to generate the corresponding Bender's cut, because the cut callback will not be called again at that node."
Kind regards,

Napo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I need to think more about this, but as a quick experiment, does the error still happen if you leave heuristics turned on but replace getBestObjValue() with a constant 0 in the call to makeBranch?

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: napoleao

Yes, the error persists. The execution is the very same.

Best regards,

Napo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: napoleao

Hi Paul,

By analyzing the log file, I finally found out the "error". When the branch-and-bound process arrives in Node4 (which contains the optimal solution), all the binary decision variables are already fixed (CONTRACT_j1 = 1, CONTRACT_j2 = 0, CONTRACT_j3 = 0, CONTRACT_j4 = 0). Since we reject this incumbent because the continuous Z variable presents a "wrong" value and since we cannot branch Node4 anymore, we miss the optimal solution. Would you have any idea how to prevent the framework from this misbehavior?

Best regards,

Napo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: napoleao

Dr. Paul,

I have performed some tests just using a LazyConstraintCallback which generates the Benders' optimality cuts, and it seems that whenever a possible incumbent is found (by means of heuristics or not, possibly many times in a given node) the LazyConstraintCallback is promptly called. The feasibility of the incumbent with respect to the lazy constraints is checked in the end of the LazyConstraintCallback. So, if it is really true, I don't see any reason to continue using IncumbentCallback + BranchCallback + LazyConstraintCallback to implement Benders'decomposition. Could anyone confirm this?

Best regards,

Napo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I can confirm that the lazy constraint callback is called whenever an incumbent is found. The only reason I can see to keep the incumbent callback and the associated baggage, meaning the branch callback, is that the lazy constraint callback is called at every node. If you only want to generate cuts when an integer-feasible solution is found (this is what I do in my code), then you have to test integer feasibility in the lazy constraint callback each time it is called. There is nothing wrong with doing that (and others do it); it just might slow your code down a bit.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: napoleao

You are totally right.
Thanks a lot for your attention.

Best,

Napo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: napoleao

Hi Paul,
maybe things are much easier now:

http://publib.boulder.ibm.com/infocenter/cosinfoc/v12r3/index.jsp?topic=%2Filog.odms.cplex.help%2Fhtml%2Frefcallablelibrary%2Fhtml%2Ffunctions%2FCPXsetlazyconstraintcallbackfunc.html

To confirm, I used the following implementation:

public class BendersIncumbentCallback extends IloCplex.IncumbentCallback {
                public void main() throws IloException {
                        System.out.println("Node " + getNnodes() + ": IncumbentCallback called");
                }
        }
        
        class BendersBranchCallback extends IloCplex.BranchCallback{
                public void main() throws IloException {
                        System.out.println("Node " + getNnodes() + ": BranchCallback called");
                }
        }     
 
        class BendersLazyConstraintCallback extends IloCplex.LazyConstraintCallback {
 
                boolean local;
                private Subproblem subproblem;
 
                BendersLazyConstraintCallback(boolean local) throws IloException {
                        this.local = local;
                        subproblem = new Subproblem(data);
                }
 
                private double[] getContractValues() throws IloException {
                        double[] solution = new double[data.nContracts];
                        for (int j = 0; j < data.nContracts; j++) {                               
                                solution[j] = getValue(contracts[j]);
                        }
                        return solution;
                }
 
                public void main() throws IloException {
                        System.out.println("Node " + getNnodes() + ": LazyConstraintCallback called");
                        double[] contractValues = getContractValues();
                        int status = subproblem.solveModel(contractValues);
                        if (status == 1) {
                                // subproblem is optimal
                                if (subproblem.cplex.getObjValue() - getValue(Z) > 0.001) {
                                        // generate Benders' optimality cut to master problem
                                        System.out.println("Node " + getNnodes() + ": Infeasible incumbent");
                                        if (local) {
                                                addLocal(bendersCut(subproblem));
                                        } else {
                                                add(bendersCut(subproblem));
                                        }
                                        //exportModel(getNnodes());
                                }
                        } else if (status == 0){
                                // subproblem is unbounded
                                System.out.println("unexpected status 0");
                        } else {
                                //unexpected subproblem status
                                System.out.println("unexpected status -1");
                        }
                }
        }

And the LazyConstraintCallback has just been called for Nodes that present integer feasible solutions.

Node 0: LazyConstraintCallback called
Node 0: Infeasible incumbent
Node 0: LazyConstraintCallback called
Node 0: IncumbentCallback called
Node 0: BranchCallback called
Node 1: BranchCallback called
Node 2: LazyConstraintCallback called
Node 2: Infeasible incumbent
Node 2: BranchCallback called
Node 3: BranchCallback called
Node 4: BranchCallback called
Node 5: BranchCallback called
Node 6: BranchCallback called
Node 7: BranchCallback called
Node 8: BranchCallback called
Node 9: BranchCallback called
Node 10: LazyConstraintCallback called
Node 10: Infeasible incumbent
Node 10: LazyConstraintCallback called
Node 10: Infeasible incumbent
Node 10: LazyConstraintCallback called
Node 10: IncumbentCallback called
Node 10: BranchCallback called
Node 12: BranchCallback called
Node 13: BranchCallback called
Node 14: BranchCallback called
Node 15: BranchCallback called
Node 16: BranchCallback called
Node 17: BranchCallback called
Node 18: LazyConstraintCallback called
Node 18: Infeasible incumbent
Node 18: LazyConstraintCallback called
Node 18: IncumbentCallback called
Node 18: BranchCallback called
Node 19: LazyConstraintCallback called
Node 19: Infeasible incumbent
Node 19: LazyConstraintCallback called
Node 19: IncumbentCallback called
Node 19: BranchCallback called
Node 20: LazyConstraintCallback called
Node 20: Infeasible incumbent
Node 20: LazyConstraintCallback called
Node 20: IncumbentCallback called
Node 20: BranchCallback called
Node 22: LazyConstraintCallback called
Node 22: Infeasible incumbent
Node 22: BranchCallback called
Node 23: LazyConstraintCallback called
Node 23: IncumbentCallback called
Node 23: BranchCallback called
Node 24: BranchCallback called
Node 25: BranchCallback called
Node 26: BranchCallback called
Node 27: BranchCallback called
Node 28: BranchCallback called
Node 29: BranchCallback called
Node 30: LazyConstraintCallback called
Node 30: IncumbentCallback called
Node 30: BranchCallback called
Node 34: BranchCallback called
Node 35: BranchCallback called
Node 36: BranchCallback called
Node 37: BranchCallback called
Node 38: BranchCallback called
Node 39: BranchCallback called
Node 40: BranchCallback called
Node 41: LazyConstraintCallback called
Node 41: Infeasible incumbent
Node 42: LazyConstraintCallback called
Node 42: Infeasible incumbent
Node 42: LazyConstraintCallback called
Node 42: IncumbentCallback called
Node 42: BranchCallback called
Node 43: BranchCallback called
Node 44: BranchCallback called
Node 45: LazyConstraintCallback called
Node 45: Infeasible incumbent
Node 45: LazyConstraintCallback called
Node 45: IncumbentCallback called
Node 45: BranchCallback called
Node 46: LazyConstraintCallback called
Node 46: Infeasible incumbent
Node 46: BranchCallback called
Node 47: BranchCallback called
Node 48: BranchCallback called
Node 49: BranchCallback called
Node 50: BranchCallback called
Node 51: LazyConstraintCallback called
Node 51: IncumbentCallback called
Node 51: BranchCallback called
Node 55: BranchCallback called
Node 56: BranchCallback called
Node 57: BranchCallback called
Node 58: BranchCallback called
Node 59: BranchCallback called
Node 60: BranchCallback called
Node 61: BranchCallback called
Node 62: BranchCallback called
Node 65: BranchCallback called
Node 66: BranchCallback called
Node 67: BranchCallback called
Node 68: BranchCallback called
Node 69: BranchCallback called
Node 70: BranchCallback called
Node 75: BranchCallback called
Node 76: BranchCallback called
Node 77: BranchCallback called
Node 78: BranchCallback called
Node 79: BranchCallback called
Node 80: BranchCallback called
Node 81: BranchCallback called
Node 82: BranchCallback called
Node 83: BranchCallback called
Node 84: BranchCallback called
Node 85: BranchCallback called
Node 86: BranchCallback called
Node 87: BranchCallback called
Node 88: BranchCallback called
Node 89: BranchCallback called
Node 90: BranchCallback called
Node 91: BranchCallback called
Node 92: BranchCallback called
Node 93: BranchCallback called
Node 94: BranchCallback called
Finally, from the documentation, it seems that only non-redundant cuts are now added to the pool.
Best,

Napo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, I would say things are easier now. As long as the only time you would reject an incumbent is when you were adding a cut, you should be able to dispense with both the incumbent and branch callbacks and just use the lazy constraint callback. (There are situations, such as attempts to enumerate all optimal solutions, where someone might reject an incumbent without adding a cut. In those cases, a branch callback may be needed to prevent CPLEX from either pruning a node with an integer-feasible LP solution or branching randomly on it.)

Thanks for the link.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: KTAT_Leonardo_Lamorgese

Hi to all,

just to make sure I'm sure I understand what is being said here:

in the 12.3 cplex version to dynamically add lazy constraints it is possible to simply implement a user written LazyConstraintCallback extension without the aid of the IncumbentCallback and BranchCallback.
However, it is more efficient (in terms of elapsed time) to implement an IncumbentCallback to test integer feasibility, so as to avoid calling the Lazy constraint callback in every node.

Is this correct?

Since I am working with a realtime problem any improvement that makes the code faster is very welcome.

Thank you very much for your help
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: napoleao

You can simply implement a user-written LazyConstraintCallback. Moreover, this callback is not called in every node...

"the user-written callback is called by CPLEX in these situations:

• when CPLEX compares an integer-feasible solution (including an integer-feasible solution provided by a MIP start before any nodes exist) to lazy constraints;
• when the LP at a node is unbounded, and a lazy constraint might cut off the primal ray."

CPLEX 12.3 documentation: http://publib.boulder.ibm.com/infocenter/cosinfoc/v12r3/index.jsp?topic=%2Filog.odms.cplex.help%2Fhtml%2Frefcallablelibrary%2Fhtml%2Ffunctions%2FCPXsetlazyconstraintcallbackfunc.html
Best,

Napo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: KTAT_Leonardo_Lamorgese

thank you napo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: KTAT_Leonardo_Lamorgese

Hi to all,

I have implemented the Lazy Constraint Callback as suggested, but there is still something that is not working.

With the instance I'm working on, Cplex calls the Callback correctly in integer nodes. It effectively adds a set of lazy constraints in node 0, then apparently adds another set in node 30 and then finds the optimal solution.

When I perform a check on this solution I find that infact it is not feasible and it violates the cuts that should have been added in node 30 (plus other cuts).
I have these cuts printed in node 30 just before calling add(IloRange[]..) in the callback and they are formed correctly, so I don't understand why CPLEX does not consider them.

I am sure that the first set of lazy constraints is effective because the corresponding values of the integer variable are coherent.

So, I'd like to ask:

1- Is there any way to have CPLEX print the lazy constraint pool to find out whats going on in there?(I am using Concert)

2- Does anyone know a case in which CPLEX considers only some lazy constraint and not others?

3- If the separator finds a violated cut but this cut is not added to the model, at the following integer node shouldn't it find the same violated cut? How can the solution then be optimal?

Once again, thank you very much for your precious help

Leo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: KTAT_Leonardo_Lamorgese

Thanks to my debugging efforts I think I am starting to understand what's going on.

In a certain not-integer node CPLEX enters the LazyCallback but does not call the separator since the solution is not integer(I have set the separator to be called only if Feasibility Status is != Infeasible), so no new lazy constraints are added.

What then happens is, due to some heuristics, CPLEX finds an Integer solution, accepts and updates the current incumbent to this value, but does NOT call the LazyCallback again, basically treating the current solution as feasible (even though it isn't).

CPLEX then carries on branching, adds a few more cuts and then quits, returning the previous NON-feasible solution as the Optimal one.

I have tried to turn off heuristics (setting param HeurFreq to -1), and this avoids CPLEX quitting immediately, but it later on finds a different solution which is "almost" Integer (all 0's and 1's and one or two components extremely close to 1) that it recognizes as unfeasible so no new cuts are generated, but is then rounded up and again turned into the incumbent(without checking feasibility).
Is there a way to force CPLEX to check these heuristic solutions (basically to call the lazycallback again)?

If not, how can I turn off this kind of rounding up in the second case?

Thank you for your help
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

My understanding is that, at least as of version 12.3, the LazyConstraintCallback should be called only when a new incumbent is found, which means COLES should consider the solution integer feasible. Perhaps you should try commenting out the feasibility check in the callback, and added some debug prints to see if the callback is really being called with unfeasible solutions.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: KTAT_Leonardo_Lamorgese

Thank you for answering Paul,
indeed I have tried commenting the feasibility check.

First of all CPLEX calls the LazyConstraintCallback almost at every node (I'm not sure yet what this subset is but it is certainly greater than only (quote) "the user-written callback is called by CPLEX in these situations:

when CPLEX compares an integer-feasible solution (including an integer-feasible solution provided by a MIP start before any nodes exist) to lazy constraints;

when the LP at a node is unbounded, and a lazy constraint might cut off the primal ray.").

Since I only need the separator to be called in integer nodes, precisely to check if the current integer solution is feasible or not (if not I separate the violated constraints), I perform this check myself by voiding what is considered unfeasible.

Unfortunately it seems that what is considered unfeasible in the callback (so no need call the separator), by the means of heuristics or round up, may then be turned into a feasible solution (hence new incumbent) without the feasibility check being performed again(the callback would have to be called again basically), returning an integer but infeasible incumbent.

Do you think that following the approach you suggested for versions prior to 12.3 (3 callbacks) this problem could be eliminated?

Thank you for your help!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Keep in mind that COLES is testing integrality using values from the presolved model, while you are testing integrality using values from the original model. If your model surfers from numerical stability issues, that could explain COLES accepting solutions you would reject.

Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: KTAT_Leonardo_Lamorgese

> Paul Rubin wrote:
> Keep in mind that COLES is testing integrality using values from the presolved model
>
> Paul

I'm sorry Paul I'm not familiar with this aspect, could you explain this to me, or link me to where I could find out more about this?

Thank you,

Leo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Sorry for the typo in the previous message; I'm using a tablet on the road, and it sometimes auto-corrects things that don't needed correcting.

I don't have a reference to presolving handy, but I imagine the user manual discusses it. Numerical instability typically involves basis matrices that are ill-conditioned (flirt with singularity). If you look in the parameter manual, you will find a parameter that will let you track kappa values (condition numbers for the basis matrices). There is also some documentation of what CPLEX considers to be suspiciously high kappa values. It is worth checking whether your kappa values look problematic.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Hello everyone,

I have implemented Benders by a branch and cut algorithm.

Surprisingly, other than my own generated cuts (user cuts), CPLEX does not generate any internal cut (like MIR cut, Gomory cut...)!

Is there anybody which have observed the same issue?

Thanks,
Amin
#CPLEXOptimizers
#DecisionOptimization