Re: [eclipse-clp-users] How to expand domain of a variable

From: Sergey Dymchenko <kit1980_at_gmail.com>
Date: Sat, 5 Nov 2011 00:03:51 +0200
Thanks for reply!

The problem I'd want to solve:
There are intervals (many, millions), for example: [1..10], [20..30],
[15..17]. Intervals can overlap, include other intervals etc. Each
border of an interval can be from 1 to 4E9, right border is always
greater or equal to the left border. List of intervals is relative
static and should be constructed only at the start of the program (for
example, after loading from a config file), so it's OK if merging and
sorting of intervals take some time.

Then there are number of queries (also millions). A query is a number,
and the task is to say if that number belongs to any of the given
interval - the task is just to say Yes or No. An answer to a query
must be fast (definitely faster than just checking all intervals one
by one).

Can this problem be solved effectively in ECLiPSe, or it doesn't look
as a good problem for CLP paradigm?

Sergey.

On Fri, Nov 4, 2011 at 11:45 AM, Marco Gavanelli
<marco.gavanelli_at_unife.it> wrote:
> On 04/11/11 01:38, Sergey Dymchenko wrote:
>> Hello!
>>
>> How to expand existing domain of a variable?
>> I mean, I have a variable with some domain (say, 1..10), and I want to
>> allow that variable to have values from that domain or from another
>> domain, like 20..30.
>>
>> I tried things like
>> N :: [1..10], get_domain(N, D), N :: D or N :: [20..30].
>> but unsurprisingly it doesn't work.
>>
>> Of course I can write just
>> N :: [1..10] or N :: [20..30].
>> but I want to add ranges to domain iteratively (in a cycle).
>>
>> Sergey.
>
> Hi,
>
> usually if you want to expand the domains of the variables it means that
> you model is not a CLP(FD) model, because in CLP(FD) domains can only
> shrink.
>
> For this reason, ECLiPSe does not allow you to add elements to a domain,
> as you also noticed.
>
> Said that, there are some cases in which the domain of a variable
> semantically contains a lot of elements, but you do not know them all
> (currently), and you need to add them dynamically during search. This
> may happen for example in configuration problems (see papers by
> Mailharro) or in visual search problems.
>
> If you are interested, these are some papers on the topic:
>
> Marco Gavanelli, Evelina Lamma, Paola Mello, and Michela Milano. Dealing
> with incomplete knowledge on CLP(FD) variable domains. ACM Transactions
> on Programming Languages and Systems, 27(2):236-263, March 2005.
> http://dl.acm.org/citation.cfm?doid=1057387.1057389
>
> Marco Alberti, Marco Gavanelli, Evelina Lamma, Paola Mello, and Michela
> Milano. A CHR-based implementation of known arc-consistency. Theory and
> Practice of Logic Programming, 5(4/5):419-440, July 2005.
> http://www.ing.unife.it/docenti/MarcoGavanelli/papers/TPLP-CHR-2005.pdf
>
> Rita Cucchiara, Marco Gavanelli, Evelina Lamma, Paola Mello, Michela
> Milano, and Massimo Piccardi. Constraint propagation and value
> acquisition: why we should do it interactively. In Thomas Dean, editor,
> Proceedings of the Sixteenth International Joint Conference on
> Artificial Intelligence, pages 468-477, Stockholm, Sweden, July 31 -
> August 6 1999.
> http://ijcai.org/Past%20Proceedings/IJCAI-99-VOL-1/PDF/068.pdf
>
> Cheers,
> Marco
> --
> Marco Gavanelli, Ph.D. in Computer Science
> Dept of Engineering
> University of Ferrara
> Tel/Fax  +39-0532-97-4833
> http://www.ing.unife.it/docenti/MarcoGavanelli/
>
> ------------------------------------------------------------------------------
> RSA(R) Conference 2012
> Save $700 by Nov 18
> Register now
> http://p.sf.net/sfu/rsa-sfdev2dev1
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
>
Received on Fri Nov 04 2011 - 22:03:58 CET

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET