[gecode-users] Not all solutions, BAB vs. DFS

[Martin Kreißig]

Hi again,

I tried my best to create a small example, but then I got stuck during
debugging at creating the DFS engine. (I was lead to core.hpp line 3165
(gecode 3.1.0)).
So I don't know yet if this example produces the problem I have.

The algorithm creates an array with different sets (here 5 sets with 2
values each) and these sets are constrained by some equations (two in
this case) that result in 0.

Here is the code:

#include <gecode/int.hh>
#include <gecode/driver.hh>
#include <iostream>

using namespace Gecode;

class CSP : public Space {
	protected:
	IntVarArray v;
	
	public:
	CSP( int arr[5][2] ) {

	// create array with different sets
	int tmp[2];

	for (int i=0; i<5; i++){
		tmp[0] = arr[i][0]; tmp[1] = arr[i][1];
		IntVar i(*this, IntSet( tmp, 2));
		v.add( *this, i );
	}

	// formulate equations coefficients
	IntArgs ia(5,0,-1,1,1,0);
	IntArgs ib(5,-1,1,-1,0,1);

	// constraints
	linear (*this,ia,v,IRT_EQ, 0, ICL_DEF );
	linear (*this,ib,v,IRT_EQ, 0, ICL_DEF );

	branch ( *this,v,INT_VAR_SIZE_MAX,INT_VAL_MIN );

}

CSP( bool share, CSP& s ) {
	v.update(*this, share, s.v);
}

virtual Space* copy( bool share ) {
	return new CSP(share,*this);
}

void print( void ) {
	std::cout << v << std::endl;
}};

int main( void ) {
	int arr[5][2] = {{-2,1},{-1,5},{3,2},{-4,3},{2,-2}};
	CSP* c = new CSP(arr);
	c->print();
	DFS<CSP> dfs(c);
	delete c;
	CSP* cc;

	while ( cc=dfs.next() ) {
		cc->print();
		delete cc;
	}
	
	return 0;
}

best
Martin


On Fri, 2009-09-04 at 10:34 +0200, Guido Tack wrote:
> Martin Kreißig wrote:
> >> You can use opt.solutions(0) with DFS, too.
> >
> > Alright, but how do I pass opt to my CSP object?
> 
> You don't.  The Options class is for use with the driver  
> infrastructure.  So either you use the driver, and Script::run, or you  
> don't use options.  There's a different options class controlling the  
> search itself (it's documented).
> 
> > The problem is: When testing I insert - lets say 3 - specific  
> > combination of variables that fulfil the constraints. Then every  
> > variable gets its set (of size 3). So the output should be (at  
> > least) 3 combinations. What I get is some of my original solutions,  
> > some mixed solutions, but some of the originals are skipped.
> >
> > Can it be that some values are deleted? but that shouldnt be the case.
> 
> That's impossible to answer without seeing the actual problem.  Maybe  
> you can post a simple, small example.
> 
> Cheers,
> 	Guido
-- 
Martin Kreißig <martin.kreissig at lss.uni-stuttgart.de>