Re: [Help-glpk] handling symmetries among constraints

[Peter Dobcsanyi]

On Mon, Dec 24, 2007 at 07:39:37PM -0800, Erik Rantapaa wrote:
> I was wondering if there are standard techniques for adding
> constraints to break variable symmetries. I am primarily interested in
> the case where all the variables are binary integer variables. I
> suppose there are a lot of questions one could ask in this vein, such
> as:
> 
> 1. What is the standard way to define and designate that sets of
> variables are interchangeable with each other (i.e. a rigorous
> definition)?

Here is a definition starting with the standard form of an LP problem

    minimize cx subject to Ax >= b

where A is an m x n matrix b is an m-vector and c is an n-vector.  Let t
be a permutation of [1,...,m] and v is a permutation of [1,...,n] and
let g = (t,v). Define A^g to be the matrix obtained from A by permuting
its rows according to t and columns according to v. b^g is the vector
obtained by permuting b's entries according to t and c^g is defined
similarly but using v.

The "symmetry group" of the LP problem is the set G of all g=(t,v) such
that A^g = A, b^g = b and c^g=c.  It is easy to see that G really is a
group, namely a subgroup of (S_m x S_n). Moreover x is feasible if and
only if x^g is feasible, and x is optimal iff x^g is optimal.


> 2. Given that you have identified a set of symmetries, what are good
> ways to add constraints to help the solver avoid investigating
> symmetric solution paths.

Tough question, ... it depends on many factors, not only on the
particular problem at hand but also on whether you are interested to
find only one solution or all of them.  Some of the useful constraints
might not easily be expressed in the Ax=b framework.  It is a very
active research area, in particular, for constraint satisfaction
problems.


> 3. To what extent can the symmetries be found algorithmically?

Consider the LP problem just as a discrete structure which can then be
transformed into an equivalent graph.  Compute the automorphism group of
this graph.  In general, that cannot be done in polynomial time,
although it is believed not to be NP-hard.


> 4. Would it help a solver such as GLPK to know that the problem has
> certain symmetries?

Knowing the symmetry group in advance could help, of course.
Unfortunately, determining the symmetries can be very costly, see above. 

One approach could be a parallel solver running on many processors which
dedicates some processing resources to finding the automorphism group
then it tries to utilize this information if the traditional "solver"
part of the program has still not reached a conclusion.

    Peter