Originally posted by: anahana

Hello,

I am working on a new branching strategy that requires a lot of control over how a B&B tree is traversed in MIP. Here's how it starts:

1. Solve node 0 and obtain the set of non-integer variables. Call this the baseSet.

2. Branch on the first variable in the baseSet and obtain two new nodes (i and j).

3. Backtrack to node 0 and branch on the second variable in the baseSet and obtain two new nodes.

4. Continue until all you branched on all variables in the baseSet.

To implement this strategy, I need to be able to:

A. Instruct CPLEX to back track to node 0 (or any node for that matter) whenever I want. How can I do that? The backtrack tolerance parameter defines a strategy on how often backtracking occurs, it does not give you control over which node to go back to.

B. Maintain nodes i and j information so that they can be reused if I decided to visit those nodes again. I assume this is not a problem if there is a way to backtrack to any node I want as long as I don't "terminate" the current search tree.

I'm using concert technology with c++ under MS visual studio. 

Regards, 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: anahana

So far I did this, which gives me the baseSet, but how can I proceed in instructing CPLEX which branching variables to use and how to back track? 

#CPLEXOptimizers
#DecisionOptimization

You cannot explicitly backtrack to a node. You can use the NodeCallback to instruct CPLEX which node to process next.

The last thing CPLEX does for a node is to invoke the branch callback. After the branch callback is complete the node is deleted, hence you cannot go back to an old node. Moreover, you can create at most two children from a single node. So to implement your strategy with CPLEX you will have to do work around these limitations. One way to do that is as follows:

Assume R is node 0. Instead of

2. Branch on the first variable in the baseSet and obtain two new nodes (i and j).
3. Backtrack to node 0 and branch on the second variable in the baseSet and obtain two new nodes.

do this:

2. Create two nodes N1 and N2 that are the same R (create branches that don't add constraints).
3. Process N1 next and create the two new nodes i and j
4. Instead of back-tracking to R process N2 as next node (this is a copy of R)

Repeating this for each variable in your baseSet you can implement your strategy. To see how to use the branch callback look at example iloadmipex1.cpp example.

You may want pass some information from R to N1 and N2 (for example the baseSet). This can be done using the callback's setNodeData() and getNodeData() functions along with the BranchCallbackI::makeBranch() functions that install node data into newly created nodes.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: anahana

 

Thanks for the idea Daniel. To make sure I understood you correctly, I need to create |baseSet| copies of node R to begin with. Each copy branches on a single variable, creates two child nodes i and j, and then I choose the next node to process to be another copy of R.

A few points though:

Will this work even though I set the node limit parameter to 1? I expect CPLEX to terminate after processing the first copy. If that is the case, should I remove the node limit parameter or set it to 2*|baseSet|?

Suppose I end up with 10 nodes after branching on all the baseSet variables, can I make copies of any node and repeat? Doing this requires calling some branching macro that I write multiple times. Is this possible? As far as I know, the macro is called through cplex.solve() and I don't have much control over it.

Copying the root node R is done through the makeBranch() function I assume and it can be called a maximum of 2 times, correct? On this issue, there is the function IloCplex::Callback copyNodes(env, branchVar), is it related? I can't find a documentation on it.

Why do I need to pass on information from R to N1 and/or N2 through getNodeData() and setNodeData()? Won't makeBranch() create an identical duplicate? And how is getNodeData() helpful when it's all zeros? This is what I get for node R.

Regards,

#CPLEXOptimizers
#DecisionOptimization

Thanks for the idea Daniel. To make sure I understood you correctly, I need to create |baseSet| copies of node R to begin with. Each copy branches on a single variable, creates two child nodes i and j, and then I choose the next node to process to be another copy of R.

Yes, that is the idea. However, since CPLEX does not allow you to explicitly copy a node you have to do some trickery with the branch-callback. And since CPLEX does not allow you to create more than two children at a node you will have to do even more trickery.

Will this work even though I set the node limit parameter to 1? I expect CPLEX to terminate after processing the first copy. If that is the case, should I remove the node limit parameter or set it to 2*|baseSet|?

Of course the node limit will not work since you are creating a lot of "fake" nodes here. You can stop the search from a callback by invoking the callback's abort() function. May that is easier to do in your case.

Suppose I end up with 10 nodes after branching on all the baseSet variables, can I make copies of any node and repeat? Doing this requires calling some branching macro that I write multiple times. Is this possible? As far as I know, the macro is called through cplex.solve() and I don't have much control over it.

The strategy I described will work recursively. So you can indeed apply the same strategy to other nodes.

Copying the root node R is done through the makeBranch() function I assume and it can be called a maximum of 2 times, correct? On this issue, there is the function IloCplex::Callback copyNodes(env, branchVar), is it related? I can't find a documentation on it.

Where did you find this function? Anyway, if it is not documented then you should not use it.

Why do I need to pass on information from R to N1 and/or N2 through getNodeData() and setNodeData()? Won't makeBranch() create an identical duplicate? And how is getNodeData() helpful when it's all zeros? This is what I get for node R.

CPLEX will only copy the data it knows about. It will for example not copy your baseSet. getNodeData() will return nil unless you set it to a non-nil value.

Maybe it helps to write up some (untested pseudo) code:

// Next node to process. If selectNextNodeId is false then let CPLEX decide,
// otherwise select the node identified by nextNodeId;
NodeId nextNodeId;
bool selectNextNodeId = false;

struct NodeCallback : public IloCplex::NodeCallbackI {
   ...
   void main() {
      if ( selectNextNodeId ) {
         selectNode(nextNodeId);
         selectNextNodeId = false;
      }
   }
};

// NodeData to pass information between nodes
struct NodeData : public IloCplex::MIPCallbackI::NodeData {
   BASESETTYPE *baseSet; // For fake nodes, points to baseSet, for other nodes is NULL
   int nextBaseSetElem; // Next element to handle in baseSet
   IloNumVar branchVar; // The variable to branch on for non-fake nodes.
};

struct BranchCallback : public IloCplex::BranchCallbackI {
   ...
   void main() {
      BASESETTYPE *baseSet = 0;
      NodeData *data = (NodeData)getNodeData();
      int nextBaseSetElem;
      if ( !data ) {
         // No node data. This is the root node (or recursive invocation on a child node)
         // Create the baseSet for this node
         baseSet = ...;
         nextBaseSetElem = 0;
      }
      else if ( !data->baseSet ) {
         // If data->baseSet == 0 we want to branch on data->branchVar
         makeBranch(..., data->branchVar, ...); // up branch
         makeBranch(..., data->branchVar, ...); // down branch
         delete data;
      }
      else {
         // We need to create more fake nodes to handle further
         // elements in the base set.
         baseSet = data->baseSet;
         nextBaseSetElem = data->nextBaseSetElem;
         delete data;
      }
      // Create a node that will branch on the nextBaseElem'th variable in *baseSet
      NodeData *data1 = new NodeData();
      data1->baseSet = 0;
      data1->nextBaseSetElem = -1;
      data1->branchVar = (*baseSet)[nextBaseSetElem];
      makeBranch(..., data1);
      // Create a node that handles further elements in baseSet
      ++nextBaseSetElem;
      if ( nextBaseSetElem < baseSet->size() ) {
         NodeData *data2 = new NodeData();
         data2->baseSet = baseSet;
         data2->nextBaseSetElem = nextBaseSetElem;
         nextNodeId = makeBranch(..., data2);
         selectNextNodeId = true; // This node should be the next one to process
      }
      else {
         // All elements in *baseSet were handled, should be safe to delete now
         delete baseSet;
      }
   }
};

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: anahana

Thanks for the detailed reply. I found the copyNodes function in the ILONODECALLBACK and ILOBRANCHCALLBACK macros. It's not a function in my code that I wrote. I have no idea what it does or where it came from. 

I implemented something similar to your suggestion actually, but got stuck on the following issue:

I call a ILONODECALLBACK macro from within a ILOBRANCHCALLBACK to select the next node for processing. See code segment:

 

nodeSelect(getEnv(), downNode, upBranchImp, downBranchImp);

Once the nextNode is selected, I want to solve it and return the solution (or at least the solution quality) to ILOBRANCHCALLBACK1 so I can store it somewhere and process the next node. Is this possible from ILONODECALLBACK3? If not, and I leave the code as is, I suspect cplex.solve() take control again, call  ILOBRANCHCALLBACK1 and ILONODECALLBACK3 again at whatever node, and... I don't even imagine what will happen next. 

If my implementation is totally wrong, please let me know.

Regards, 

#CPLEXOptimizers
#DecisionOptimization

I think you are misunderstanding how callbacks work. Once a callback's main function returns control is back to CPLEX and CPLEX will invoke the next callback at the appropriate time. You cannot invoke one callback from another callback (callbacks cannot be nested).

In order to pass information between callbacks you need to use node data or global variables.

Why do you actually want to pass information from the child nodes back to the parent nodes? If you want to store information for the child node then you should do that from a callback that is invoked when processing the child node.

#CPLEXOptimizers
#DecisionOptimization