[gecode-users] Branching and FlatZincGecode

[Morten Boysen]

Hi Guido

Thank you very much for the reply. I do have some follow-up questions:

>> 3) I want to make a branching that follows the standard "fail-first"
>> heuristic, that is, choose the value with the smallest domain possible
>> and then use a special value heuristic. As I understand I need to
>> implement a branching for the integer variables in the FlatZincGecode
>> space and a branching for the boolean variables. If I understand it
>> correctly, this means the search will process all integer variables
>> first and then the boolean variables or vice verse, depending on the
>> order the branching were posted to the space (the branching posted first
>> is tested first). Is this correct?
> 
> Yes, that's right.  For your own branching, you can reuse the 
> ViewValBranching class, and instantiate it with the BySizeMin view 
> selector class and your own value selector.  Then you can add support 
> for that branching to the FlatZinc parser in gecode.cc, in the function 
> parseSolveAnn.  That's also the place where you can disable the default 
> branching.  Let us know if you need more help.

Earlier I was advised not to use the ViewValBranching class, but to 
implement the complete branching (I originally implemented this 
branching a couple of months ago, but never got around to make it work). 
  It works now, but I am a bit unsure whether it is as efficient as the 
standard Gecode branchings (The IConfigurator class can be seen as a 
black-box, where we can get a set from with some values. We want to find 
a value, that is not in this set):

class BranchingIntegers : public Gecode::Branching
{
public:

   virtual const BranchingDesc* description(const Space* home) const;

   virtual bool status(const Space* home) const;
   virtual ExecStatus commit(Space* home,
                             const BranchingDesc* d,
                             unsigned int a);

   // Copy a BranchingIntegers object.
   virtual Actor* copy(Space *home, bool share);

   // Add the branching strategy to the space home,
   // where the home has the IntVarArgs vars
   static void post( Space* home, IntVarArgs vars, IConfigurator* conf );

private:
   static const int POS_BEGIN = -1;
   static const int VAL_BEGIN = -1;

   const IConfigurator& configurator;

   Gecode::ViewArray<Gecode::Int::IntView> vars;
   mutable int pos; // TODO: Is this neeeded?
   mutable int val; // TODO: Is this neeeded?

   BranchingIntegers(Space* home,
                     ViewArray<Int::IntView>& xv,
                     const IConfigurator& conf);

   BranchingIntegers(Space* home, bool share, BranchingIntegers& b);
};


BranchingIntegers::BranchingIntegers(Space* home, 	
                                      ViewArray<Int::IntView>& xv,
                                      const IConfigurator& conf)
   : Branching( home ),
     vars( xv ),
     configurator( conf ),
     pos( POS_BEGIN ),
     val( VAL_BEGIN )
{ }


BranchingIntegers::BranchingIntegers(Space* home,
                                      bool share,
                                      BranchingIntegers& b)
   : Branching(home, share, b),
     configurator(b.configurator),
     pos(b.pos),
     val(b.val)
{
   vars.update(home, share, b.vars);
}

// What does this do???
const BranchingDesc* BranchingIntegers::description(const Space*) const
{
   assert( pos != POS_BEGIN && pos < vars.size() );
   return new PosValDesc<int,2>(this, pos, val);
}

// Compute the variable and value to branch on
bool BranchingIntegers::status(const Space* home) const
{
   // First we find the variable to branch one, using the standard
   // fail-first heuristic where the variable with the smallest domain is
   // chosen. This is done by iterating over all variable, checking
   // if they have been assigned, and if not, then we check whether the
   // domain of the variable is smaller than the smallest seen so far. If
   // it is, we choose the new one. There is no tiebreaking as the
   // first variable occuring with the smallest domain is used.
   int smallest_domain = numeric_limits<int>::max();

   for ( int i = 0; i < vars.size(); ++i ) {
     if ( !vars[i].assigned() ) {
       if ( vars[i].size() < smallest_domain ) {
         pos = i;
         smallest_domain = vars[i].size();
       }
     }
   }
   if ( pos == POS_BEGIN ) {
     // No non-assigned variables left
     return false;
   }

   // When the variable has been detected we need to find a value that
   // does not have support. In case several values does not have
   // support, we choose the first one. If all values have support
   // we choose the first one in the domain.

   // Get the valid domains computed so far for variable
   // we are dealing with.
   const set<int>& valid = configurator.getValidIntegerDomain( pos );

   // Iterate over the values in the view and take the
   // first one not found to be valid
   Int::ViewValues<Int::IntView> vals( vars[pos] );
   val = vals.val();
   while ( vals() ) {
     if ( valid.find( vals.val() ) == valid.end() ) {
       // This value has not been found to be valid yet, so use it.
       val = vals.val();
       return true;
     }
     ++vals;
   }

   // If we reach here, all values were supported,
   // so use the first one in the domain.
   return true;
}

ExecStatus BranchingIntegers::commit(Space *home,
                                      const BranchingDesc* d,
                                      unsigned int a)
{
   const PosValDesc<int,2> *desc =
     static_cast<const PosValDesc<int,2>*>( d );
   pos = POS_BEGIN;
   val = VAL_BEGIN;
   if ( a ) {
     return me_failed( vars[desc->pos()].nq( home, desc->val() ) )
                       ? ES_FAILED : ES_OK;
   }
   else {
     return me_failed( vars[desc->pos()].eq( home, desc->val() ) )
                       ? ES_FAILED : ES_OK;
   }
}

// Copy a BranchingIntegers object.
Actor* BranchingIntegers::copy(Space *home, bool share)
{
   return new (home) BranchingIntegers(home, share, *this);
}

// Add the branching strategy to the space home,
// where the home has the IntVarArgs vars
void BranchingIntegers::post( Space* home,
                               IntVarArgs vars,
                               IConfigurator* conf )
{
   ViewArray<Int::IntView> xv( home, vars );
   (void) new (home) BranchingIntegers( home, xv, *conf );
}

Kind regards
Morten