struggling with syntax and semantics, need help with code
George Rudolph
rudolphg1 at citadel.edu
Wed Jan 24 22:33:09 CET 2007
Note: This post includes information that may have been lost to the mailing
list
due to recent problems. I apologize that it is so long, but Raph and I
thought
that others will find the information useful.
1. I knew there were bugs, which is why I asked for help. ;) Some of them
were cut-and-paste typos that I thought I had fixed (famous last words,
right?) Others were simply mistakes.
2. Clearly, though, I have problems understanding the difference between "="
and"=:", and "==" and ":=". I still am not clear when one or the other, in
each respective case, is required, and what the semantics are.
3. In some iteration of writing that code, I tried using the Mod or ModI
operator in just that way, and it didn't seem to work--probably that was
because of other problems with the script, though. But I eliminated that
possibility by writing what I thought was equivalent code for it.
What do you mean that the condition Z <: 93 is not a boolean condition?
What type is returned by that expression?
4. Re: (X-Y) mod 93 appears once, etc...
Yes, you are correct in that statement. I hadn't quite seen that property
that way--the existing literature maps the counts and differences into
vectors and matrices, rather than referring back to the original list of
differences--but that is correct.
5. You can see that the sets D and E partition the list Diffs.
I was looking for a way to reify and count the number of intersections,
similar to what was done for Count in the Exactly procedure.
I couldn't quite figure out how to do it though, even though I knew what
I wanted to do. Thanks!
6. I like this following fragment. In the code I posted, I knew I didn't
really want those conditionals, I wanted a uniform constraint--but
I couldn't figure out how to state it. Here, you did it!
%% The number of X such that Intersect0Y.X==1 is equal to
%% Count.Y+21 (22 if Y in D, 23 if Y in E).
{FD.sum Intersect0Y '=:' {FD.plus 21 Count.Y}}
7. Clearly, this new constraint on the pairs is what makes the problem both
combinatorial, and potentially intractable for large V (i.e. V = 93).
Apparently even when we can reduce it to looking at pairs {0,Y}, as opposed
to all pairs {X,Y}.
However, consider this: It should now be relatively easy to constrain the
search space further by asking for solutions that contain specific blocks,
or (sub)sets of blocks, or to further constrain values of X and/or Y.
Correct?
That would yield one or more valid solutions in a smaller search space, not
enumerating every possible solution, but finding some, if they exist.
And therefore getting a further glimpse into the structure of the solution
space.
This is, I think, one of the strengths of a CLP approach as opposed to other
methods such as Combinatorial Optimization algorithms: The ability to add
(or remove) recognizable constraints to tune the solver.
8. I knew that the algorithm I posted was "heavy", as you say, I was focused
on trying to put together something that would work correctly, and then
strive to make it more efficient. I have been trying to learn the language
of constraints in Oz, as well as discover hidden structures and properties
in this class of design problems, on top of developing an executable
specification of this particular problem (where V=93). I plan to generalize
the code to work with any V that fits the more general design problem, much
like the Steiner Triple solver will work with any N that meets the basic
constraints on N--but I want to do that only after the code works for the
current case.
> From Raph:
> There are a few bugs in the code you shipped. I will point out where
> they are, so that you can understand why your script did not work.
> But I will also give an alternative way to encode the balancing
constraints.
> See below.
>
>
> Here we go:
>
> > for Y in 1..92 do
> > DiffsY
> > CountY
> > Intersect0Y
> > in
> > DiffsY = {Map Diffs fun {$ Diff}
> > Z = {FD.plus Diff Y}
> > in
> > if Z <: 93 then Z
> > else {FD.minus Z 93}
> > end
> > end
> > }
>
> Boom! Your script never goes beyond this. Why? Because Z is a
> constrained variable, and Z<:93 returns an *undetermined* binary
> variable. So the "if" blocks forever. Actually the condition is even
> the wrong type (not a boolean)!
>
> A simple solution is to use the propagator FD.modI (or FD.modD) for
> computing the modulo:
>
> DiffsY = {Map Diffs fun {$ Diff}
> {FD.modI {FD.plus Diff Y} 93}
> end}
>
> > CountY = {FD.tuple pairedY 92 1#2}
> > for I in 1..92 do
> > {Exactly CountY Diffs I} % CountY.I elements of DiffsY are I
> > end
>
> Thanks for documenting this line! It contains two errors: CountY
> should be CountY.I, and Diffs should be DiffsY:
>
> {Exactly CountY.I DiffsY I} % CountY.I elements of DiffsY are I
>
> > Intersect0Y = {FD.tuple pairedI 92 0#1}
> > for I in 1..92 do
> > Intersect0Y.I =: (Count.I == 1) && (Count.Y == 1)
> > end
>
> Yet another one! The comparators == will block, and return the wrong
> type. You have to use =: instead. And '&&' is C, not Oz. As we are
> combining binary integers, we should multiply the reified conditions.
> Moreover, the second one should be CountY.I =: 1 (otherwise CountY is
> useless).
>
> Intersect0Y.I =: (Count.I =: 1) * (CountY.I =: 1)
>
> > if Count.Y == 1 then
> > {Exactly 22 Intersect0Y 1}
> > else
> > {Exactly 23 Intersect0Y 1}
> > end
>
> Again here, Count.Y == 1 blocks forever. All those blocking
> statements prevent the distributor (FD.distribute) from determining
> variables. So the solver is stuck.
>
> Before you rush at making all the fixes, let us analyze a bit your
> script. The original script has around 200 variables. The list Diffs
> contains 23*6 = 138 variables, and Count has 92 variables. Your extra
> constraints create 92 lists DiffsY, each having 138 variable, and 92
> tuples Intersect0Y, each with 92 variable. That is about 21160
> variable, and about the same number of propagators! This is WAY too
> much. I tried to run the program, and it quickly starts to eat all my
> computer's memory.
>
> You can reformulate the definitions of the sets D, E, and F without
> creating so many variables. Let X and Y be elements in 1..92.
>
> - X is in D if it appears once with 0, i.e., Count.X == 1. It is in
> E if Count.X == 2. Those two are easy to reify without excessive cost.
>
> - X is in F if it appears once with Y. You encode is as: X appears
> once in DiffsY, where DiffsY is obtained by adding Y mod 93 to all
> elements of Diffs. The condition is in fact equivalent to:
>
> X-Y (normalized modulo 93) appears once in Diffs.
>
> Can you see the magic? Both X and Y are determined (they are loop
> variables), so no extra variable needs to be created.
>
> I have rewritten the program with these modifications. The script is
> still heavier that the original, because it creates 92 tuples
> Intersect0Y, but this is definitively less than before. Moreover,
> counting the number of 1 in Intersect0Y is equivalent to summing the
> vector (the other elements are 0).
>
>
>
> I have not been able to find a solution with this, yet. This is
> because the search tree is huge: its depth goes beyond 200! And I did
> not let it run more that a minute or so. But at least it works
> better. Note that in the program, I changed the options of the
> Explorer to use recomputation (this uses much less memory).
>
> Happy exploration,
>
> Cheers,
> raph
------------------- original code that is referred to above -------------
declare
% Recursively flatten the list Ls one level, and return the result in R.
proc {Concat Ls ?R}
case Ls of L|Lr then R1 in
R={Append L R1} R1={Concat Lr}
else R=nil end
end
% Exactly D elements of Dv have the value I.
% This is a rewrite of the built-in function FD.exactly,
% which has a bug in version 1.2.3.
% This is used to enforce the constraint that half the differences appear
once and
% half appear twice, by counting differences that appear twice.
proc {Exactly D Dv TargetValue}
Ds = if {List.is Dv}
then Dv
else {Record.toList Dv} end
Bs = {Map Ds fun {$ E} E =: TargetValue end}
in
{FD.sum Bs '=:' D}
end
%
%
%
proc {Design Blocks}
Diffs
Count
%% BlockIds is a list of 23 integers in the interval 1..92^2
BlockIds = {FD.list 23 1#(92*92)}
in
%% Blocks is a list of 23 "normalized" blocks
Blocks = {MakeList 23}
for B in Blocks Id in BlockIds do X Y in
[X Y] ::: 1#92
X <: 31
2 * X =<: Y
Y <: 93 - X
B = [0 X Y]
Id =: X * 93 + Y
end
%% all blocks are pairwise distinct; we order them by Id in order
%% to break more symmetries
for Id1 in BlockIds Id2 in BlockIds.2 do
Id1 <: Id2
end
%% Diffs is the list of all elements paired with 0
Diffs = {Concat {Map Blocks
fun {$ [0 X Y]}
L=[X Y {FD.minus Y X}]
in
{Append L {Map L fun {$ E} {FD.minus 93 E} end}}
end}}
%% Count is a list of 92 integers in the interval 0..2
Count = {FD.tuple paired 92 1#2}
for I in 1..92 do
{Exactly Count.I Diffs I} % Count.I elements of Diffs have the value I
end
{Exactly 46 Count 2} % 46 elements appear twice with 0 in the design
{Exactly 46 Count 1} % 46 elements appear once with 0 in the design
%
% I need help with the code below.
% when I add it in, the solution becomes indeterminate (light green
% diamond).What have I done wrong?
%
%% Now we balance pairs {0,Y}in the design,
%% further constraining the blocks that are accepted.
%% If all pairs {0,Y} are balanced, then all pairs {X,Y} in the design
%% are guaranteed to be balanced.
%% To balance the pairs in the design, I need to compute the set of points
%% that appear twice with 0, (call it E),
%% the set of points that appear once with 0 (call it D),
%% and for each Y, the set of points that appear once with that Y (call it
F).
%% We can calculate the set of points that appear once with a given Y
%% by adding Y (mod 93) to each element that appears once with 0.
%% The constraint is as follows:
%% for all elements in E, the cardinality of D intersect F is 23.
%% for all elements in D, the cardinality of D intersect F is 22.
for Y in 1..92 do
DiffsY
CountY
Intersect0Y
in
DiffsY = {Map Diffs fun {$ Diff}
Z = {FD.plus Diff Y}
in
if Z <: 93 then Z
else {FD.minus Z 93}
end
end
}
CountY = {FD.tuple pairedY 92 1#2}
for I in 1..92 do
{Exactly CountY Diffs I} % CountY.I elements of DiffsY are I
end
Intersect0Y = {FD.tuple pairedI 92 0#1}
for I in 1..92 do
Intersect0Y.I =: (Count.I == 1) && (Count.Y == 1)
end
if Count.Y == 1 then
{Exactly 22 Intersect0Y 1}
else
{Exactly 23 Intersect0Y 1}
end
end
% end of "balancing pairs" {0,Y} constraints
%% distributed on the variables in Blocks
{FD.distribute ff {Concat Blocks}}
end
{ExploreOne Design}
------------------ end of original code ---------------
-------------------modified code (written by Raph)-----
%% this is the section of code rewritten by Raph as described above
%% replace everything AFTER the line "{Exactly 46 Count 1} % 46 elements
appear once with 0 in the design"
%% in the original code with the code below.
%% Now we balance pairs {0,Y}in the design, further constraining
%% the blocks that are accepted. If all pairs {0,Y} are balanced,
%% then all pairs {X,Y} in the design are guaranteed to be
%% balanced.
%%
%% To balance the pairs in the design, I need to compute the set of
%% points that appear twice with 0, (call it E), the set of points
%% that appear once with 0 (call it D), and for each Y, the set of
%% points that appear once with that Y (call it F). We can
%% calculate the set of points that appear once with a given Y by
%% adding Y (mod 93) to each element that appears once with 0.
%%
%% The constraint is as follows: for all elements in E, the
%% cardinality of D intersect F is 23. For all elements in D, the
%% cardinality of D intersect F is 22.
%%
%% raph: Element X is in D if Count.X==1, and in E if Count.X==2.
%% Moreover, X appears once with Y means that it appears twice in
%% the list Diffs where each element D is replaced by (D+Y) mod 93.
%% This is in fact equivalent to: (X-Y+93) mod 93 appears once in
%% Diffs. The latter formulation drastically reduces the number of
%% FD variables in the script!
for Y in 1..92 do
Intersect0Y = {FD.tuple pairedI 92 0#1}
in
for X in 1..92 do
if X\=Y then Z = (X-Y+93) mod 93 in
%% reifies: X appears once with 0 and once with Y
Intersect0Y.X =: (Count.X =: 1) * (Count.Z =: 1)
else
Intersect0Y.X = 0
end
end
%% The number of X such that Intersect0Y.X==1 is equal to
%% Count.Y+21 (22 if Y in D, 23 if Y in E).
{FD.sum Intersect0Y '=:' {FD.plus 21 Count.Y}}
end
%% end of "balancing pairs" {0,Y} constraints
%% distributed on the variables in Blocks
{FD.distribute ff {Concat Blocks}}
end
{Explorer.object option(search search:5 information:25 failed:true)}
{Explorer.object script(Design)}
-------------------end of modified code ---------------
--------------------
George Rudolph
Assistant Professor
Thompson Hall 225
Math & Computer Science Dept.
The Citadel
171 Moultrie St.
Charleston, SC 29414
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.gforge.info.ucl.ac.be/pipermail/mozart-users/attachments/20070124/dba01dbe/attachment-0001.html
More information about the mozart-users
mailing list