[gecode-users] Computing Variable Domains

Tue Aug 14 10:19:18 CEST 2012

I think Guido's proposal is a very good one: just reasonable bounds. Here,
reasonable means that the only thing you have to get right is to come up
with bounds for linear constraints. The other constraints do not suffer that
easily from arithmetic overflow.

Keep it simple!

Christian

--

Christian Schulte, www.ict.kth.se/~cschulte/

From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Max Ostrowski
Sent: Tuesday, August 14, 2012 9:34 AM
To: Guido Tack
Cc: users at gecode.org
Subject: Re: [gecode-users] Computing Variable Domains

OK, i see.
This was indeed the thing i wanted to do.
I had some bad experiences with posting propagators on unrestricted
variables.
Given that my supports has a declarative language for the description of the
constraints, no domain is given as input.
That why i wanted to compute one.
But i will now leave it with a simple bound computation using
boost::numeric::interval.

Thanks a lot,
Max

On 08/14/2012 06:52 AM, Guido Tack wrote: 

Sorry but I'm not sure I understand what you're trying to do.  Are you
trying to precompute bounds on the domains of a and b given that there is a
constraint a+b=c in your model?  We don't have specialised iterators for
that kind of computation, and just running propagation (i.e. calling status
once) will give you the same result.  You should only restrict the variables
to reasonable initial domains (i.e., use some easy to compute upper and
lower bounds). But you don't have to do the propagators' job.

Cheers, 

Guido

On 13/08/2012, at 8:57 PM, Max Ostrowski <ostrowsk at cs.uni-potsdam.de> wrote:

Thank you very much for the fast answer.
I tried to play around with them but still face a lot of problems.

In the documentation
http://www.gecode.org/doc-latest/reference/group__FuncIterRangesVirt.html it
is written that
"Iterators with virtual member functions have to be used when they are
combined dynamically ..."
The only base class i found is MinMax.

So how can i use the iterator dynamically.
In the given example i have to know the type of the iterator used before.
(To build the intersection of two Singletons for example)
But if i want to build the intersection of two "domains" which could have
been constructed in various ways (for example recursively),
i need to have a general Base Type, right ?
Is the Iter::Ranges thing still the right thing to use or is there something
else.

Also i found only iterators for union/intersection etc...
Given that you want to add two variables a and b with known domain (stored
in a RangeList?), how do you compute the domain of the result.
Is there any functionality for this or do i have to iterate through both
lists of ranges and add them together to form a new list.

I hope i made things clear, if not please ask.

Best,
Max

On 08/10/2012 06:44 AM, Guido Tack wrote: 

Hi, 

here's some code that will do what you want:

      Iter::Ranges::Singleton si00(6,Int::Limits::max);

      Iter::Ranges::Singleton si10(Int::Limits::min,9);

      Iter::Ranges::Inter<Iter::Ranges::Singleton,Iter::Ranges::Singleton> 

        inter0(si00,si10);

      Iter::Ranges::Singleton si01(101,Int::Limits::max);

      Iter::Ranges::Singleton si11(Int::Limits::min,104);

      Iter::Ranges::Inter<Iter::Ranges::Singleton,Iter::Ranges::Singleton> 

        inter1(si01,si11);

      Iter::Ranges::Union<

Iter::Ranges::Inter<Iter::Ranges::Singleton,Iter::Ranges::Singleton>,

        Iter::Ranges::Inter<Iter::Ranges::Singleton,Iter::Ranges::Singleton>
> 

        u(inter0,inter1);

      IntVar a(*this,IntSet(u));

You can also use the n-ary variants of the iterators if you need to compute
a union or intersection of more than two sets.

Cheers,

Guido

On 08/08/2012, at 9:41 PM, Max Ostrowski <ostrowsk at cs.uni-potsdam.de> wrote:

Sorry for reposting an old question. I'm just cleaning up my code and
noticed that i still not managed to use gecode's functionality to precompute
domains of IntVar.
So, given a constraint "(a>5 /\ a<10) \/ (a>100 /\ a<105)"
I want to precompute the domain of "a".
I'm simply not able to find out how the Ranges iterators are used.
How to i create a range "5..inf" and a range "-inf..10"
How do i create the intersection of both.
And finally how to set the domain of IntVar x to this range then.

I tried to grep the gecode code and the examples but was not able to find
any.

Sorry again for reposting this, i'm ashamed.

Best,
Max

The best is to look for examples in the code ;-) Just grep for it.

MinMax is nothing but a base-class for other classes and cannot be used 
directly. Look for the iterators that take arrays as input, they will do
what 
you want.

Best
Christian

--
Christian Schulte, KTH, web.it.kth.se/~cschulte/
<http://web.it.kth.se/%7Ecschulte/> 

-----Original Message-----
From: users-boun... at gecode.org [mailto:users-boun... at gecode.org] On Behalf
Of 
Max Ostrowski
Sent: Thursday, July 21, 2011 10:49 AM
To: users at gecode.org
Subject: [gecode-users] Computing Variable Domains (Integer)

Hello everybody,

as variables in gecode need to have a domain, i want to compute the domain
of 
the variables automatically, given the constraints.
I could also let the constraints restrict the domains of my variables, but
as i 
understood, this is similar to propagation and could take some time.
There i want to restrict the domain manually for all unary constraints.
So, given a constraint "(a>5 /\ a<10) \/ (a>100 /\ a<105)"
the domain should be {6..9,101..104}.
Therefore i wanted to use some Gecode classes to compute the 
intersection/union/complement etc.. of the sets.
Am i right that i can use the Int::Iter::Ranges classes for this?
And second, how do they work?
So in this case, i would create a 

IntSet a1(Gecode::Iter::Ranges::MinMax(5+1,Int::Limits::max));
IntSet a2(Gecode::Iter::Ranges::MinMax(Int::Limits::min, 10-1));

And them somehow the intersection of this.
But i was neither able to initialize a set with a Range, nor to combine
Ranges 
recursively.

So, how do i do this using the helping classes of gecode.

Best,
Max

_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users

_______________________________________________
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.gecode.org/pipermail/users/attachments/20120814/e57e3806/attachment.html>