Dear George,
The clarification helped. I thought a bit about the problem this
morning, and I found a few extra tricks that allowed me to write a
decent solver for the problem. The program is attached. It is provided
without guarantee, so take some time to check that I have not made any
mistake...
George Rudolph wrote:
Fortunately, there is a shortcut due to the structure of cyclic sets. Cyclic
means that you can add the same number n, to all elements in a block, and the
resulting block is also a member of the design. {0,1,46} + {5,5,5} =
{5,6,51}. All arithmetic is done mod |V| (in this case 93).
This allows us to partition a design into groups of 92 subsets, where each
element in a partition belongs to the same cycle. We can generate the entire
set by choosing one block from each subset and list those.
In this case, we only need 23 blocks instead of 2,196.
(...)
We can pick any block from each partition, but the ones that begin with 0 are
convenient.
If we "normalize" the blocks such that 0 is the first element in the
block, then we search for blocks of the form {0,X,Y} where 0<X<Y. The
ordering between X and Y disambiguates the representation without any
loss of generality.
I found out that we can better constrain X and Y. Let us enforce the
convention that 0 and X are the closest points in {0,X,Y}. This implies
0<X=<31 and 2*X=<Y=<93-X. (Drawing a circle with the points helps!)
But we can even go further: X cannot be 31, because in that case 31
would be paired at least 3 times with 0, which is excluded by the 3rd
condition of the problem.
Therefore we can constrain X and Y with
0 < X < 31 and 2*X =< Y < 93-X.
There is another property of cyclic designs that is useful. If you take a
block like {0,20,27}, and compute the differences between elements, you get
the 6 elements paired with 0 in the cycle to which it belongs. 0-20 = -20 =
63, 0-27 = -27 = 56, 20-27 = -7 = 86, and the others are 20, 27 and 7. If you
compute all 6 differences for all 23 blocks, you have all 138 elements paired
with 0 in the design. If these pairs obey the desired constraints, the rest
of the design is guaranteed to follow.
So again, it seems the previous question becomes important, but applied in a
different context:
How to count the differences thus generated by the 23 blocks?
My proposal is to represent those differences as variables of the
problem. For each block {0,X,Y} we consider the values
X, Y, Y-X, 93-X, 93-Y, 93-Y+X.
Those values are constrained variables of the problem. All those
variables are in the list Diffs in my attached proposal.
We then use a specific propagator to say that 1 appears Count.1 times in
Diffs. Count is a tuple which tells how many times each element appears
in Diffs. The constraint is given by procedure Exactly, which has the
same semantics as FD.exactly. I discovered that FD.exactly has a bug,
hence the hand-made propagator.
Every element of Count is either 1 (paired once) or 2 (paired twice).
We then constrain Count with Exactly to enforce that 46 counters are
equal to 2. This implements the 3rd condition of the problem.
The solver is not very efficient (partly because I reimplemented
FD.exactly in a less efficient way), but you have something to play
with. So, enjoy!
Cheers,
raph
% Here is the problem, as stated by George Rudolph:
%
% I have a set V of 93 elements, labeled 0...92. A "point" is one of
% the elements of V. From V, I can draw elements to create 3-element
% subsets of V, such as {0,1,23} or {27,8,55}, and numbers car repeat
% as many times as desired. Each of these subsets is called a "block",
% and a list of blocks that meet some set of specified constraints is
% called a "design".
%
% For this particular design, I want 2,196 blocks with the following
% constraints.
% 1. All blocks must be distinct, no two can be equal or
% equivalent. Blocks are unordered sets, so any two permutations of
% the same set are equivalent.
% 2. Each element of V (point) must occur in 69 (different) blocks.
% 3. Each element of V must be paired with each of the other 92
% elements of V in at least one block, but 46 of those pairings must
% be repeated in other blocks. (69x2=138, and 138-92=46). Hence, each
% element of V is paired with 46 other elements once, and 46 others
% twice, in the design.
%
% Fortunately, there is a shortcut due to the structure of cyclic
% sets. Cyclic means that you can add the same number n, to all
% elements in a block, and the resulting block is also a member of the
% design. {0,1,46} + {5,5,5} = {5,6,51}. All arithmetic is done mod
% |V| (in this case 93). This allows us to partition a design into
% groups of 92 subsets, where each element in a partition belongs to
% the same cycle. We can generate the entire set by choosing one block
% from each subset and list those. In this case, we only need 23
% blocks instead of 2,196.
%
% We can pick any block from each partition, but the ones that begin
% with 0 are convenient. Therefore in our model we only consider
% blocks of the form
%
% {0,X,Y} where 0 < X < Y.
%
% There is another property of cyclic designs that is useful. If you
% take a block like {0,20,27}, and compute the differences between
% elements, you get the 6 elements paired with 0 in the cycle to which
% it belongs. 0-20 = -20 = 63, 0-27 = -27 = 56, 20-27 = -7 = 86, and
% the others are 20, 27 and 7. If you compute all 6 differences for
% all 23 blocks, you have all 138 elements paired with 0 in the
% design. If these pairs obey the desired constraints, the rest of the
% design is guaranteed to follow.
%
% If we take the block {0,X,Y} above, the 6 elements paired with are
% given by X, Y, Y-X, 93-X, 93-Y, and 93+X-Y.
%
% Here are a few extra constraints that would break cycle symmetries
% in the solutions. First, we can always normalize the block such
% that 0 and X are the closest points. This implies that the distance
% between the pairs (X,Y) and (Y,0) must be smaller or equal to X.
% Second, we can exclude the block {0,31,62} because with this block 0
% would be paired at least three times with 31. This constrain the
% domain of X in the interval 1#30. We thus have
%
% 0 < X < 31 and 2*X =< Y < 93-X.
declare
proc {Concat Ls ?R}
case Ls of L|Lr then R1 in
R={Append L R1} R1={Concat Lr}
else R=nil end
end
proc {Exactly D Dv I}
Ds = if {List.is Dv} then Dv else {Record.toList Dv} end
Bs = {Map Ds fun {$ E} E =: I end}
in
{FD.sum Bs '=:' D}
end
proc {Design Blocks}
Diffs Count
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 = {FD.tuple paired 92 1#2}
for I in 1..92 do
{Exactly Count.I Diffs I} % Count.I elements of Diffs are I
end
{Exactly 46 Count 2} % 46 elements appear twice
%% distributed on the variables in Blocks
{FD.distribute ff {Concat Blocks}}
end
{ExploreOne Design}
_________________________________________________________________________________
mozart-users mailing list
mozart-users@ps.uni-sb.de
http://www.mozart-oz.org/mailman/listinfo/mozart-users
