Re: [eclipse-clp-users] Symmetry

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

----------------------------------------------------------------------------
--
Keep Your Developer Skills Current with LearnDevNow!
The most comprehensive online learning library for Microsoft developers
is just $99.99! Visual Studio, SharePoint, SQL - plus HTML5, CSS3, MVC3,
Metro Style Apps, more. Free future releases when you subscribe now!
http://p.sf.net/sfu/learndevnow-d2d
_______________________________________________
ECLiPSe-CLP-Users mailing list
ECLiPSe-CLP-Users_at_lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
Received on Thu Jan 26 2012 - 16:30:00 CET

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