SymCon'07

The Seventh International Workshop on Symmetry and Constraint Satisfaction Problems

A Satellite Workshop of CP 2007 - September 23rd 2007 - Providence, RI, USA

Homepage        Call for Papers        Important Dates        Organisation

Proceedings       Programme        Previous Workshops

 

Invited Speaker

Stefan Szeider

Department of Computer Science Durham University
Durham, UK
 stefan.szeider@durham.ac.uk

Title:  Without Loss of Generality – Symmetric Reasoning for
          Resolution Systems

Abstract:
Krishnamurthy [1985] introduced symmetry rules that make the informal “without loss of generality” reasoning available for resolution based systems. The homomorphism rules of Szeider [2005] are more powerful variants of Krishnamurthy’s rules and can save in certain cases an exponential number of inference steps over symmetry rules. In this talk we will review the concepts of symmetry and homomorphism rules for resolution-based systems and discuss various questions and results that arise in that context.

 

Technical Programme

8:50                                                      Opening remarks           (Berthe Y. Choueiry)
9:00-10:30                                             Session 1            (Chair:  Meinolf Sellman)
09:00 - A Novel Approach For Detecting Symmetries in CSP Models
       B. Domoen, M. Garcia de la Banda, C. Mears, M. Wallace
 
09:30 - Exploiting Symmetry in Multiple Knapsack Problems.
       A.S. Fukunaga
     
10:00 - Efficient Symmetry Breaking Predicates for Quantified Boolean Formulas
        G. Audemard, S. Jabbour, L. Sais
10:30                                                    Coffee Break
11:00-12:30                                           Session 2             (Chair:  Lakhdar Sais)
11:00 - Minimal Ordering Constraints for Some Families of Variable Symmetries
       A. Grayland, I. Miguel, C. Rouney-Dougal
 
11:30 - Invited talk:   Without Loss of Generality - Symmetric Reasoning for Resolution Systems
        S. Szeider
     
12:30-2:00                                             Lunch
2:10-3:30                                               Session 3             (Chair:  Inês Lynce)
2:10 - Breaking Value Symmetry
      T. Walsh
 
2:30 - Symmetry in Constraint Optimization
      T. Walsh

2:50 - A CP Approach to the Balanced Academic Curriculum Problem
     J.N. Monette, P. Schaus, S. Zampelli, Y. Deville, P. Dupont

3:10 - Symmetry Breaking in Subgraph Isomorphism
      S. Zampelli, Y. Deville, M.R. Saidi, B. Benhamou
3:30                                                      Coffee Break
4:00-5:00                                               Session 4                (Chair:  Toby Walsh)
4:00 - Symmetry Breaking in Local Search for Unsatisfiability
      F. Aloul, I. Lynce, S. Prestwich
 
4:20 - Symmetry-Breaking Formulas for Groups with Bounded Orbit Projections
      A. Roy

4:40 - Dynamic Detection and Elimination of Local Symmetry in CSPs
      B. Benhamou, M.R.  Saidi
5:00              Informal discussion on symmetry   (Belaïd Benhamou & Berthe Y. Choueiry)