Originally posted by: vishalovercome

Hello,
I am completely new to CPLEX and am having difficulty figuring out what function calls to make to do my assignment. Specifically, I would like to add user cuts to my integer program. However, I would like to these to be local cuts. What's more, the equation of the cutting plane is not known beforehand. Once, I obtain a solution, I would like to test whether the solution is cut off by one of the cutting planes, whose equation depends not only the variables picked, but also on the variables yet to be picked. If the current solution satisfies one of the several planes(where do implement this code?), then I would like to add this to my list of cuts. I have read the manual and it says that I have to use the CPXusercutcallback along with a couple of other functions. I have also gone through the codes that come along with CPLEX, but am still clueless. Can you let me know how to go about it? If you do, then can you present your solution as an algorithm rather than a description(which I can get from the manual anyway!), since more than the functions, I am confused about what aspect should be implemented in which user defined function.

Thanks,
Vishal
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I am quite experienced with CPLEX and I have a similar problem. I can attempt an answer to the above:

usercut(..., int useraction_p)
{
x = malloc(...)
CPXgetcallbacknodex(..., x, ...)
you now have the primal variable values x_i in the node solution
for (C is a lazy constraint you want to check, expressed as a <= constraint)
{
if sum C_i x_i > C_rhs
{
CPXcutcallbackadd(C)
}
}
free(x)
useraction_p = CPX_SET; / or CPX_DEFAULT, it doesn't matter */
}

however, this appears to have a problem if several rounds of cuts need to be added. Since the user's manual states that this method can be used for adding lazy constraints (i.e. those which can't be derived from existing constraints) I would expect that CPLEX would re-call the solve routine (or solve callback) and then re-call the cuts routine as above until no further cuts are added. However, it doesn't, so any cuts not discovered in the first round don't have a chance to be added. Do I have to resort to advanced trickery with installing an incumbent callback and branching from inside it to force further rounds of user cuts? I noticed there are flowcharts available that explain what CPLEX does, but they aren't available to the public, could they be released?

cheers, Nick
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The following general approach works for me:

1. Use an incumbent callback to test proposed incumbents. If the incumbent callback doesn't like them, it generates some additional cuts (that lop off that solution), queues them, and rejects the incumbent. (The cut queue is maintained in my code.)

2. Use a cut callback to add the cuts. The cut callback flushes the queue after adding the cuts. Note that the cut callback will be called repeatedly at the same node until it no longer has a cut to add. Cuts can be added globally (apply to the entire tree) or locally (apply only to descendants of the current node).

3. Use a branch callback. The branch callback looks at the cut queue and, if the cut queue is empty, tells CPLEX to branch however it wants to. If the cut queue is not empty, however, the branch callback creates a single child node by applying all the cuts in the queue and does NOT flush the queue (so the cut callback will apply those cuts the next time it is called). The branch callback is necessary because the incumbent could have been found at various stages of node processing (by heuristics, as an integer feasible solution to the node LP, ...). If we want to apply cuts after heuristics find an incumbent (which I believe may occur after the node LP has been solved), it's too late to use the cut callback to modify the current node; so we create a single child that adds the cuts.

/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

OK. Can I suggest that the branch-callback, if there are no cuts queued, should also check and queue some if possible? And only allow CPLEX to proceed with the branching if the solution is linear feasible with regard to all user constraints? This should allow cuts to be generated before diving, I believe it would be quite inefficient to generate the cuts at the bottom of the dive. I guess we also need the incumbent callback in case the solution (without user constraints) just happens to be integer feasible, as CPLEX wouldn't then attempt any branching.

I will give this a try. Many thanks. It would be good to have your thoughts on the idea though. Also: I think it would be good in a future release of CPLEX if the cut-callback could return a value such as CPX_CALLBACK_RETRY which means to solve and then re-call the cut callback. This would avoid all this messing around and would be more efficient as CPLEX's branching strategy and/or integer feasibility checking could be deferred until all use cuts had been added. With the workaround outlined here, these checks are made on each node but the result is usually not used.

cheers, Nick
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I will try to shed some light on this issue...

Let's talk about sequential and opportunistic parallel mode first.
In this case, the cut callback is called at every node with fractional LP solution. If the cut callback adds cuts, the LP is re-solved, and the cut callback is called again until no more cuts are found.
If the LP solution is integral, then CPLEX scans the user cuts and lazy constraints tables and adds violated inequalities. Additionally, the cut callback is called. Again, if at least one constraint has been added, the LP is re-solved and the process is iterated until the LP solution is fractional or no additional cuts have been found.
So, I think that all what you need is indeed already there.

Deterministic parallel mode is a bit more complicated.
The cut callback is again called at every node, but if it finds cuts we cannot immediately add them to the LP because this is incompatible with how we manage the data structures during deterministic parallel MIP solving. Instead, the cuts are only moved into some internal pool and then added to the LP at the next synchronization point. As a consequence, the LP at the current node is not resolved (because no cuts have been added immediately) and no second round of cuts is generated.
In the case of integral LP solutions, however, we are basically doing the same as in the opportunistic and sequential cases by using some trick. The user cuts and lazy constraint tables are scanned for violated inequalities and the cut callback is called. If at least one cut has been found, the cuts are directly added to the LP, the LP is solved and the process is iterated, just like in the opportunistic case. If no more cuts have been found, we force a synchronization such that we can keep the cuts in the LP even in deterministic parallel mode. Note that this forcing of a synchronization can be pretty time consuming, which is why we do not use the same trick for the regular cuts. But in the case of integer feasible LP solutions, we need to continue searching for cuts until the LP solution is fractional or no cuts are found, which means the solution is a new incumbent. Thus, there is no other way than doing this trick with forcing synchronization.
Hope this helps. The suggestion of Paul to queue cuts found in the incumbent callback makes some sense but is actually not necessary. It should suffice to just reject infeasible solutions in the incumbent callback without generating a cut. The incumbent callback is mainly used for solutions that have been generated by primal heuristics. Therefore, a cut that cuts off such a solution may not be very useful for the search tree since the heuristic solution may be very far away from any LP solution that is encountered during the search. Since the cut callback is called for every integral LP solution, it suffices to separate cuts in the cut callback.

I don't understand the reason why you would even need a branch callback. This sounds very strange...
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> Tobias Achterberg wrote:
> I don't understand the reason why you would even need a branch callback. This sounds very strange...

My understanding of the plumbing (which may be wrong, and in any case predates parallelism) is that if the LP relaxation yields an integer-feasible solution, CPLEX calls the incumbent callback but does not call the cut callback again at the current node. Perhaps this has changed recently, but I'm pretty sure this was the case back around version 9. So consider a node which contains two integer-feasible solutions A and B to the current node LP, with A optimal in the LP but not feasible in the real problem and B optimal in the real problem (but perhaps not in the node LP). Solving the node LP yields A, which is fed to the incumbent callback, which rejects it and generates one or more new cuts (which B would satisfy). If I'm right that the cut callback is not called again at the current node, CPLEX will move on either to the node heuristics or to the branching step (I think the latter but I'm not positive). Since the node LP generated an integer-feasible solution, CPLEX has no criteria for branching, so either you provide a branch callback to tell it what to do or it prunes the current node (and optimal solution B is cast to the winds).

If this has in fact changed, it would be good to know, since it makes a lot of my existing code obsolete.

Cheers,
Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Paul,

I understand the issue that you are describing, but looking at the history of our code basically says that it has been like how I described it forever. At least I found a commit from Mary dated September 2001 (that added the option to add local cuts in the cut callback) that clearly shows that the cut callback is called when CPLEX found an integer-feasible LP solution.
So, the only way in which the cut callback is not called before a new incumbent is installed is when the solution was found by a heuristic. But in this case, you also do not need the cut callback, as adding cuts usually does not make much sense to cut off such a solution.

If the code misbehaves in the presence of a cut callback, then this is clearly a bug. So it would be nice if you could remove the branch callback trick from your codes and check if you get again wrong answers. If so, please send a bug report.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Tobias,

> Tobias Achterberg wrote:
>
> I understand the issue that you are describing, but looking at the history of our code basically says that it has been like how I described it forever. At least I found a commit from Mary dated September 2001 (that added the option to add local cuts in the cut callback) that clearly shows that the cut callback is called when CPLEX found an integer-feasible LP solution.

You may be right about this; certainly you have better access to inside information than I do. I have a flow chart that I got from Ed Klotz a couple of years ago, showing the order of processing at a node. He was trying to keep it simple, though, so I'm pretty sure there are one or two missing paths in the chart.

> So, the only way in which the cut callback is not called before a new incumbent is installed

Did you mean "after" here? That's the issue.

> is when the solution was found by a heuristic. But in this case, you also do not need the cut callback, as adding cuts usually does not make much sense to cut off such a solution.

I think it does (or at least can) in Benders decomposition, since the cuts are global.
>
> If the code misbehaves in the presence of a cut callback, then this is clearly a bug. So it would be nice if you could remove the branch callback trick from your codes and check if you get again wrong answers. If so, please send a bug report.

I'll try to remember to test this if I get the chance, but it will be in the indefinite future -- I'm immersed right now in a project that does not involve Benders. I vaguely recall that an early version of the code did screw up without the branch callbacks, but whether that was a consequence of heuristically found solutions or integer-feasible LP solutions I don't recall clearly. (I think it was the latter, but this occurred years ago and my memory is fuzzy.)

/Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> Paul Rubin wrote:
> > So, the only way in which the cut callback is not called before a new incumbent is installed
>
> Did you mean "after" here? That's the issue.

I mean "before" in the sense "before the incumbent is actually accepted and stored in CPLEX data structures" and "after" in your sense "after a candidate to be the new incumbent has been found".
> > is when the solution was found by a heuristic. But in this case, you also do not need the cut callback, as adding cuts usually does not make much sense to cut off such a solution.
>
> I think it does (or at least can) in Benders decomposition, since the cuts are global.

Certainly the cut can be globally valid. My point is that if it only cuts off a solution vector that was generated by a heuristic, then chances are high that it will never cut off any LP solution in the whole search tree and is therefore just increasing the size of the LP. If it is expensive to generate those cuts, then it is certainly a good idea to store it somewhere, but I recommend to store it in your internal pool and only add it to CPLEX in the cut callback if it is violated by an LP solution.
Cheers,

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> Tobias Achterberg wrote:

> My point is that if it only cuts off a solution vector that was generated by a heuristic, then chances are high that it will never cut off any LP solution in the whole search tree

Really? I'll grant you it's not necessarily cutting off the current LP solution, but the cut is chopping off a portion of the LP hull (since the proposed incumbent is probably interior to the LP hull). Whether the portion it's cutting off would be visited otherwise is not obvious (to me, at least).

> and is therefore just increasing the size of the LP. If it is expensive to generate those cuts, then it is certainly a good idea to store it somewhere, but I recommend to store it in your internal pool and only add it to CPLEX in the cut callback if it is violated by an LP solution.

I see what you are saying, but that means that I have to go to the expense of generating the cut, and then also go to the expense of checking violations at every node in my code. My impression is that CPLEX is pretty good about managing cuts, almost surely better than my code (written in Java by a highly non-professional programmer, to wit me) would be.and we're comparing highly optimized (I'm told) C code to my thoroughly unoptimized Java code.

There's also one other impediment I can see to your suggestion: as far as I can tell, there's no way to know in an incumbent callback what produced the incumbent, other than by querying the LP solution and comparing it to the incumbent. Granted that's not too costly since incumbents are generated rather infrequently, but if I'm right about CPLEX's ability to manage cuts for me, I'm inclined to take the lazy programming approach.

If I ever find the time, I'll try coding a parallel version of one of my programs that does what you suggest, and see if performance improves.

Cheers,
Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> nick_d wrote:
> OK. Can I suggest that the branch-callback, if there are no cuts queued, should also check and queue some if possible? And only allow CPLEX to proceed with the branching if the solution is linear feasible with regard to all user constraints? This should allow cuts to be generated before diving, I believe it would be quite inefficient to generate the cuts at the bottom of the dive. I guess we also need the incumbent callback in case the solution (without user constraints) just happens to be integer feasible, as CPLEX wouldn't then attempt any branching.

Perhaps I mistook your original post: I thought you were generating new cuts from integer-feasible solutions (new incumbents) only. If you have a way to generate new cuts from the solution to the node LP (including solutions that are not integer-feasible), then you can use the cut callback to query the LP solution and determine new cuts as needed. Otherwise, you only need the incumbent callback to check for new cuts. Offhand, I don't see any scenario under which you would need to look for new cuts in the branch callback.
>
> I will give this a try. Many thanks. It would be good to have your thoughts on the idea though. Also: I think it would be good in a future release of CPLEX if the cut-callback could return a value such as CPX_CALLBACK_RETRY which means to solve and then re-call the cut callback. This would avoid all this messing around and would be more efficient as CPLEX's branching strategy and/or integer feasibility checking could be deferred until all use cuts had been added. With the workaround outlined here, these checks are made on each node but the result is usually not used.

I think you have a misconception here. After solving the node LP, and assuming the solution is not integer-feasible, CPLEX calls the cut callback (if one exists). If the cut callback adds a cut, CPLEX updates the node LP and calls the cut callback again. It keeps calling the cut callback until the cut callback stops feeding it cuts at that node (or, if I understand it correctly, if those cuts lead to an integer-feasible solution, in which case it calls the incumbent callback). So your retry flag would just be confirming the existing behavior if true; if false, it would just save the last call to the cut callback (which returns no new cuts). Keeping in mind that in many cases the cut callback has to see the new LP solution (the result of the most recently added cuts) before deciding that no further cuts are warranted, I doubt the flag would accomplish much.

/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