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_unife.it]
> 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_unife.it]
>> 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/