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

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
    ACCEPTED ANSWER

    Re: Branch and bound tree

    ‏2012-10-01T21:48:01Z  in response to SystemAdmin
    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
      ACCEPTED ANSWER

      Re: Branch and bound tree

      ‏2012-10-02T09:31:49Z  in response to SystemAdmin
      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
        ACCEPTED ANSWER

        Re: Branch and bound tree

        ‏2012-10-02T13:52:50Z  in response to SystemAdmin
        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
          ACCEPTED ANSWER

          Re: Branch and bound tree

          ‏2012-10-02T16:54:36Z  in response to SystemAdmin
          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
            ACCEPTED ANSWER

            Re: Branch and bound tree

            ‏2012-10-02T17:06:57Z  in response to SystemAdmin
            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
              ACCEPTED ANSWER

              Re: Branch and bound tree

              ‏2012-10-03T08:04:20Z  in response to chintasunny
              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,
              • chintasunny
                chintasunny
                23 Posts
                ACCEPTED ANSWER

                Re: Branch and bound tree

                ‏2012-10-04T11:07:37Z  in response to SystemAdmin
                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
                  ACCEPTED ANSWER

                  Re: Branch and bound tree

                  ‏2012-10-05T17:30:12Z  in response to chintasunny
                  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
                  ACCEPTED ANSWER

                  Re: Branch and bound tree

                  ‏2012-10-05T17:31:28Z  in response to chintasunny
                  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
                    ACCEPTED ANSWER

                    Re: Branch and bound tree

                    ‏2012-10-12T09:04:06Z  in response to SystemAdmin
                    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
                      ACCEPTED ANSWER

                      Re: Branch and bound tree

                      ‏2012-10-14T17:52:24Z  in response to SystemAdmin
                      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
                        ACCEPTED ANSWER

                        Re: Branch and bound tree

                        ‏2012-10-15T12:34:16Z  in response to SystemAdmin
                        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.
          • SystemAdmin
            SystemAdmin
            754 Posts
            ACCEPTED ANSWER

            Re: Branch and bound tree

            ‏2012-10-03T23:39:16Z  in response to SystemAdmin
            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)