Re: [eclipse-clp-users] ECLiPSe - Real variables domain propagation problem

From: Kish Shen <kisshen_at_cisco.com>
Date: Thu, 23 Jul 2009 14:25:34 +0100
Wayne Mac Adams wrote:
> Or even just a simpler way to represent it is to just focus on the following
> query(assuming the ic librarby is loaded)
> 
> ?- A :: 0.0 .. 0.5, [B, C] :: 0.0 .. 1.0, A $= eval(B + C - B * C).
> A = A{0.0 .. 0.5}
> B = B{0.0 .. 1.0}
> C = C{0.0 .. 1.0}
> There are 4 delayed goals.
> Yes (0.00s cpu)
> 
> If i had
> ?- A :: 0.0 .. 0.5, [B, C] :: 0.0 .. 1.0, A $= eval(B + C).
> A = A{0.0 .. 0.5}
> B = B{0.0 .. 0.5}
> C = C{0.0 .. 0.5}
> There is 1 delayed goal.
> Yes (0.00s cpu)
> 
> it propagates correctly.
> 
> I have been told( by Helmut Simonis, and I hope I paraphrase this
> correctly!) it is because ECLiPSe treats B+C and B*C as seperate and not
> foesn't see the it as as the same terms being used.
> 
> Again any help is appreciated,
> Thanks,
> Wayne
> 
> On Wed, Jul 22, 2009 at 11:52 AM, Wayne Mac Adams
> <waynemacadams_at_gmail.com>wrote:
> 
>> Hi,
>> Hopefully someone can help me with my problem, I have been advised to send
>> an email to this mailing list.
>>
>>
>> I have the following predictate
>>
>> prob_sum([],Sum,Sum).
>> prob_sum([E | Tail], Sum,End):-
>>     prob_sum(Tail,Sum+E-Sum*E,End).
>>
>> It take a list of Variables and gets the probabilistic sum fo them.
>> Somewhere else the sum is then constrained to be less than or equal to some
>> other variable.
>> However when the list has more than one element the domains of the
>> variables in the list don't seem to propagate correctly.
>> For example consider this query
>>
>> N::0.0..0.5, NA::0.0..1.0, NC::0.0..1.0,
>> prob_sum([NA,NC],0,M),N1::0.0..1.0, eval(M) $=N1, N1 $=<N.
>>
>> It gives the result
>>
>> ?- N::0.0..0.5, NA::0.0..1.0, NC::0.0..1.0,
>> prob_sum([NA,NC],0,M),N1::0.0..1.0, eval(M) $=N1, N1 $=<N.
>> N = N{0.0 .. 0.5}
>> NA = NA{0.0 .. 1.0}
>> NC = NC{0.0 .. 1.0}
>> M = 0 + NA{0.0 .. 1.0} - 0 * NA + NC{0.0 .. 1.0} - (0 + NA - 0 * NA) * NC
>> N1 = N1{0.0 .. 0.5}
>> There are 5 delayed goals.
>> Yes (0.00s cpu)
>>
>> As you can see the domains for NA and NC remain from 0.0..1.0 when you
>> would think they should be 0.0..0.5.
>>
>> Does anyone know how to solve this problem?
>> It forms part of a larger problem in which I am getting an incorrect result
>> because of the domains staying between 0.0..1.0.
>>
>> Any help is appreciated,
>> Thanks,
>> Wayne
>>
> 
> 
> ------------------------------------------------------------------------
> 
> ------------------------------------------------------------------------------
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
Hi Wayne,

I am probably not the best person to answer your question, but as you 
have not heard from someone else yet...

As far as I know, ic does not have any special mechanisms for reasoning 
about the bounds on quadratic expressions, so there is really no 
built-in way that ECLiPSe can examine the linear and qudratic part of 
your expression together, so your quadratic sub-expression is simply 
treated like any non-linear component by ic -- it is extracted and 
replaced by a variable in the original expression, so that the original 
expression is kept linear. The non-linear parts are posted as seperate 
constraints.

ic does provide an interface for users to program their own constraints, 
and so if you know how to program the sort of bounds propagation for the 
expressions you have, you may be able to add your own constraints to 
deal with them.

Helmut (and I assume others at 4C) can probably give you much more 
information on reasoning about quadratic constraints than I can.

We welcome any contributions to ECLiPSe, so if you do decide to write 
your own constraints, and you think they may be generally applicable, 
we'd be very glad to add them to ECLiPSe!

Cheers,

Kish
-- 
This e-mail may contain confidential and privileged material for the
sole use of the intended recipient. Any review, use, distribution or
disclosure by others is strictly prohibited. If you are not the intended
recipient (or authorized to receive for the recipient), please contact
the sender by reply e-mail and delete all copies of this message.
Cisco Systems Limited (Company Number: 02558939), is registered in
England and Wales with its registered office at 1 Callaghan Square,
Cardiff, South Glamorgan CF10 5BT.
Received on Thu Jul 23 2009 - 13:25:38 CEST

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