Hi,
In the branch and bound tree, at each node, is it possible to know which variables have been valued so far and what are their values (for that specific branch) and also which variables are to branch at the current node.
Could some one please tell me what to do? (in C++ concert tech.)
Cheers,
Topic

Re: Branch and bound tree
20121001T21:48:01ZThis is the accepted answer. This is the accepted answer.I think you can tell which variables are fixed, either explicitly or implicitly, by grabbing the upper and lower bounds of the integer variables (in a callback) and checking which ones have lower bound equal to upper bound.
In a branch callback, you can ask CPLEX how it is planning to branch (and then you can let it have its way by doing no branching yourself in the 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) 
Re: Branch and bound tree
20121002T09:31:49ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20121001T21:48:01Z
I think you can tell which variables are fixed, either explicitly or implicitly, by grabbing the upper and lower bounds of the integer variables (in a callback) and checking which ones have lower bound equal to upper bound.
In a branch callback, you can ask CPLEX how it is planning to branch (and then you can let it have its way by doing no branching yourself in the 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)
Cheers. 
Re: Branch and bound tree
20121002T13:52:50ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20121002T09:31:49Z
Thanks Paul. I think I get it. Very naive question from me. I think I always can use getValue to see if a variable is set to 0 or 1!
Cheers.
Note that there are several threads in this Forum that show how to use a BranchCallback to keep track of the branching decisions that CPLEX made. You may find them helpful. 
Re: Branch and bound tree
20121002T16:54:36ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20121002T13:52:50Z
Yes, getValue() will give you the value of that variable in the current solution at the current node.
Note that there are several threads in this Forum that show how to use a BranchCallback to keep track of the branching decisions that CPLEX made. You may find them helpful.
I looked for my original problem (mentioned below) in the forum but I could not find any relevant solution.
My question: I want to add another criterion to pruning roles (in addition the lower bound).
Meaning that if by the lower bound it is OK to carry on a branch but by my new criterion it is not OK, I want to prune that node.
How can I do it? 
Re: Branch and bound tree
20121002T17:06:57ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20121002T16:54:36Z
Thanks.
I looked for my original problem (mentioned below) in the forum but I could not find any relevant solution.
My question: I want to add another criterion to pruning roles (in addition the lower bound).
Meaning that if by the lower bound it is OK to carry on a branch but by my new criterion it is not OK, I want to prune that node.
How can I do it?
You can refer to some of those papers.
Thanks
Sunil 
Re: Branch and bound tree
20121003T08:04:20ZThis is the accepted answer. This is the accepted answer. chintasunny
 20121002T17:06:57Z
Apart from lower bounds, you can think of coming up with dominance rules to prune nodes. Depending upon your problem structure, there will be some way to come up with such rules. Dominance rules were widely employed in B&B methods for Machine scheduling, Vehicle routing, etc
You can refer to some of those papers.
Thanks
Sunil
Also, in terms of implementation in CPLEX (C++), how can I introduce new criterion (in addition to the lower bound) that can be performed as I described in my previous question? (if by the lower bound it is OK to carry on a branch but by my new criterion it is not OK, I want to prune that node.)
Cheers, 
Re: Branch and bound tree
20121003T23:39:16ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20121002T16:54:36Z
Thanks.
I looked for my original problem (mentioned below) in the forum but I could not find any relevant solution.
My question: I want to add another criterion to pruning roles (in addition the lower bound).
Meaning that if by the lower bound it is OK to carry on a branch but by my new criterion it is not OK, I want to prune that node.
How can I do it?
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) 
Re: Branch and bound tree
20121004T11:07:37ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20121003T08:04:20Z
Thanks Sunil for your. I was wondering if you could introduce me some papers on the dominance rules.
Also, in terms of implementation in CPLEX (C++), how can I introduce new criterion (in addition to the lower bound) that can be performed as I described in my previous question? (if by the lower bound it is OK to carry on a branch but by my new criterion it is not OK, I want to prune that node.)
Cheers,
You may be employing CPLEX to solve the problem. But depending on problem structure and the way you are employing cplex to solve your problem, there may or may not be a possibility of employing dominance rules
By the way, what is the problem that you are attempting to solve and how you are employing CPLEX?
Thanks
Sunil 
Re: Branch and bound tree
20121005T17:30:12ZThis is the accepted answer. This is the accepted answer. chintasunny
 20121004T11:07:37Z
You can start looking at the paper "A BranchandBound Procedure to Minimize Total Tardiness on One Machine with Arbitrary Release Dates" by Philippe Baptiste, et al. It also talks about several other papers that employed dominance rules. All these papers talk about dominance rules in customized branch & bound methods (i.e. these branch & bound methods do not employ Math. formulations or CPLEX to solve the problem in hand).
You may be employing CPLEX to solve the problem. But depending on problem structure and the way you are employing cplex to solve your problem, there may or may not be a possibility of employing dominance rules
By the way, what is the problem that you are attempting to solve and how you are employing CPLEX?
Thanks
Sunil
It is a general IP problem I am working on.
Let assume that we have a simple problem Max{x_1+3x_2: 2x_1+x_2<=2 and x_1+2x_2<=1 and x_1,x_2\in {0,1}}
If in BranchCallback, we just write "prune();". it means that it prunes every branch. So it terms of IP solutions, should it give a infeasible message?
I tried it. Cplex solves it as if I have not invoked prune() to its IP solution. An I right?
My question is what I should do to prune a node completely. 
Re: Branch and bound tree
20121005T17:31:28ZThis is the accepted answer. This is the accepted answer. chintasunny
 20121004T11:07:37Z
You can start looking at the paper "A BranchandBound Procedure to Minimize Total Tardiness on One Machine with Arbitrary Release Dates" by Philippe Baptiste, et al. It also talks about several other papers that employed dominance rules. All these papers talk about dominance rules in customized branch & bound methods (i.e. these branch & bound methods do not employ Math. formulations or CPLEX to solve the problem in hand).
You may be employing CPLEX to solve the problem. But depending on problem structure and the way you are employing cplex to solve your problem, there may or may not be a possibility of employing dominance rules
By the way, what is the problem that you are attempting to solve and how you are employing CPLEX?
Thanks
Sunil
It is a general IP problem I am working on.
Let assume that we have a simple problem Max{x_1+3x_2: 2x_1+x_2<=2 and x_1+2x_2<=1 and x_1,x_2\in {0,1}}
If in BranchCallback, we just write "prune();". it means that it prunes every branch. So it terms of IP solutions, should it give a infeasible message?
I tried it. Cplex solves it as if I have not invoked prune() to its IP solution. Am I right?
My question is what I should do to prune a node completely. 
Re: Branch and bound tree
20121012T09:04:06ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20121005T17:31:28Z
Thanks for your responses and also the paper.
It is a general IP problem I am working on.
Let assume that we have a simple problem Max{x_1+3x_2: 2x_1+x_2<=2 and x_1+2x_2<=1 and x_1,x_2\in {0,1}}
If in BranchCallback, we just write "prune();". it means that it prunes every branch. So it terms of IP solutions, should it give a infeasible message?
I tried it. Cplex solves it as if I have not invoked prune() to its IP solution. Am I right?
My question is what I should do to prune a node completely.
Just writing prune() in a branch callback will prune every node. However, if CPLEX already solves the problem at the root node then this will have no effect as the branch callback is never called in this case. 
Re: Branch and bound tree
20121014T17:52:24ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20121012T09:04:06Z
Can you show us a log file of such a solve?
Just writing prune() in a branch callback will prune every node. However, if CPLEX already solves the problem at the root node then this will have no effect as the branch callback is never called in this case.
IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ".
Tried aggregator 1 time.
MIP Presolve eliminated 2 rows and 3 columns.
MIP Presolve modified 4 coefficients.
All rows and columns eliminated.
Presolve time = 0.00 sec.
Solution value = 1
and this is the logfile when every node is pruned ("ILOBRANCHCALLBACK1(MyBranch) {prune();} ")
IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ".
Tried aggregator 1 time.
MIP Presolve eliminated 2 rows and 2 columns.
MIP Presolve modified 6 coefficients.
Reduced MIP has 0 rows, 1 columns, and 0 nonzeros.
Reduced MIP has 1 binaries, 0 generals, 0 SOSs, and 0 indicators.
Probing time = 0.00 sec.
Tried aggregator 1 time.
Presolve time = 0.00 sec.
Probing time = 0.00 sec.
MIP emphasis: balance optimality and feasibility.
MIP search method: traditional branchandcut.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.00 sec.
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap Variable B NodeID Parent Depth
 0+ 0 1.0000 0 
Root node processing (before b&c):
Real time = 0.00
Sequential b&c:
Real time = 0.00
Total (root+branch&cut) = 0.00 sec.
Solution value = 1
In this simple example, does CPLEX solve the problem in the root node? 
Re: Branch and bound tree
20121015T12:34:16ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20121014T17:52:24Z
Here is the log file for the default setting:
IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ".
Tried aggregator 1 time.
MIP Presolve eliminated 2 rows and 3 columns.
MIP Presolve modified 4 coefficients.
All rows and columns eliminated.
Presolve time = 0.00 sec.
Solution value = 1
and this is the logfile when every node is pruned ("ILOBRANCHCALLBACK1(MyBranch) {prune();} ")
IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ".
Tried aggregator 1 time.
MIP Presolve eliminated 2 rows and 2 columns.
MIP Presolve modified 6 coefficients.
Reduced MIP has 0 rows, 1 columns, and 0 nonzeros.
Reduced MIP has 1 binaries, 0 generals, 0 SOSs, and 0 indicators.
Probing time = 0.00 sec.
Tried aggregator 1 time.
Presolve time = 0.00 sec.
Probing time = 0.00 sec.
MIP emphasis: balance optimality and feasibility.
MIP search method: traditional branchandcut.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.00 sec.
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap Variable B NodeID Parent Depth
 0+ 0 1.0000 0 
Root node processing (before b&c):
Real time = 0.00
Sequential b&c:
Real time = 0.00
Total (root+branch&cut) = 0.00 sec.
Solution value = 1
In this simple example, does CPLEX solve the problem in the root node?