Topic
  • 13 replies
  • Latest Post - ‏2012-10-15T12:34:16Z by SystemAdmin
SystemAdmin
SystemAdmin
754 Posts

Pinned topic Branch and bound tree

‏2012-10-01T20:44:31Z |
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,
Updated on 2012-10-15T12:34:16Z at 2012-10-15T12:34:16Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    754 Posts

    Re: Branch and bound tree

    ‏2012-10-01T21: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)
  • SystemAdmin
    SystemAdmin
    754 Posts

    Re: Branch and bound tree

    ‏2012-10-02T09:31:49Z  
    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)
    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.
  • SystemAdmin
    SystemAdmin
    754 Posts

    Re: Branch and bound tree

    ‏2012-10-02T13:52:50Z  
    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.
    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.
  • SystemAdmin
    SystemAdmin
    754 Posts

    Re: Branch and bound tree

    ‏2012-10-02T16:54:36Z  
    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.
    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?
  • chintasunny
    chintasunny
    23 Posts

    Re: Branch and bound tree

    ‏2012-10-02T17:06:57Z  
    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?
    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
  • SystemAdmin
    SystemAdmin
    754 Posts

    Re: Branch and bound tree

    ‏2012-10-03T08:04:20Z  
    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
    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,
  • SystemAdmin
    SystemAdmin
    754 Posts

    Re: Branch and bound tree

    ‏2012-10-03T23:39:16Z  
    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?
    If 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)
  • chintasunny
    chintasunny
    23 Posts

    Re: Branch and bound tree

    ‏2012-10-04T11:07:37Z  
    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 can start looking at the paper "A Branch-and-Bound 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
  • SystemAdmin
    SystemAdmin
    754 Posts

    Re: Branch and bound tree

    ‏2012-10-05T17:30:12Z  
    You can start looking at the paper "A Branch-and-Bound 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
    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. An I right?
    My question is what I should do to prune a node completely.
  • SystemAdmin
    SystemAdmin
    754 Posts

    Re: Branch and bound tree

    ‏2012-10-05T17:31:28Z  
    You can start looking at the paper "A Branch-and-Bound 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
    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.
  • SystemAdmin
    SystemAdmin
    754 Posts

    Re: Branch and bound tree

    ‏2012-10-12T09:04:06Z  
    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.
    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.
  • SystemAdmin
    SystemAdmin
    754 Posts

    Re: Branch and bound tree

    ‏2012-10-14T17:52:24Z  
    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.
    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 branch-and-cut.
    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 ---
    0 0 cutoff 1.0000 1.0000 0 0.00%

    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?
  • SystemAdmin
    SystemAdmin
    754 Posts

    Re: Branch and bound tree

    ‏2012-10-15T12:34:16Z  
    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 branch-and-cut.
    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 ---
    0 0 cutoff 1.0000 1.0000 0 0.00%

    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?
    In 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.