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's gravatar image

Monemi
2114
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

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.

link

answered 12 Jun '12, 13:38

Jeff%20Linderoth's gravatar image

Jeff Linderoth
4412
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

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.

link

answered 13 Jun '12, 06:52

jfpuget's gravatar image

jfpuget
2.5k310
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
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×28
×11
×6
×2
×2

Asked: 12 Jun '12, 11:48

Seen: 5,406 times

Last updated: 21 Jun '12, 20:35

OR-Exchange! Your site for questions, answers, and announcements about operations research.