Topic
15 replies Latest Post - ‏2013-01-04T16:15:51Z by Tulkas
Tulkas
Tulkas
15 Posts
ACCEPTED ANSWER

Pinned topic BranchCallbacks and LazyConstraints

‏2012-12-11T14:32:24Z |
Since I know my problem well, I've decided to implement a few additional dynamical deduction algorithms thanks to a branch callback. Given a node, and current LBs/UBs, I can indeed fix some new bounds. All my variables being booleans, I thus write something like this:

getBranch(newVars_1, newBounds_1, newDirections_1, 0);
getBranch(newVars_2, newBounds_2, newDirections_2, 1);

...

// variables[currentIndex] = 0.0 with respect to the first branch
newVars_1.add(variables[currentIndex]);
newBounds_1.add(0.0);
directions_1.add(IloCplex::BranchDown);

...

// variables[anotherIndex] = 1.0 with respect to the first branch
newVars_1.add(variables[anotherIndex]);
newBounds_1.add(1.0);
directions_1.add(IloCplex::BranchUp);

...

makeBranch(newVars_1, newBounds_1, newDirections_1, getObjValue(), 0);
makeBranch(newVars_2, newBounds_2, newDirections_2, getObjValue(), 0);

It works in fact very well if I do not post any lazy contraint... In this later case, I sometimes have variables whose lower bound is greater than its upper bounds, i.e. lb = 1.0 / ub = 0.0 !

NB:
  • My lazyconstraints implements some strict dominance rules and thus delete some feasible integer solutions.
  • If I use lazyconstraints only, it works !
  • If I use branch callback only, it works !
  • If I use both, bounds inconsistency appear...
  • I'm not 100% sure this problem comes from either my branch callback or my lazy constraints...

Do you have an idea ?

Thanks a lot !
Updated on 2013-01-04T16:15:51Z at 2013-01-04T16:15:51Z by Tulkas
  • Tulkas
    Tulkas
    15 Posts
    ACCEPTED ANSWER

    Re: BranchCallbacks and LazyConstraints

    ‏2012-12-12T10:06:27Z  in response to Tulkas
    Another remark : it perfectly works if my lazy constraints are added as classical constraints, i.e. model.add(IloRange(...)). I may thus have misunderstood lazy constraints.
  • Tulkas
    Tulkas
    15 Posts
    ACCEPTED ANSWER

    Re: BranchCallbacks and LazyConstraints

    ‏2012-12-12T10:33:14Z  in response to Tulkas
    Please ignore my last post. It does not work so fine finally !
  • SystemAdmin
    SystemAdmin
    7944 Posts
    ACCEPTED ANSWER

    Re: BranchCallbacks and LazyConstraints

    ‏2012-12-13T13:24:42Z  in response to Tulkas
    Do you post the lazy constraints from a callback or do you add them prior to calling solve()?
    At which point do you observe the conflicting bounds?
    • Tulkas
      Tulkas
      15 Posts
      ACCEPTED ANSWER

      Re: BranchCallbacks and LazyConstraints

      ‏2012-12-13T14:37:58Z  in response to SystemAdmin
      I add them prior to calling solve().

      I observe conflicting bounds at the very begining of the branch callback. I just call getLBs(...) and getUBs(...) and check consistency before calling makebranch(...) one or twice.

      For the moment, I have substituded cplex.addLazyConstraint(cons) by model.add(cons) and inconsistencies appear more rarely, but still appear ! I mean from an instance to another ;-)

      Some recent observation :
      1) If I reverse the two callings of makebranch, the problem diseappear... It nevertheless does not convince me !
      2) If I turn preprocessing off, calling cplex.setParam(solver.PreInd, 0);, then itt also disappear ! Could it be a problem between presolved variables and problem variables or something like this ?

      Thanks a lot !
      • SystemAdmin
        SystemAdmin
        7944 Posts
        ACCEPTED ANSWER

        Re: BranchCallbacks and LazyConstraints

        ‏2012-12-13T15:10:37Z  in response to Tulkas
        When you do
        // variables[currentIndex] = 0.0 with respect to the first branch
        newVars_1.add(variables[currentIndex]);
        newBounds_1.add(0.0);
        directions_1.add(IloCplex::BranchDown);
        

        (which sets ub=0), do you check that CPLEX does not try to do a BranchUp on that variable at the same time (which would set lb=1)? In other words, do you check that currentIndex is not yet contained in newVars_1? getBranch() may have returned an array that already contains this variable. In that case you want to remove CPLEX's branching decision on that variable.
        Updated on 2014-03-24T22:43:46Z at 2014-03-24T22:43:46Z by iron-man
        • Tulkas
          Tulkas
          15 Posts
          ACCEPTED ANSWER

          Re: BranchCallbacks and LazyConstraints

          ‏2012-12-13T15:31:33Z  in response to SystemAdmin
          for(int i=0; i < newVars_1.getSize(); ++i)
          if(newVars_1[i].getId() == variablescurrentIndex.getId())
          std::cout << "PROBLEM !!!";

          My prompt is empty :(
          • SystemAdmin
            SystemAdmin
            7944 Posts
            ACCEPTED ANSWER

            Re: BranchCallbacks and LazyConstraints

            ‏2012-12-13T15:55:53Z  in response to Tulkas
            Just to be extra-sure, could you please add something like this right before the call to makeBranch() (and similarly for newVars_2):
            std::set<IloInt> mark1;
            for (IloInt i = 0; i < newVars_1.getSize(); ++i) {
               IloNumVar v = newVars_1[i];
               if (mark1.find(v.getId()) != std::set<IloInt>::end()) {
                  std::cerr << "Duplicate variable " << v << std::endl;
                  ::abort();
               }
               else
                  mark1.insert(v.getId());
            }
            
            Updated on 2014-03-24T22:43:42Z at 2014-03-24T22:43:42Z by iron-man
            • Tulkas
              Tulkas
              15 Posts
              ACCEPTED ANSWER

              Re: BranchCallbacks and LazyConstraints

              ‏2012-12-13T16:16:01Z  in response to SystemAdmin
              I never reach breakpoints at :
              std::cerr << "Duplicate variable " << v << std::endl;
              (for both newVars_1 and newvars_2)

              Nevertheless ! I might have found !

              // I protect variables I might handle through branch callbacks.
              cplex.protectVariables(decisionVariables);

              It seems to work, even with "lazy constraints implementation".

              Could it be right or it is probably "luck" ?
              • Tulkas
                Tulkas
                15 Posts
                ACCEPTED ANSWER

                Re: BranchCallbacks and LazyConstraints

                ‏2012-12-13T18:27:35Z  in response to Tulkas
                If cplex.protectVariables(decisionVariables); works (I'm refering to my question above). It means that my problems were coming from the fact that I attempt to read variables which were aggegated by presolve algorithms or something like this. In that case, shouldn't I have caught an PresolvedVariableException exception ? I also tried to set IloCplex::PreLinear to 0 without success. I was thinking it let cplex translate variables from the presolved problem to the original problem. Am I wrong ?
                • SystemAdmin
                  SystemAdmin
                  7944 Posts
                  ACCEPTED ANSWER

                  Re: BranchCallbacks and LazyConstraints

                  ‏2012-12-14T07:36:19Z  in response to Tulkas
                  It may indeed be the case that you are trying to branch on variables that have been fixed by presolve. To check that you should check BranchCallbackI::getLB() and BranchCallbackI::getUB() for the respective variable before you add it to newVars_1 or newVars_2. Make sure that those bounds do not conflict with the branching decision you are planning to take.
                  As far as I can tell makeBranch() will not throw an exception if you branch on a variable that has been fixed by presolve.
                  PreLinear has nothing to do with the type of model. In Concert all callbacks always operate on the original model (never on the presolved model).
                  • Tulkas
                    Tulkas
                    15 Posts
                    ACCEPTED ANSWER

                    Re: BranchCallbacks and LazyConstraints

                    ‏2012-12-14T08:25:45Z  in response to SystemAdmin
                    So it seems to be luck :( I indeed call BranchCallbackI::getLB() and BranchCallbackI::getUB() before any operation. What I retrieve from these methods is corrupted, i.e lb > ub. My deduction algorithms even work ONLY with these bounds.

                    For instance if x_1 == 1 && x_2 == 0 => x_3 <- 1 (it's naturally much more complicated in reality). I write something like this:

                    getLBs(lb, variables);
                    getUBs(ub, variables);
                    if(lb[x_1] > 1 - EPSILON && ub[x_2] < EPSILON) // if lb > ub, I perform bad deductions ;S
                    {
                    newVars.add(x_3);
                    newBounds.add(1.0);
                    newDirections.add(BranchUp);
                    }

                    To sum up:
                    1) I use LBs and UBs of current node,
                    2) I use the branching variables chosen by CPLEX,
                    => I update LBs and UBs as if branching was already done with respect to branch 0 and branch 1 independently (I only consider getBranchType() == BranchOnVariable) and try to fix more variables on these branches...
                    3) I never perform branching up and branching down on the same variables
                    4) I've checked that I do not perform bad deductions. I compare any deductions to known optimal solutions. If LBs and UBs of this node are compatible with one of these solutions S (this node could lead to S), I compare my deductions to S. I'm therefore sure I'm not implicitely pruning a branch leading to S !
                    5) I prune nodes when my deductions are conflicting with current fixed variables because it means there is not feasible solutions beyond. Once again, I checked I never prune a node leading to an optimal solution.

                    What could it be so ?

                    Thanks !
                    • Tulkas
                      Tulkas
                      15 Posts
                      ACCEPTED ANSWER

                      Re: BranchCallbacks and LazyConstraints

                      ‏2012-12-14T08:35:12Z  in response to Tulkas
                      For information, what disturbs me about presolved and original variables is in the documentation:

                      "Protected variables in presolve reductions
                      Describes the interaction of protected variables and presolve.

                      A final facility that modifies the set of reductions performed by presolve is the CPXcopyprotected routine. The user provides as input a list of variables in the original problem that should survive presolve (that is, should exist in the presolved model). Presolve will avoid reductions that remove those variables, with one exception. If a protected variable can be fixed, presolve will still remove it from the problem. This command is useful in cases where the user wants to explicitly control some aspect of the branch & cut process (for example, through the branch callback) using knowledge about those variables."
                      • Tulkas
                        Tulkas
                        15 Posts
                        ACCEPTED ANSWER

                        Re: BranchCallbacks and LazyConstraints

                        ‏2012-12-17T16:20:13Z  in response to Tulkas
                        With a bit more details...

                        getLBs(lb, variables);
                        getUBs(ub, variables);
                        if(lbx_1 > 1 - EPSILON && ubx_2 < EPSILON && )
                        {

                        if(ubx_3 < EPSILON)
                        prune();

                        if(lbx_3 <= EPSILON)
                        {
                        newVars.add(x_3);
                        newBounds.add(1.0);
                        newDirections.add(BranchUp);
                        }

                        }
                        • SystemAdmin
                          SystemAdmin
                          7944 Posts
                          ACCEPTED ANSWER

                          Re: BranchCallbacks and LazyConstraints

                          ‏2013-01-02T08:48:04Z  in response to Tulkas
                          This code fragment looks wrong:
                          if(ub[x_3] < EPSILON)
                             prune();
                           
                          if(lb[x_3] <= EPSILON)
                          {
                             newVars.add(x_3);
                             newBounds.add(1.0);
                             newDirections.add(BranchUp);
                          }
                          

                          If ub and lb are both 0 for x_3 then you will call prune() and makeBranch() at the same node (which is an error, see documentation of prune()).
                          Do you check that not both bounds for x_3 are 0? Does the problem persist if you immediately 'return' after calling 'prune()'?
                          Updated on 2014-03-24T22:43:20Z at 2014-03-24T22:43:20Z by iron-man
                          • Tulkas
                            Tulkas
                            15 Posts
                            ACCEPTED ANSWER

                            Re: BranchCallbacks and LazyConstraints

                            ‏2013-01-04T16:15:51Z  in response to SystemAdmin
                            I just forget an "else" when writing my message. I cannot call both makeBranch and prune in my callback.

                            if(ub[x_3] < EPSILON)
                            prune();

                            else if(lb[x_3] <= EPSILON)
                            {
                            newVars.add(x_3);
                            newBounds.add(1.0);
                            newDirections.add(BranchUp);
                            }