Originally posted by: srvh

I run a code in CPLEX and I switched off all cuts and heuristics. I set up best bound for node selection.

According to NodeID and Parent in CPLEX log, I drew tree search algorithm in Python Graphviz. But when I see the graph, something is wrong. I set up best bound but it's really not best bound. The value of NodeID is not in order. For example, after root node, node 3 and 4 are in level one then node 2 and 1 are in level 2. According CPLEX log  I can't understand the order of node selection.

How can I find the order of node selection? Because of my research, the order of node selection is very important for me.

Thank you in advance.

I am not sure what the problem is. The order of nodes selected should be clearly visible in the node log. Consider this log:

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap         Variable B NodeID Parent  Depth

*     0+    0                         5975.0000      458.0000            92.33%
Found incumbent of value 5975.000000 after 0.02 sec. (10.34 ticks)
      0     0      983.1674    24     5975.0000      983.1674      108   83.55%
*     0+    0                         2173.0000      983.1674            54.76%
Found incumbent of value 2173.000000 after 0.03 sec. (18.06 ticks)
*     0+    0                         1502.0000      983.1674            34.54%
Found incumbent of value 1502.000000 after 0.04 sec. (27.91 ticks)
*     0+    0                         1426.0000      983.1674            31.05%
Found incumbent of value 1426.000000 after 0.05 sec. (32.98 ticks)
*     0+    0                         1389.0000      983.1674            29.22%
Found incumbent of value 1389.000000 after 0.05 sec. (36.93 ticks)
      0     2      983.1674    24     1389.0000      983.1674      108   29.22%                        0             0
Elapsed time = 0.06 sec. (39.84 ticks, tree = 0.02 MB, solutions = 5)
      1     3      994.5026    24     1389.0000      994.8397      134   28.38%             x11 U      8      0      1
      2     4     1005.5125    22     1389.0000     1005.8540      148   27.58%            x317 D     16      8      2
      3     5     1006.1583    23     1389.0000     1006.6740      150   27.53%            x397 D     24     16      3
      4     6     1009.5292    23     1389.0000     1006.9448      155   27.51%            x411 D     32     24      4
      5     7     1012.3328    21     1389.0000     1006.9448      167   27.51%             x13 D     40     32      5
      6     8     1014.5176    22     1389.0000     1006.9448      176   27.51%            x195 D     48     40      6
      7     9     1016.5134    21     1389.0000     1006.9448      191   27.51%              x6 D     56     48      7

In column NodeID you have the ids of the nodes in exactly the order in which they were processed. Remember that the node id is just some (random) unique number and you should not attach any additional meaning to it. The node with id 2 is not necessarily the second node.

What makes you thing CPLEX is not doing best bound search as requested? Can you please elaborate on that?

You may also want to disable multi-threading if you not already did that. If nodes are processed in parallel then of course the log will interleave output from different threads and that may be a little hard to read, especially if you have many threads.

Originally posted by: srvh

Thank you so much dear Daniel.

As I wrote, the order of node selection is important for me. At each iteration, i want to know which node is selected for branching.For best bound i sorted by Objective and added new column for numbering then drew the tree  with new column as a label for nodes but I don't know what do I do for depth first search to draw the tree.

My other question is, at some nodes why is branching done for one direction? For example at the picture on NodeID 2, there is one branching on variable x74. I checked up and down direction of this node it isn't infeasible.

My other question is about the values of Objective column. There are  numbers, Integer, Infeasible and Cutoff. When is Cutoff used?

My last question is:

In my problem optimal solution is 333 but the branch continued to 326 at the other route. For example at NodeID 46 best solution is 337.76 after branch on NodeID 46 best solution is 328.45 and now the number of node is 47. CPLEX continues branching on node 47. Why does it continue? The optimal solution is 333 and it must stop on node 46 with 328.45.

For your first question it seems you are confusing two things: a node is not selected for branching. What is selected for branching is a variable. Nodes are only selected for processing. This are two very different things, controlled by two different CPLEX parameters.

For the second question I don't understand what the problem is, sorry. You have NodeId 2. The two children of a node are not processed simultaneously. It could well be that one child is evaluated immediately while the other child is deferred. It may even be not evaluated at all because it is cut off eventually. What is displayed in the node log is not the branching decision taken at each node. What is displayed is the node that is being processed and the branching decisions that led to this node. In the example you attached you can see that the node with id 3 was created from its parent by branchin up on x(9)(5) while the node with id 4 was created from its parent by branching down on that variable. These are the two branches created at the root and CPLEX branched up and down on x(9)(5).

Next question: cut off is displayed if the objective function of the node's relaxation is worse then the best feasible solution available. If that happens the node can be cut off, hence "cutoff" is displayed. Note that in this case CPLEX did not necessarily solve the relaxation to optimality. It will stop as soon as it can prove that the optimal solution would be worse than the best feasible. That is why no objective value and just "cutoff" is displayed.

Last question: I am not sure how to answer this because your node log does not include the respective nodes. In any case, did you switch CPLEX to single-threaded? If not then this may be a thread synchronization issue and may well be expected.

Originally posted by: srvh

Thank you dear Daniel.

No,  I am not confusing. It was typing mistake.

I set up "Global default thread count" to 1 and set up node selection to "depth first". According to this setting, the value of NodeID is in the order of processing. But when I set up "Global default thread count" to 0 and node selection is "best bound" , the value of NodeID is not in the order of processing. What do I do to get the value of NodeID in the order of processing in best bound strategy? because the order of processing is important for me and i have to get the log information according to order of processing. 

You have the order of processing in the log. In the NodeID column you can see the ids of the nodes in the order in which they are processed (remember that NodeIDs are random numbers and their actual value does not matter, so the numbers in this column are not necessarily increasing).

If you use more than one thread (thread count set to anything other than 1) then there just is no defined order of node ids: Threads run in parallel, so nodes are solved simultaneously. If you want a definite order of nodes then you have to restrict yourself to a single thread.

Originally posted by: srvh

Thank you.I wish it was in order with multithread.

Dear Daniel, you said you answered the question about how to use callback to retrieve the variable that was branch at each node. But I couldn't find it. As well you said I must use BranchCallback to get that information. I found this callback "NodeCallback/getBranchVar". Can I use this callback to get those variables at each nodes?

I wrote this macro code but it has error. Sorry I'm beginner in using callbacks.

ILONODECALLBACK1(MYNODE, IloInt, nodeid) {
        for (int i = 0; i< nodeid.getNnodes() ,i++) {
                cout << "BranchVariable" << getBranchVar(nodeid(i)) << endl;

        }
}

I wish it was in order with multithread.

Then you must define an order on things that happen simultaneously.

I did not try but I think your callback should look something like this:

ILONODECALLBACK0(MYNODE) {
  IloInt64 n = getNnodes64();
  for (IloInt64 i = 0; i < n; ++i) {
    cout << "BranchVariable " << getBranchVar(i) << endl;
  }
}

Note that the node callback is invoked whenever the next node is selected. So going through all nodes every time a new node must be selected will incurr a huge performance overhead. That is why I said it is better to use a branch callback (and there is a lot of example code for this on this forum). That allows you to trace the branching decisions when they are made instead of having to recover them from a node callback.

Originally posted by: srvh

I appreciate for your help dear Daniel.

Originally posted by: 894294736@qq.com

How to write benders program framework of calling CPLEX in MATLAB?