Re: [eclipse-clp-users] Symmetry

From: Bogdan Tanasa <g-bogta_at_ida.liu.se>
Date: Thu, 26 Jan 2012 20:29:33 +0100
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.

Bogdna.

-----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/
Received on Thu Jan 26 2012 - 19:29:42 CET

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET