From: Marco Gavanelli <marco.gavanelli_at_unife.it>

Date: Thu, 26 Jan 2012 22:13:58 +0100

Date: Thu, 26 Jan 2012 22:13:58 +0100

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_unife.it] > 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_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 - 21:14:10 CET

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