Re: [eclipse-clp-users] Symmetry

On 26/01/12 21:46, Bogdan Tanasa wrote:
> Thanks,
>
> If the matrix has N columns this means that I have to add N-1 constraints of
> that type ?

Yes, correct.

Cheers,
Marco

> -----Original Message-----
> From: Marco Gavanelli [mailto:marco.gavanelli_at_...17...]
> Sent: 26 ianuarie 2012 21:28
> To: eclipse-clp-users_at_lists.sourceforge.net
> Subject: Re: [eclipse-clp-users] Symmetry
>
> Hi,
>
> On 26/01/12 20:29, Bogdan Tanasa wrote:
>> Hi,
>>
>> I don't see how that constraint is helping.
>> I can have a solution (the optimal one) of the form
>>    1 0
>>    0 1
>>    1 0
>>    0 1
>>
>> Putting that constraint on the columns of the matrix X will prevent
>> obtaining this kind of solutions.
>
> Indeed, but you will still get the symmetrical solution
>
> 	0 1
> 	1 0
> 	0 1
> 	1 0
>
> that, according to what you said, has exactly the same cost.
>
> If your program does not return that solution, this means that it was
> actually not a symmetry: by definition if you have a column symmetry and
> you swap two columns from a solution, you always get another solution.
>
> Adding a symmetry breaking constraint (such as lex_le) is usually the
> simplest and most efficient way to remove symmetries. But there are
> other methods, that can be useful when symmetry breaking constraints are
> not applicable: you can have a look at the ic_sbds library.
>
> Cheers,
> Marco
>
>> -----Original Message-----
>> From: Marco Gavanelli [mailto:marco.gavanelli_at_...17...]
>> Sent: 26 ianuarie 2012 17:58
>> To: Bogdan Tanasa
>> Cc: eclipse-clp-users_at_lists.sourceforge.net
>> Subject: Re: [eclipse-clp-users] Symmetry
>>
>> Hi,
>>
>> in this case, you can impose the constraint lex_le on every two
>> consecutive columns of the matrix.
>>
>> Cheers,
>> Marco
>>
>> On 26/01/12 17:29, Bogdan Tanasa wrote:
>>> Hi,
>>>
>>> A solution is an instantiation of that matrix.
>>> Any permutation of the columns of that matrix represents the same
>> solution.
>>>
>>> How can I avoid this situation in CLP?
>>>
>>> Thanks,
>>> Bogdan.
>>>
>>> -----Original Message-----
>>> From: Marco Gavanelli [mailto:marco.gavanelli_at_...17...]
>>> Sent: 26 ianuarie 2012 16:13
>>> To: eclipse-clp-users_at_lists.sourceforge.net
>>> Subject: Re: [eclipse-clp-users] Symmetry
>>>
>>> On 26/01/12 15:09, Bogdan Tanasa wrote:
>>>> I have a problem for which the boolean optimization variables are of the
>>>> following form (a matrix):
>>>>
>>>>
>>>>
>>>> x_11, x_12, .., x_1n
>>>>
>>>> x_21, x_22, .., x_2n
>>>>
>>>> .
>>>>
>>>> x_n1, x_n2, .., x_nn
>>>>
>>>>
>>>>
>>>> In my case a solution of the form
>>>>
>>>> 0 1 0 1
>>>>
>>>> 0 0 0 1
>>>>
>>>> 0 1 0 1
>>>>
>>>> Is identical with
>>>>
>>>> 1 0 1 0
>>>>
>>>> 0 0 1 0
>>>>
>>>> 1 0 1 0
>>>>
>>>>>      From the cost function point of view.
>>>>
>>>>
>>>>
>>>> Can you please tell me how to ignore exploring the symmetrical solutions
>>> of
>>>> this form ?
>>>
>>> To avoid this symmetry (this very symmetry), you can add the constraint:
>>>
>>> X_11 #\= 0 or X_12 #\= 1 or X_13 #\= 0 or X_14 #\= 1 or
>>> X_21 #\= 0 or X_22 #\= 0 or X_23 #\= 0 or X_24 #\= 1 or
>>> X_31 #\= 0 or X_32 #\= 1 or X_33 #\= 0 or X_34 #\= 1
>>>
>>> If you want something more general, you might want to explain in more
>>> detail why these two solutions are symmetric in your problem.
>>>
>>> Best,
>>> Marco


-- 
Marco Gavanelli, Ph.D. in Computer Science
Dept of Engineering
University of Ferrara
Tel/Fax  +39-0532-97-4833
http://www.ing.unife.it/docenti/MarcoGavanelli/