[gecode-users] LDSB : symmetries on value tuples and depending symmetries

[Martin Mann]

Dear Chris,

thanks for your answer. Think the solution you provided wont do the 
trick due to the following reason: say I have X=(x1,x2) where x1.x2 are 
somehow specially dependent (also via constraints). So a symmetric 
assignment of x1 directly defines an assignment of x2 and vice versa. It 
is thus no simple value symmetry that can be independently applied to 
any variable. I guess constraint propagation would ensure the symmetry 
propagation from one to the other, but not sure if it does not actually 
make the solver loose solutions.

But I built a workaround via branch and wait statements and special 
checks. As soon as this is running smooth I will give LDSB a second try. 
Furthermore, I have some fixed order constraints on X that break some 
symmetries. Will have to check how this influences the LDSB results.

So long,
Martin


Am 26.04.2013 03:00, schrieb Chris Mears:
> On Tue, 23 Apr 2013 10:55:08 +0200
> Martin Mann <mmann at informatik.uni-freiburg.de> wrote:
>
>> I have a symmetry function "s" that can generate for each solution
>> "a" the set of symmetric assignments on X1 and on X2 (independently).
>> The problem is defined in a way that all symmetries from X1 are
>> theoretically combineable with symmetric assignments on X2.
>>
>> Thus I would like to do something like that:
>>
>> - for each assignment a1 on X1
>>    + find assignment a2 on X2
>>    + ensure during remaining search implication
>>      if(a1) --> [X2 not s(a2)] for all symmetries of a2
>>    + ensure during remaining search
>>      [X1 not s(a1)] for all symmetries of a1
>>    + continue search
>
> Hi Martin,
>
> I'm not sure I understand exactly what you are trying to do.  Say you
> have a model like this:
>
> class TwoPhase : public Script {
> protected:
>    IntVarArray x;
>    IntVarArray y;
> public:
>    TwoPhase(const Options&)
>      : x(*this,2,1,2), y(*this,3,1,3) {
>
>      Symmetries sx;
>      sx << ValueSymmetry(IntArgs(2,1,2));
>
>      Symmetries sy;
>      sy << ValueSymmetry(IntArgs(3,1,2,3));
>
>      branch(*this, x, INT_VAR_NONE(), INT_VAL_MIN(), sx);
>      branch(*this, y, INT_VAR_NONE(), INT_VAL_MIN(), sy);
>    }
>    // ...
> }
>
> You would get these solutions:
>
> x: 1 1	y: 1 1 1
> x: 1 1	y: 1 1 2
> x: 1 1	y: 1 2 1
> x: 1 1	y: 1 2 2
> x: 1 1	y: 1 2 3
> x: 1 2	y: 1 1 1
> x: 1 2	y: 1 1 2
> x: 1 2	y: 1 2 1
> x: 1 2	y: 1 2 2
> x: 1 2	y: 1 2 3
>
> i.e. the symmetry is broken within the "x" and "y" independently.  If
> this is not what you are looking for, could you please explain a bit
> more?
>
> Cheers,
> Chris
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>

-- 
Dr. Martin Mann, Postdoc
Bioinformatics - Inst. of Computer Science
Albert-Ludwigs-University Freiburg
Tel: ++49-761-203-8254
Fax: ++49-761-203-7462
http://www.bioinf.uni-freiburg.de/~mmann/