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
NOTICE: developerWorks Community will be offline May 2930, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
This topic has been locked.
13 replies
Latest Post
 20121015T12:34:16Z by SystemAdmin
ACCEPTED ANSWER
Pinned topic Branch and bound tree
20121001T20:44:31Z

Answered question
This question has been answered.
Unanswered question
This question has not been answered yet.
Updated on 20121015T12:34:16Z at 20121015T12:34:16Z by SystemAdmin

ACCEPTED ANSWER
Re: Branch and bound tree
20121001T21:48:01Z in response to SystemAdminI 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)
ACCEPTED ANSWER
Re: Branch and bound tree
20121002T09:31:49Z in response to SystemAdminThanks 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.
ACCEPTED ANSWER
Re: Branch and bound tree
20121002T13:52:50Z in response to SystemAdminYes, 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.
ACCEPTED ANSWER
Re: Branch and bound tree
20121002T16:54:36Z in response to SystemAdminThanks.
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?
ACCEPTED ANSWER
Re: Branch and bound tree
20121002T17:06:57Z in response to SystemAdminApart 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
ACCEPTED ANSWER
Re: Branch and bound tree
20121003T08:04:20Z in response to chintasunnyThanks 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,
ACCEPTED ANSWER
Re: Branch and bound tree
20121004T11:07:37Z in response to SystemAdminYou 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
ACCEPTED ANSWER
Re: Branch and bound tree
20121005T17:30:12Z in response to chintasunnyThanks 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. An I right?
My question is what I should do to prune a node completely. 
ACCEPTED ANSWER
Re: Branch and bound tree
20121005T17:31:28Z in response to chintasunnyThanks 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.
ACCEPTED ANSWER
Re: Branch and bound tree
20121012T09:04:06Z in response to SystemAdminCan 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.
ACCEPTED ANSWER
Re: Branch and bound tree
20121014T17:52:24Z in response to SystemAdminHere 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?
ACCEPTED ANSWER
Re: Branch and bound tree
20121015T12:34:16Z in response to SystemAdminIn either case CPLEX solves the problem at the root node. The problem is so simple that CPLEX does not even need to branch. Hence the branch callback is never invoked. If you want to see the branch callback in action you need to use a more difficult problem that is not solved at the root node.






ACCEPTED ANSWER
Re: Branch and bound tree
20121003T23:39:16Z in response to SystemAdminIf you are asking how to prune a node, you can invoke the prune() method in a branch 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)



