Topic
  • 4 replies
  • Latest Post - ‏2013-06-28T09:16:00Z by mrmag
mrmag
mrmag
28 Posts

Pinned topic Branching the nodes with the smallest bound first

‏2013-06-18T20:14:53Z |
Hello,
 
How can I change the processing order of nodes for the branching tree (or IlcGoal-s in terms of CPO)? 
 
The idea comes from the ILP where the nodes of the branching tree with the smallest LP lower bound (for minimization problem) are processed first. This greedy strategy is based on the logical hypothesis that the optimal solution is probably in the nodes with the smallest bound.
 
I defined a custom constraint where I define a propagation() procedure where I calculate the lower bound for a node:

class IlcMyConstraintI : public IlcConstraintI {

  virtual void propagate() {
    
    // calculate the lower bound lb for the current node
 
    _obj->setMin(lb);
 
  }
};
 
 
How can I now process (branch) the nodes with the smallest lower bound first?
 
Updated on 2013-06-18T20:16:09Z at 2013-06-18T20:16:09Z by mrmag
  • Philippe_Refalo
    Philippe_Refalo
    50 Posts

    Re: Branching the nodes with the smallest bound first

    ‏2013-06-20T07:52:20Z  

    I see two possibilities, both using search phases

    1. Create a subclass of IloIntVarEvalI and/or IloIntValueEvalI that evaluates variables and values from the lower bound. Then use them in a selector (IloSelectSmallest, IloSelectLargest).  In this case you can use them in combination with other selectors. 

    2. Create a var and/or variable chooser by subclassing the IloVarChooserI. In this case you need to return one variable or one value to branch on.

    Regards

    Philippe

     

     

     

  • mrmag
    mrmag
    28 Posts

    Re: Branching the nodes with the smallest bound first

    ‏2013-06-20T12:29:18Z  

    I see two possibilities, both using search phases

    1. Create a subclass of IloIntVarEvalI and/or IloIntValueEvalI that evaluates variables and values from the lower bound. Then use them in a selector (IloSelectSmallest, IloSelectLargest).  In this case you can use them in combination with other selectors. 

    2. Create a var and/or variable chooser by subclassing the IloVarChooserI. In this case you need to return one variable or one value to branch on.

    Regards

    Philippe

     

     

     

    Thank you for the answer, Phillipe.
     
    The idea is a bit different. I have a set of decision variables _w[]. Some of them are fixed, the rest is not fixed. Based on the information which variable are fixed and which are not I calculate an upper bound for the objective expression (this is done in a user defined constraint). The problem is that I do not branch on the IloNumVar _obj for the objective expression.
     
    I need to branch on the variables as in the SimpleInstantiate, but select the variables _w[] for which _obj->getMax() is the largest.
     
    Unfortunately, both of the proposed solutions do not work. And it is not possible to use my SimpleInstantiate branching strategy while I use UpperBoundVarI and UpperBoundValI. Is it possible to realise the idea? Is it possible to select _w[] (a node of the branching tree) based on the _obj.getMax()?
     
     
     
     
    class UpperBoundVarI : public IloIntVarEvalI {
    private:
      IloNumVar _obj;
    public:
      UpperBoundVarI(IloEnv env, IloNumVar obj) : IloIntVarEvalI(env), _obj(obj) { }
      IloNum eval(IloCP cp, IloIntVar v) { 
        return _obj.getUB(); 
      }
    };
    IloIntVarEval UpperBoundVar(IloEnv env, IloNumVar obj) 
      return new (env) UpperBoundVarI(env, obj); 
    }
     
     
    class UpperBoundValI : public IloIntValueEvalI {
      private:
      IloNumVar _obj;
    public:
      UpperBoundValI(IloEnv env, IloNumVar obj) : IloIntValueEvalI(env), _obj(obj) { }
      IloNum eval(IloCP cp, IloIntVar var, IloInt value) {
        return _obj.getUB();
      }
    };
    IloIntValueEval UpperBoundVal(IloEnv env, IloNumVar obj) {
      return new (env) UpperBoundValI(env, obj);
    }
     
     
    ILCGOAL3(SimpleInstantiate,
             IlcInt,         _n, 
             IlcIntVar *,    _w, 
             IlcFloatVar *,  _obj
            )
    {
      int k = 0;
      for (; k < _n; k++)
        if (!_w[k].isFixed())
          break;
     
      if (k >= _n)
        return 0;
     
      IlcInt val = _w[k].getMin();
      
      return IlcAnd(IlcOr(_w[k] == val, _w[k] != val), this);
    }
     
     
    class IlcMyConstraintI : public IlcConstraintI {
    protected:
      IlcInt             _n;
      IlcIntVar *        _w;
      IlcFloatVar *      _obj;
     public:
      IlcMyConstraintI (IloCP cp, IlcInt n, IlcIntVar * aa, IlcFloatVar * bb
      ) : IlcConstraintI(cp), _n(n), _w(aa), _obj(bb)
      {
      }
      ~IlcMyConstraintI () {}
      virtual void post();
      virtual void propagate();
      void varDemon();
    };
     
    void IlcMyConstraintI::propagate() {
      // calculate an upper bound based on _w[]
     
      _obj->setMax(ub);
    }
     
     
    int main () {
     
      IloModel model(env);
     
      IloIntVarArray x(env);
     
      IloNumExpr objexpr = ...;
     
      IloNumVar objvar(env);
      
      model.add(objvar == objexpr);
     
      model.add(IloMaximize(env, objvar));
     
      model.add(IloMyConstraint(env, x, objvar));
     
      IloGoal simple_goal = WrapperSimpleInstantiate(env, x, objvar);
     
      IloCP cp(model);
     
      IloIntVarEval   varEval  = UpperBoundVar(env, objvar);
      IloIntValueEval valEval  = UpperBoundVal(env, objvar);
      IloSearchPhase phase(env, x, IloSelectLargest(varEval),
                                   IloSelectLargest(valEval));
     
      cp.startNewSearch(phase);
      //cp.startNewSearch(simple_goal);
      while(cp.next()) {
       ...
      }
    }
     
     
     
    Updated on 2013-06-20T12:33:14Z at 2013-06-20T12:33:14Z by mrmag
  • Philippe_Refalo
    Philippe_Refalo
    50 Posts

    Re: Branching the nodes with the smallest bound first

    ‏2013-06-20T15:35:52Z  
    • mrmag
    • ‏2013-06-20T12:29:18Z
    Thank you for the answer, Phillipe.
     
    The idea is a bit different. I have a set of decision variables _w[]. Some of them are fixed, the rest is not fixed. Based on the information which variable are fixed and which are not I calculate an upper bound for the objective expression (this is done in a user defined constraint). The problem is that I do not branch on the IloNumVar _obj for the objective expression.
     
    I need to branch on the variables as in the SimpleInstantiate, but select the variables _w[] for which _obj->getMax() is the largest.
     
    Unfortunately, both of the proposed solutions do not work. And it is not possible to use my SimpleInstantiate branching strategy while I use UpperBoundVarI and UpperBoundValI. Is it possible to realise the idea? Is it possible to select _w[] (a node of the branching tree) based on the _obj.getMax()?
     
     
     
     
    class UpperBoundVarI : public IloIntVarEvalI {
    private:
      IloNumVar _obj;
    public:
      UpperBoundVarI(IloEnv env, IloNumVar obj) : IloIntVarEvalI(env), _obj(obj) { }
      IloNum eval(IloCP cp, IloIntVar v) { 
        return _obj.getUB(); 
      }
    };
    IloIntVarEval UpperBoundVar(IloEnv env, IloNumVar obj) 
      return new (env) UpperBoundVarI(env, obj); 
    }
     
     
    class UpperBoundValI : public IloIntValueEvalI {
      private:
      IloNumVar _obj;
    public:
      UpperBoundValI(IloEnv env, IloNumVar obj) : IloIntValueEvalI(env), _obj(obj) { }
      IloNum eval(IloCP cp, IloIntVar var, IloInt value) {
        return _obj.getUB();
      }
    };
    IloIntValueEval UpperBoundVal(IloEnv env, IloNumVar obj) {
      return new (env) UpperBoundValI(env, obj);
    }
     
     
    ILCGOAL3(SimpleInstantiate,
             IlcInt,         _n, 
             IlcIntVar *,    _w, 
             IlcFloatVar *,  _obj
            )
    {
      int k = 0;
      for (; k < _n; k++)
        if (!_w[k].isFixed())
          break;
     
      if (k >= _n)
        return 0;
     
      IlcInt val = _w[k].getMin();
      
      return IlcAnd(IlcOr(_w[k] == val, _w[k] != val), this);
    }
     
     
    class IlcMyConstraintI : public IlcConstraintI {
    protected:
      IlcInt             _n;
      IlcIntVar *        _w;
      IlcFloatVar *      _obj;
     public:
      IlcMyConstraintI (IloCP cp, IlcInt n, IlcIntVar * aa, IlcFloatVar * bb
      ) : IlcConstraintI(cp), _n(n), _w(aa), _obj(bb)
      {
      }
      ~IlcMyConstraintI () {}
      virtual void post();
      virtual void propagate();
      void varDemon();
    };
     
    void IlcMyConstraintI::propagate() {
      // calculate an upper bound based on _w[]
     
      _obj->setMax(ub);
    }
     
     
    int main () {
     
      IloModel model(env);
     
      IloIntVarArray x(env);
     
      IloNumExpr objexpr = ...;
     
      IloNumVar objvar(env);
      
      model.add(objvar == objexpr);
     
      model.add(IloMaximize(env, objvar));
     
      model.add(IloMyConstraint(env, x, objvar));
     
      IloGoal simple_goal = WrapperSimpleInstantiate(env, x, objvar);
     
      IloCP cp(model);
     
      IloIntVarEval   varEval  = UpperBoundVar(env, objvar);
      IloIntValueEval valEval  = UpperBoundVal(env, objvar);
      IloSearchPhase phase(env, x, IloSelectLargest(varEval),
                                   IloSelectLargest(valEval));
     
      cp.startNewSearch(phase);
      //cp.startNewSearch(simple_goal);
      while(cp.next()) {
       ...
      }
    }
     
     
     

    You cannot use the bounds on the objective because they stay the same at a given node. However, you need to parameterize your lower bound computation so that it uses the current bounds on variables _w[]  plus  a given instantiation _w[i] == value. This is the method that you need to call at each variable _w[i] evaluation for some or all the values remaining in its domain. This probably requires significant changes in your code.  

    Note that since you are minimizing, the important information is the lower bound.

    - For selecting variables, one will prefer to choose the variable that has the greatest impact on the objective (that is the one that will raise the lower bound the most when assigned to the possible choices). In other words, since you need to branch on every variable, it is more efficient to branch first on the ones that will be harder to give a good value for obtaining a good solution.

    - For selecting values, the problem is different. Here you need to choose one value only, and it is better to choose the one that raises the lower bound the least. It is the one that will lead more quickly to better quality solutions.

    This strategy is refered to as pseudo-cost branching in the litterature, if you want to dig this more. 

    Philippe

    Updated on 2013-06-20T18:11:37Z at 2013-06-20T18:11:37Z by Philippe_Refalo
  • mrmag
    mrmag
    28 Posts

    Re: Branching the nodes with the smallest bound first

    ‏2013-06-28T09:16:00Z  

    You cannot use the bounds on the objective because they stay the same at a given node. However, you need to parameterize your lower bound computation so that it uses the current bounds on variables _w[]  plus  a given instantiation _w[i] == value. This is the method that you need to call at each variable _w[i] evaluation for some or all the values remaining in its domain. This probably requires significant changes in your code.  

    Note that since you are minimizing, the important information is the lower bound.

    - For selecting variables, one will prefer to choose the variable that has the greatest impact on the objective (that is the one that will raise the lower bound the most when assigned to the possible choices). In other words, since you need to branch on every variable, it is more efficient to branch first on the ones that will be harder to give a good value for obtaining a good solution.

    - For selecting values, the problem is different. Here you need to choose one value only, and it is better to choose the one that raises the lower bound the least. It is the one that will lead more quickly to better quality solutions.

    This strategy is refered to as pseudo-cost branching in the litterature, if you want to dig this more. 

    Philippe

    Philippe, thank you for the answer!
     
    Often a lower bound suggests the best direction of branching. It could be great to have the possibility to change the order of exploration of IloGoals.