# Symmetry in Integer Programming

 2 Hello everybody I have a question regarding the symmetry group defined in the paper written by Francois Margot in the book of “50 years of integer programming 1958-2008”. In fact the definition of a symmetric group is clear. The definition of symmetry group in this paper is as following: Assume that Q is the set of all feasible solution of an integer linear programming (ILP). Then the symmetry group G of ILP is the set of all permutations of the variables mapping Q on itself and mapping each feasible solution on a feasible solution having the same value. The problem is here! In my ILP, the set of different feasible solutions with the same value does not define a group since it is not close under the operations defined on permutation groups! More precisely, there exists a permutation which maps a feasible solution on another one with the same value while it maps another feasible solution with the same value to a feasible solution with a different value. Any comment is highly appreciated. asked 12 Jun '12, 11:48 Monemi 21●1●4 accept rate: 0% I add a small instance of my problem to shed more light on the question: \begin{aligned} \max \quad & x_{12} + x_{21} + x_{23} + x_{32} + 3 \cdot x_{13} + x_{31} \\ s.t. \quad & x_{12} + x_{23} + x_{31} \le 2\\ & x_{21} + x_{13} + x_{32} \le 2\\ & x_{ij} \in \{0,1\} \end{aligned} The set of feasible solution contains 6 elements: $a = (1,0,1,0,1,0) \\ b = (1,0,0,1,1,0) \\ c = (0,1,1,0,1,0) \\ d = (0,1,1,0,0,1) \\ e = (1,0,0,1,0,1) \\ f = (0,1,0,1,0,1)$ a, b and c are having the same objective value equal to 5 and d, e and f also defining a set of feasible solution with the same value equal to 3. So we need the permutations as following: $$p1 = (1,2)$$ (to find c from a) $$p2 = (3,4)$$ (to find b from a) $$p1.p2 = (1,2).(3,4)$$ (is enough to find b from c) However p1 and p2 map d, e and f on some infeasible solutions. Also p1 maps b on an infeasible solution (0,1,0,1,1,0). Does it mean there is no symmetry group to define here even if there is a high degree of symmetry inherently in th eproblem? Any explanation is highly appreciated (13 Jun '12, 05:47) Monemi Sorry I forgot to add the following constraints to my model: $x_{12} + x_{21} = 1\\ x_{23} + x_{32} = 1\\ x_{13} + x_{31} = 1$ Now, the set of all feasible solutions contains exactly 6 elements a, b, c, d, e and f. (13 Jun '12, 08:45) Monemi

 4 The permutation you describe wouldn't be a member of the symmetry group of the problem. The definition says that for a permutation to be a member of the group it must map each feasible solution on a feasible solution having the same value. answered 12 Jun '12, 13:38 Jeff Linderoth 441●2 accept rate: 40% Thanks for your comment. Well the definition is right like that. If I am not mistaking, it means that we may have symmetry in our problem but no possibility to find a symmetry group on the set of feasible solutions! (13 Jun '12, 05:45) Monemi
 3 Margot's definition has a hidden issue. Assume that Q is the set of all feasible solution of an integer linear programming (ILP). Then the symmetry group G of ILP is the set of all permutations of the variables mapping Q on itself and mapping each feasible solution on a feasible solution having the same value. If you have an infeasible model, then ANY permuation would be a symmetry. This has been debatted in the constraint programming community a lot, and no clear conclusion could be found on how to fix that. It is much safer to define a symmetry as a permutation of rows and columns that leaves the matrix unchanged IMHO. It has a drawback too, some symmetry will be missed because of the particular way constraints are expressed. With this syntactic definition, the symmetry gorup of your example be generated by (x_12 x_23) (x_23 x_31) (x_21 x_32) (x_32 x_13) (x_12 x_21)(x_23 x_13)(x_31 x_32) i.e. the variables appearing in the first constraint can be freely permuted, and the variables appearing on the second constraint can be freely permuted, and the two constraints can be permuted If we take into account the objective, then two feasible solutions having different objective values aren't symmetric. in this case x_13 cannot be permuted with any other variable. The generators become (x_12 x_23) (x_23 x_31) (x_21 x_32) Looking at the set of feasible solutions, you're missing many of them. For instance, (0 0 0 0 0 0) is feasible. answered 13 Jun '12, 06:52 jfpuget 2.5k●3●10 accept rate: 8% Thank you for the comment. I need to mention that in my problem, the set of feasible solutions is never empty. Actually I do not understand exactly what has been changed in your definition. Following your way as you mentioned, (x_12, x_23) is one of the generators of our symmetry group. Then there is the same problem appearing here: Applying this permutation will map b on an infeasible solution (0,0,1,1,1,0) and c on another infeasible solution (1,1,0,0,1,0), and the same will happen for d and e. (13 Jun '12, 07:55) Monemi I can't add comments (yet) hence I'll add an answer As said, you do not list all feasible solutions in your example. Start by lisitng all of them before looking for symmetry. (13 Jun '12, 12:32) jfpuget Hi Jean-Francois. Thank you for your insight. I didn't know there was a big controversy surrounding the question "what are the symmetries of the empty set?" (Very zen -- It's like "What is the sound of one hand clapping?") Is there a place you can point us to learn about the difficulties that arise when one assumes that the empty set has a symmetry group that is the complete symmetric group? One problem with using the symmetry group of the matrix (or something similar) as you suggest is that it is less clear what to do in case the problem is not linear. (13 Jun '12, 13:06) Jeff Linderoth 1 Jeff, I may have exaggerated a little bit. The issue in constraint programming came from an even wider definition of symmetry, where permutation of values was also allowed. Then variable/value pairs that appeared in no solution lead to what I would call "artificial" symmetry. Here are papers about it http://www.comp.leeds.ac.uk/bms/Talks/SymDefnsCP05.ppt http://www.informatik.uni-freiburg.de/~ki/teaching/ss11/readinggroup/private/cohen-et-al-constraints2006.pdf http://www.comp.leeds.ac.uk/bms/Papers/AAAI06.pdf (13 Jun '12, 20:20) jfpuget 1 Regarding the detection of syntactic symmetry from a larger class of problem than LP or MIP, there has been work in the CP community that may be relevant, starting with a paper of mine ftp://ftp.db.toronto.edu/pub/kitching/CSP_papers/automatic_detection.pdf And a PhD by C Mears, see for instance http://www.csse.monash.edu.au/~mbanda/papers/constraints09.pdf I agree it is less easy to define and implement than LP matrix symmetry (13 Jun '12, 20:24) jfpuget @jfpuget "As said, you do not list all feasible solutions in your example. Start by lisitng all of them before looking for symmetry." Why do you think not all feasible solutions are listed? To me sounds all are listed. Sorry I jumped in, I am also very much interested in understanding this concept of symmetry as I suffer a lot from it in my benders decomposition and I just saw this is a nice example. (14 Jun '12, 01:02) ShahinG @jfpuget "As said, you do not list all feasible solutions in your example. Start by lisitng all of them before looking for symmetry." After adding the three missed equality constraints, I do not see if there exists any other feasible solution! Please correct me if I’m still mistaken. Thank you in advance (14 Jun '12, 05:03) Monemi 1 Thanks Jean-Francois. This is quite interesting. I appreciate the references. And I will also share. :-) From the "optimization side," there was a recent paper by Liberti that offers an approach to detect a large subgroup of the symmetry group for more general problems. ww.lix.polytechnique.fr/~liberti/minlpgroup.pdf (14 Jun '12, 10:22) Jeff Linderoth Thank you Jeff, I wsn't aware of this paper of Liberti. PS. You link is missing a w at the start ;) (14 Jun '12, 15:35) jfpuget 2 @monemi, I am not clever enough to derive the permutaitions on the set of feasible solutions, but as Jeff Linderoth says, you need to consider only those permutations that map feasible to feasible. Looking at the non zero matrix, I can derive symmetry however. Basically, you can exchange the two first constraints, and you can exchange two columns of these two constraints. This yields the following generators (x_12 x_21)(x_31 x_13)(x_23 x_32) (x_12 x_23)(x_21 x_32) (x_23 x_31)(x_32 x_13) (14 Jun '12, 15:40) jfpuget @jfpuget, Thank you very much for your comment. This is exactly what I was looking for. I am quite curious to ask one more question here: In general, would it be possible to have an instance with a non-empty set of feasible solutions of which contains multiple feasible solutions with the same value while no symmetry group exists? (15 Jun '12, 08:48) Monemi 1 @ShahinG Three constraints were missing when I said feasible solutions were missing (21 Jun '12, 20:35) jfpuget showing 5 of 12 show 7 more comments
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: