Detection of Permutation Symmetries in Continuous Constraint Problems

Work default illustration


  • If you are interested in the proposal, please contact with the supervisors.


Project background:
Symmetry exploitation in discrete constraint problems has received a great deal of attention lately, because they can lead to simplifications and computational savings.
Recent work in which IRI has been actively participating, has filled the gap in continuous (or numerical) constraint solving domains, offering a general symmetry breaking algorithm.
Now we want to focus in symmetry detection in continuous domains, which is largely an unexplored field. Some molecular conformation problems (Figure 1) are examples of symmetric problems in nature.
The proposed project can be adapted to be a degree or a master final work.

Figure 1: The Hex B, a symmetrical protein involved in the Tay-Sach disease.

The main objective at this project is to implement a method that detects potential symmetric problems, quickly excluding non symmetric problems. This work will be in principle restricted to deal only with symmetries due to permutation of variableS (i.e., problemS which remain unchanged under some permutation of variables).
The method will be validated in a standard benchmark of numerical problems to detect their known symmetries and perhaps others previously unknown.
In the case of a master work, the student could be involved not only in implementing the method but also in eventually extending and improving it.

Expected requirements:
Solid Mathematical background is a plus. Although it is not strictly required for the implementation, a taste for group theory will be appreciated. Computational Group Theory would be helpful.
Some programming skills. Knowledge of Matlab and C/C++ will be appreciated.