[gecode-users] Strange behavior of BAB search with the function CONSTRAIN

[Guido Tack]

Dear Raffaele,

this behaviour is due to a bug in your code, or rather, due to a  
misunderstanding how the constrain function works.

Constrain must post a constraint that states that all solutions found  
from now on are "better" than the one we just discovered.  In your  
code, you only make sure that the 5th solution is better than the 4th  
(where better means that x[1]==1), but you say nothing about how the  
6th solution is related to the 5th!

In your concrete example, suppose you go down the left branch of the  
search tree and find the 4th solution.  You backtrack one level, go to  
the right, post the constraint x[1]==1, and find another solution.  So  
now you increment your solution counter, and when you backtrack  
further, there are still "open nodes" in the search tree that need to  
be constrained.  But as you incremented the solution counter, the  
constrain function will not post the x[1]==1 constraint again.  So,  
for the 5th solution, constrain does not subsume the constraint you  
posted for the 4th solution.

If you replace solutions_number == 4 by solutions_number >= 4, the  
code will do what you intended.  Not sure this can easily be done in  
your original example, though.

I hope this clarifies things a bit!

Cheers,
	Guido

Raffaele Cipriano wrote:

> Dear Gecode developers,
> we are using the BAB search with the function "constrain", to  
> implement a cutting-plane search algorithm, and we have noticed a  
> strange behavior.
>
> At some point of the search we need to add a constrain on the Space  
> we are exploring and we use the function
>
> void constrain( T* t )
>
> The constrain is correctly posted and some solutions are cut off,  
> but when the BAB engine backtracks it looses the constrain added and  
> finds solutions that should be cut off.
>
> We have isolated this behavior in a small example: the source code  
> (MyTest.cc) and the execution output (log.log) are attached. Here it  
> is a brief explanation:
>
> In the example there is only an IntVarArray x, of length 3 and  
> domain 0..2.
> We perform a branch on x, looking for all the solution.
> When the fifth solution has been discovered we post the constrain  
> x[1] = 1.
> The constrain is posted, in fact solution {0, 2, 0}, {0, 2, 1},  
> {0,2, 2} are not enumerated.
> But when the engine backtracks to the x[0] level, the constraint is  
> lost and all the possible remaining solutions are found: according  
> to the constrain posted, solution 7 to 9, 13 to 18 and 22 to 24  
> should be cut-off.
>
> Is this a normal behavior or a bug?
>
> Is there any alternative way to add constraints at run time?
>
> Thank you very much
>
> Best regards
>
> Raffaele Cipriano
>
> #include "support.hh"
> #include "gecode/minimodel.hh"
>
> int solutions_number;
>
> class MyTest : public Example {
>
> public:
> 	IntVarArray x;
>
> 	MyTest(const SizeOptions& opt)
> 	: x(this,3,0,2) {
> 		branch(this, x, INT_VAR_NONE, INT_VAL_MIN);
> 	}
>
> 	/// Constructor for cloning \a s
> 	MyTest(bool share, MyTest& s) : Example(share,s) {
> 		x.update(this, share, s.x);
> 	}
>
> 	/// Perform copying during cloning
> 	virtual Space*
> 		copy(bool share) {
> 	return new MyTest(share,*this);
> 	}
>
> 	void constrain(MyTest * solution) {
> 		if (solutions_number == 4) {
> 			std::cout << "put constraint x[1] = 1" << std::endl;
> 			rel(this,x[1],IRT_EQ,1,ICL_DEF,PK_DEF);
> 		}
> 		solutions_number++;
> 	}
>
> 	/// Print solution
> 	virtual void print(std::ostream& os) {
> 		os << "solution "<< solutions_number << ": " << x << std::endl;
> 	}
> };
>
> /** \brief Main-function
> */
> int main(int argc, char* argv[]) {
> 	solutions_number = 0;
> 	SizeOptions opt("MyTest");
> 	opt.iterations(20);
> 	opt.solutions(0);
> 	opt.parse(argc,argv);
> 	Example::run<MyTest,BAB,SizeOptions>(opt);
> 	return 0;
> }
> MyTest
> solution 0: {0, 0, 0}
> solution 1: {0, 0, 1}
> solution 2: {0, 0, 2}
> solution 3: {0, 1, 0}
> solution 4: {0, 1, 1}
> put constraint x[1] = 1
> solution 5: {0, 1, 2}
> solution 7: {1, 0, 0}
> solution 8: {1, 0, 1}
> solution 9: {1, 0, 2}
> solution 10: {1, 1, 0}
> solution 11: {1, 1, 1}
> solution 12: {1, 1, 2}
> solution 13: {1, 2, 0}
> solution 14: {1, 2, 1}
> solution 15: {1, 2, 2}
> solution 16: {2, 0, 0}
> solution 17: {2, 0, 1}
> solution 18: {2, 0, 2}
> solution 19: {2, 1, 0}
> solution 20: {2, 1, 1}
> solution 21: {2, 1, 2}
> solution 22: {2, 2, 0}
> solution 23: {2, 2, 1}
> solution 24: {2, 2, 2}
>
> Initial
> 	propagators:   0
> 	branchings:    1
>
> Summary
> 	runtime:       0.010 (10.000000 ms)
> 	solutions:     24
> 	propagations:  0
> 	failures:      1
> 	clones:        48
> 	commits:       66
> 	peak memory:   14 KB
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20080418/9208259a/attachment.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2436 bytes
Desc: not available
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20080418/9208259a/attachment.bin>