Originally posted by: AlbertoSantini

I am a user of the C++ interface. I add cuts to my problem via a class inheriting from UserCutCallbackI.

I'd like, however, to separate and add these cuts every - say - 100 nodes begin explored by CPLEX. So, my main() method would look like the following:

if(solution_is_integer || current_node_number % 100 == 0) { // Execute expensive separation algorithm }

(The first part is required to check that I don't "accept" an incumbent if it violates some cut not yet added to the problem.)

However, I can't find a way to obtain the current node number from the IloEnv object I pass to UserCutCallbackI. Should I pass in something else? Should I use a different approach? If so, which one?

Thanks.

Originally posted by: EhsanN

Since you want to add cuts to integer incumbents, you should use a lazy constraint callback because the user cut callback is not called when an integer incumbent is found.

Regarding the node number, you could do as follows:

// Define a structure to store node data
struct DummyNodeData : public IloCplex::MIPCallbackI::NodeData {};

// Within the lazy constraint callback
ILOLAZYCONSTRAINTCALLBACK0(YourCallbackName){

    IloCplex::MIPCallbackI::NodeData *const data = getNodeData();

    if ( !data ) { // We are at this node for the first time.
        setNodeData(new DummyNodeData());
        nodeCounter++;
    }
    else {
        // We are not at this node for the first time.
    }
    
    if (nodeCounter % 100 == 0){
        // Separate and add the necessary cuts
        nodeCounter = 0;
    }
}

Originally posted by: AlbertoSantini

Since you want to add cuts to integer incumbents, you should use a lazy constraint callback because the user cut callback is not called when an integer incumbent is found.

You are right. Unfortunately lazy constraints are not really suitable for my purpose. The manual says that:

Lazy constraints are constraints that the user knows are unlikely to be violated, and in consequence, the user wants them applied lazily, that is, only as necessary or not before needed.

Which is not true in my case, as the cuts are subtour elimination cuts for a Travelling Salesman Problem. The way I thought to solve this issue is by checking that the integer solution is valid in 2 places:

1) in the cuts callback (in case the integer solution is found as the solution of the relaxation of the problem);

2) in an incumbent callback, by calling the reject() method of IloCplex::IncumbentCallbackI in case the solution is not feasible.

Right now I'm trying to do just this, but I'm wondering if my approach would also require me to instruct CPLEX on how to branch after an incumbent has been refused.

In short, having such a huge number of potential cuts makes the approach of adding all of them as lazy constraints infeasible, in my opinion. Again, I'm open to suggestions on how to implement this.

Going back to the solution you kindly proposed, I came up with somehting similar too, but it has the disadvantage that it relies on a global variable counting the current node number. I would like to avoid using such an approach, as global variables tend to lead to unpredicatable errors, as their value can be set anywhere in the programme. I thought it was impossible that the node number is not available to IloCplex::UserCutCallbackI but maybe I should review my expectation?

Thanks,

AS

Originally posted by: AlbertoSantini

I'd like to add that the solution I found simply increments a counter every time the main() method of the callback class is called, without effectively checking if we are in the same or in another node. Regarding the setNodeData() method, I can't find it in any class of the inheritance hierarchy of neither UserCutCallbckI nor LazyConstraintCallbackI and the manual says that node data can only be set via the makeBranch() method of BranchCallbackI. Maybe you weren't referring to the C++ API in your answer?

Thanks,

AS

Originally posted by: EhsanN

The method is fully available for implementation in C++ (my code is C++, too). SetNodeData() is available in the lazy constraint callback through inherited methods from control callback.

The only drawback of this approach is that it cannot differentiate incumbents found via CPLEX heuristics (right now, CPLEX won't tell you whether the current solution is found by a node or a heuristic while being in the lazy constraint callback). So if it is important for you to count everything, you would have to disable heuristics. 

Originally posted by: AnirudhSubramanyam

As pointed out above, it seems like the lazy cut callback is exactly suited for your needs. If, by your solution being integer, you mean that there are possible subtours in the problem which cplex will accept as a valid incumbent, then this integer solution with subtours will first be passed to the lazy constraint callback and then the incumbent callback (assuming both are enabled). The integral solution will not be passed through the cut callback. So as pointed out above, you need a lazy constraint callback. This lazy constraint callback of yours should have the functionality to detect subtours and if found, must also return valid cutting planes which must be added to the constraint matrix.

"In short, having such a huge number of potential cuts makes the approach of adding all of them as lazy constraints infeasible, in my opinion. Again, I'm open to suggestions on how to implement this."

If you incorporate a separation algorithm into the cut callback to detect fractional subtours, then I don't anticipate the number of cuts to become unmanageably large. Having just a lazy constraint callback should also do the job for small instances.

As for getting the node number, the C API function is CPXXgetcallbacknodeinfo() with whichinfo = CPX_CALLBACK_INFO_NODE_SEQNUM I'm not sure if there's a C++ concert equivalent.

Originally posted by: AlbertoSantini

Yes, now I think I see more clearly how a lazy constraint callback could be used with profit. However, the manual says that:

IloCplex calls the user-written callback when either a candidate feasible solution is found and it needs to be tested whether it violates any lazy constraints; or the LP relaxation is found to be unbounded and a lazy constraint may cut off the unbounded direction.

I would still need to add a third option, namely "or the LP relaxation is bounded but the current node's number is a multiple of 100 and therefore the user decided that he wants to add cuts". So, not only I should find a way to check the current node's number, but I should also convince CPLEX to call the lazy constraint callback more often than it would like. Am I missing something else?

Thanks,

AS

Originally posted by: AnirudhSubramanyam

You cannot make CPLEX call the lazy constraint callback function whenever you want. That function is called only at integral nodes, whose node numbers may or may not be a multiple of 100. If you do have a separation routine which is designed for fractional solutions and not just integral solutions, then you may call the routine at nodes, whose node numbers are a multiple of 100 (which also, may not happen as nodes with node numbers 100 may be infeasible/cutoff).

I'm not sure I completely follow you when you say you want to call your separation routine inside the lazy callback at nodes 100,200 etc. If this routine is essential to rejecting solutions you don't want, you have to call it no matter what. If they are "optional", you may keep a global counter which triggers the expensive routine when you enter the lazy callback for the 100th time.

You need both a lazy constraint callback and a user cut callback (which can call the same method to generate the cuts). You need the user cut callback if you want to add cuts every n nodes, even when the n-th node does not yield an integer feasible solution. You need the lazy constraint callback both for the reason articulated above (it is the only way to be sure that you intercept a proposed incumbent before CPLEX accepts that incumbent) and also because CPLEX expects cuts from a user cut callback not to cut off feasible solutions. Were you to use just the user cut callback, CPLEX might make dual-based reductions that would be incorrect for your model (meaning you could get incorrect answers).

Have the lazy constraint callback present tells CPLEX not to do whatever things it would otherwise do that are unsafe when the feasible region will be modified on the fly by cuts. It's fine to add cuts in the user cut callback that would cut off feasible solutions as long as the lazy constraint callback is present.

As for knowing when n nodes have gone by, you can call getNnodes() in both callbacks to get the cumulative number of nodes processed, then mod that by n to see if you want to generate cuts.

Paul

Originally posted by: AlbertoSantini

I think this is the correct and most complete answer. To summarize:

1. Lazy constraints are needed to remove potentially infeasible integral solutions as soon as they appear (i.e. when they are generated by CPLEX heuristics or found solving the relaxed problem). Adding a lazy constraint rather than simply rejecting the solution might also help in keeping other infeasible integral solution in a "neighbourhood" of the chosen one away, since the same cut could apply to them as well.
2. User cuts are needed if one wants to add cuts only at a subset of nodes (the optimal "density" of this subset will be experimentally determined - once every 100, 200, 500, whatever nodes).
3. No user cut should cut off a previously feasible integral solution, so if I want to add an inequality that cuts away a part of the feasible region containing an integer point I must make sure that said point wasn't chosen as an incumbent. The lazy constraint part in point 1 takes care of this.
4. All callbacks inherit at some point from IloCplex, which is where getNnodes() is defined and therefore all callback classes should be able to access said method.

I will proceed with implementation according to this understanding and, if everything works out as planned, I'll mark the question as answered - for the benefit (?) of posterity.

Thanks EhsanN, anirudhsubramanyan and Paul Rubin for your kind help.

The gist of this is correct, but I have two corrections.

In item 3, it is not important whether or not the the point was chosen as an incumbent. If every infeasible integer solution were cut away by a user cut before it had a chance to become an incumbent, you would still need the lazy constraint callback, or else you would need to make the same changes to CPLEX's behavior (in particular, turning off certain presolve reductions) manually. If you have unstated constraints (that will be applied in callbacks) and you don't have a lazy constraint callback (or make the manual changes), CPLEX may produce an incorrect root problem by doing things in the presolve stage that it shouldn't. At least that's my understanding.

In item 4, getNnodes() is defined in MIPInfoCallback, not from IloCplex.

Originally posted by: AlbertoSantini

Thanks for your corrections, Paul. I implemented the suggestions you made and everything is working perfectly. I hope this thread can be of help for someone else who stumbles upon the same issue.