I post here to ask if there is a way to alternate different strategies of branching. Let me explain, I have an efficient branching strategy which we'll call the strategy A. The biggest problem is that the strategy A cannot be used that often. So when I cannot use the strategy A, I use another strategy, which I'll call the strategy B, which is less efficient.
The documentation says that:
Brancher order. Creating a brancher registers it with its home space. A space maintains a queue of its branchers in that the brancher that is registered first is also used first for branching. The first brancher in the queue of branchers is referred to as the current brancher.
So, I supposed that if I post the brancher A then the brancher B, the brancher A will has priority and each time the status of A says there is no branching to do, the brancher B will be used. Seems like I was wrong because when the status of a brancher return false, it is never called again.
Here is a "minimal example":
#include <gecode/minimodel.hh>
#include <iostream>
using namespace Gecode;
using namespace std;
class MyChoice : public Choice {
public:
int pos; // Position of the variable
int val; // Value of to assign
MyChoice(const Brancher& b, int pos0, int val0)
: Choice(b,2), pos(pos0), val(val0) {}
// Report size occupied
virtual size_t size(void) const {
return sizeof(*this);
}
// Archive into e
virtual void archive(Archive& e) const {
Choice::archive(e);
e << pos << val;
}
};
class BranchA : public Brancher {
protected:
ViewArray<Int::IntView> x;
public:
BranchA(Home home, ViewArray<Int::IntView>& x0)
: Brancher(home), x(x0) {}
static void post(Home home, ViewArray<Int::IntView>& x) {
(void) new (home) BranchA(home,x);
}
virtual size_t dispose(Space& home) {
(void) Brancher::dispose(home);
return sizeof(*this);
}
BranchA(Space& home, bool share, BranchA& b)
: Brancher(home,share,b) {
x.update(home,share,b.x);
}
virtual Brancher* copy(Space& home, bool share) {
return new (home) BranchA(home,share,*this);
}
// status
virtual bool status(const Space& home) const {
for (int i=0; i<x.size(); i++)
if (!x[i].assigned())
return !i%2 && x[i].in(1);
return false;
}
// choice
virtual Choice* choice(Space& home) {
for (int i=0; true; i++)
if (!x[i].assigned())
return new MyChoice(*this,i,1);
GECODE_NEVER;
return NULL;
}
virtual Choice* choice(const Space&, Archive& e) {
int pos, val;
e >> pos >> val;
return new MyChoice(*this, pos, val);
}
// commit
virtual ExecStatus commit(Space& home,
const Choice& c,
unsigned int a) {
const MyChoice& pv = static_cast<const MyChoice&>(c);
int pos=pv.pos, val=pv.val;
if (a == 0)
return me_failed(x[pos].eq(home,val)) ? ES_FAILED : ES_OK;
else
return me_failed(x[pos].nq(home,val)) ? ES_FAILED : ES_OK;
}
};
void branchA(Home home, const IntVarArgs& x) {
if (home.failed()) return;
ViewArray<Int::IntView> y(home,x);
BranchA::post(home,y);
}
// BranchB //////////////////////////////////////////////////////
class BranchB : public Brancher {
protected:
ViewArray<Int::IntView> x;
public:
BranchB(Home home, ViewArray<Int::IntView>& x0)
: Brancher(home), x(x0) {}
static void post(Home home, ViewArray<Int::IntView>& x) {
(void) new (home) BranchB(home,x);
}
virtual size_t dispose(Space& home) {
(void) Brancher::dispose(home);
return sizeof(*this);
}
BranchB(Space& home, bool share, BranchB& b)
: Brancher(home,share,b) {
x.update(home,share,b.x);
}
virtual Brancher* copy(Space& home, bool share) {
return new (home) BranchB(home,share,*this);
}
// status
virtual bool status(const Space& home) const {
for (int i=0; i<x.size(); i++)
if (!x[i].assigned())
return i%2 && x[i].in(2);
return false;
}
// choice
virtual Choice* choice(Space& home) {
for (int i=0; true; i++)
if (!x[i].assigned())
return new MyChoice(*this,i,2);
GECODE_NEVER;
return NULL;
}
virtual Choice* choice(const Space&, Archive& e) {
int pos, val;
e >> pos >> val;
return new MyChoice(*this, pos, val);
}
// commit
virtual ExecStatus commit(Space& home,
const Choice& c,
unsigned int a) {
const MyChoice& pv = static_cast<const MyChoice&>(c);
int pos=pv.pos, val=pv.val;
if (a == 0)
return me_failed(x[pos].eq(home,val)) ? ES_FAILED : ES_OK;
else
return me_failed(x[pos].nq(home,val)) ? ES_FAILED : ES_OK;
}
};
void branchB(Home home, const IntVarArgs& x) {
if (home.failed()) return;
ViewArray<Int::IntView> y(home,x);
BranchB::post(home,y);
}
// Minimal Space ///////////////////////////////////////
class TestSpace : public Space {
protected:
IntVarArray x;
public:
TestSpace(int size)
: x(*this, size, 0, 10) {
branchA(*this, x);
branchB(*this, x);
}
TestSpace (bool share, TestSpace& s)
: Space(share, s) {
x.update(*this, share, s.x);
}
virtual Space* copy (bool share) {
return new TestSpace(share, *this);
}
void print(std::ostream& os) {
os << "x= " << x << endl;
}
};
// Minimal Main //////////////////////:
int main (int, char**) {
// create model and search engine
TestSpace* m = new TestSpace(10);
DFS<TestSpace> e(m);
delete m;
// search and print all solutions
while (TestSpace* s = e.next()) {
s->print(cout); delete s;
}
return 0;
}
In this example, the status of the brancher A return true if the next variable to assign is on an even index and if the variable can take the value of 1 (false else). And the brancher B status return true if the next variable to assign is on an odd index and if the variable can take the value of 2 (false else).
With that code I expected to get the solutions [1, 2, 1, 2, ...] and [!1, !2, !1, !2, ...] (and others combinations like [!1, 2, 1, !2, ...]) but since the branchers are disposed when their status return false, only the two first variables have been assigned.
Is there a good way to make the brancher not being disposed after its status return false (or to alternate two differents branching strategies) or should I merge the two branchers into one ?
