# 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
 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: