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
[EMAIL PROTECTED]
https://www.gecode.org/mailman/listinfo/gecode-users
