Oz and Mozart Users Mailing List

RE: Finite Set Constraint Question

From: Nathan Barnett (nathan@nrbservices.com)
Date: Thu Nov 13 2003 - 20:51:32 CET

Next message: Nathan Barnett: "RE: Finite Set Constraint Question"
Previous message: Nathan Barnett: "RE: Finite Set Constraint Question"
In reply to: Raphael Collet: "Re: Finite Set Constraint Question"
Next in thread: Nathan Barnett: "RE: Finite Set Constraint Question"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Mail actions: [ respond to this message ] [ mail a new topic ]

Raph,

Thanks, what I ended up using was your 2nd solution even though I am still
using Finite Sets as the problem is more complex overall than what I sent to
the list. But I turn that particular set into a 7 element finite domain
list by setting the finite domain list equal to the FS.int.match of the set
and it works perfectly and very efficiently.

Thanks,
Nathan

-----Original Message-----
From: owner-oz-users@ps.uni-sb.de [mailto:owner-oz-users@ps.uni-sb.de] On
Behalf Of Raphael Collet
Sent: Thursday, November 13, 2003 4:05 AM
To: users@mozart-oz.org
Subject: Re: Finite Set Constraint Question

Nathan Barnett wrote:

> I have been working on some finite set problems to build my skills
> with Mozart and I had a problem that I ran into that I wasn't sure how
> to solve.
>
> I have a Finite Set with cardinality of 7 that I am working with.
> Each element in the set is restricted to 0#1000. How can I apply a
> constraint that guarantees that at least 3 of the elements in the set
> when modded with 100 have the same result. So an example good set
> would be [13 213 413 786 999 321 100] since 13 213 and 413 when modded
> by 100 have the same value.

Here is my first idea: use reification to count the number of elements that
are equal to K mod 100, for each K. Then check which satisfy the constraint
(at least 3 in the set), then ensure that at least one of those sets
satisfies the constraint.

The first program in attachment gives you the code of the propagator, and a
small script that solves your problem. But this is terribly inefficient!
Your constraint does not prune very much the search, and I'm not sure at all
my implementation is optimal. And the distribution strategy is too naive.

Actually, if the cardinality is fixed, you should probably code it as a list
of FD integers. The model is pretty simple: impose the first three elements
to have the same remainder modulo 100. The second file in attachment gives
you a solver for this. This one is efficient.

raph

-
Please send submissions to users@mozart-oz.org
and administriva mail to users-request@mozart-oz.org.
The Mozart Oz web site is at http://www.mozart-oz.org/.
Please send bug reports to bugs@mozart-oz.org.

Next message: Nathan Barnett: "RE: Finite Set Constraint Question"
Previous message: Nathan Barnett: "RE: Finite Set Constraint Question"
In reply to: Raphael Collet: "Re: Finite Set Constraint Question"
Next in thread: Nathan Barnett: "RE: Finite Set Constraint Question"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Mail actions: [ respond to this message ] [ mail a new topic ]

This archive was generated by hypermail 2b29.