[gecode-users] gecode-users Digest, Vol 25, Issue 3
'Stanimir Dragiev'
stanio at cs.tu-berlin.de
Thu Oct 18 18:52:02 CEST 2007
Hello,
* Christian Schulte <cschulte at kth.se> [2007-10-17 15:17]:
> actually I am totally lost now: What do you really do? Is it that you solve
> a problem with search and there abs is not propagated? Or what?
I am sorry for not explaining clear enough. I thought there is a
general mistake in the code you will find at first glance.
I am extending the Example class and invoking some static functions
from within the constructor, after initialisation and before
branching. They realize "complex" constraints by invoking
gecode-built-in constraints.
The pieces of code I posted couple of days ago were outline of what is
done in one such function invoked by the constrain() method of my
space. I experienced the abs(Space*, IntVar a, IntVar b) to leave
b unconstrained ... while the other way round: post(abs(....)) worked
well.
So, today I tested a minimal example with both pieces of code and
they resulted again in _not_ identical output. Please find the example
below.
Again, sorry for bothering you. My code seems to work now anyway
(with the second way of using abs()), but I am still curious to
understand the reason.
>
> Maybe you send us the code that exhibits the problem.
Well, here the code, which shows the both ways of using abs() behave
in different way (according to me). I apparently miss something
important.
--------- code --------------------------------------------
// Last edited: <2007-10-18 Thu 18:40:03 stanio_>
#include "support.hh"
#include "gecode/minimodel.hh"
/**
* Problem: Find _all_ pairs (a, b) ,
* a,b \in 0..n
* a + b = n
*
*/
class Test_common : public Example{
protected:
IntVarArray vars;
int n;
public:
Test_common(const Options& opt) :
vars(this,2, 0, opt.size),
n(opt.size)
{
linear(this, vars, IRT_EQ, n);
branch(this, vars, BVAR_SIZE_MIN, BVAL_MIN);
}
Test_common(bool share, Test_common& test) : Example(share, test){
vars.update(this, share, test.vars);
}
virtual Space*
copy(bool share){
return new Test_common(share, *this);
}
virtual void
print(void){
std::cout << "Solution: (a,b) = (" << vars[0] << ", " << vars[1] << ")" << std::endl;
}
};
/**
* Problem: Find _best_ pair (a, b) ,
* a,b \in 0..n
* a + b = n
* |a - b| -> min
*/
class Test_one : public Test_common{
public:
Test_one(const Options &o):Test_common(o){}
void
constrain(Space * space){
Test_one * s = (Test_one *) space;
IntVar signed_diff_now = post(this, vars[0] - vars[1], ICL_DOM);
IntVar abs_diff_now(this, 0, n);
abs(this, signed_diff_now, abs_diff_now, ICL_DOM);
IntVar signed_diff_best = post(s, s->vars[0] - s->vars[1], ICL_DOM);
IntVar signed_diff_best_this; signed_diff_best_this.update( this, true, signed_diff_best);
IntVar abs_diff_best(this, 0, n);
abs(this, signed_diff_best_this, abs_diff_best, ICL_DOM);
rel(this, abs_diff_best, IRT_GR, abs_diff_now );
std::cout << "constrain: signed best : " << signed_diff_best <<
" ; best (imported) : " << signed_diff_best_this <<
" ; best : " << abs_diff_best <<
" ; now : " << abs_diff_now << std::endl;
}
};
/**
* Problem: Find _best_ pair (a, b) ,
* a,b \in 0..n
* a + b = n
* |a - b| -> min
*/
class Test_two : public Test_common{
public:
Test_two(const Options &o):Test_common(o){}
void
constrain(Space * space){
Test_two * s = (Test_two *) space;
IntVar abs_diff_best = post(this,
abs(this,
minus(s, s->vars[0], s->vars[1],
ICL_DOM), ICL_DOM), ICL_DOM);
IntVar abs_diff_now = post(this,
abs(this,
minus(this, vars[0], vars[1],
ICL_DOM), ICL_DOM), ICL_DOM);
rel(this, abs_diff_best, IRT_GR, abs_diff_now );
std::cout << "constrain: best : " << abs_diff_best << " ; now : " << abs_diff_now << std::endl;
}
};
int main(int argc, char** argv) {
int size = 5;
Options opt("Test_common");
opt.solutions = 0;
opt.size = size;
opt.parse(argc,argv);
Example::run<Test_common,DFS>(opt);
opt = Options("Test_one");
opt.solutions = 0;
opt.size = size;
opt.parse(argc,argv);
Example::run<Test_one,BAB>(opt);
opt = Options("Test_two");
opt.solutions = 0;
opt.size = size;
opt.parse(argc,argv);
Example::run<Test_two,BAB>(opt);
return 0;
}
----- end code --------------------------------------------
And here what is this code resulting in.
----- output ----------------------------------------------
Test_common
Solution: (a,b) = (0, 5)
Solution: (a,b) = (1, 4)
Solution: (a,b) = (2, 3)
Solution: (a,b) = (3, 2)
Solution: (a,b) = (4, 1)
Solution: (a,b) = (5, 0)
Initial
propagators: 1
branchings: 1
Summary
runtime: 0
solutions: 6
propagations: 10
failures: 0
clones: 5
commits: 10
peak memory: 6 KB
Test_one
Solution: (a,b) = (0, 5)
constrain: signed best : -5 ; best (imported) : -5 ; best : 5 ; now : [0..4]
Solution: (a,b) = (1, 4)
constrain: signed best : -3 ; best (imported) : -3 ; best : 0 ; now : 0
Initial
propagators: 1
branchings: 1
Summary
runtime: 0
solutions: 2
propagations: 11
failures: 1
clones: 4
commits: 4
peak memory: 6 KB
Test_two
Solution: (a,b) = (0, 5)
constrain: best : 5 ; now : [0..4]
Solution: (a,b) = (1, 4)
constrain: best : 3 ; now : [0..2]
Solution: (a,b) = (2, 3)
constrain: best : 1 ; now : 0
Initial
propagators: 1
branchings: 1
Summary
runtime: 0
solutions: 3
propagations: 37
failures: 1
clones: 6
commits: 6
peak memory: 6 KB
----- end output ------------------------------------------
--
/----------------------------------
/ S|t|a|n|i|m|i|r| D|r|a|g|i|e|v
| a|k|a| C|m|a|p|Y|o|p|c
| [ i c q ] 2 2 2 0 4 0 6 9 8
| [jabber]CmapYopc at users.jabber.org
More information about the gecode-users
mailing list