# Combining Symmetry Breaking And Global Constraints⋆

George Katsirelos, Nina Narodytska, and Toby Walsh NICTA and UNSW, Sydney, Australia Abstract. We propose a new family of constraints which combine together lexicographical ordering constraints for symmetry breaking with other common global constraints. We give a general purpose propagator for this family of constraints, and show how to improve its complexity by exploiting properties of the included global constraints.

## 1 Introduction

The way that a problem is modeled is critically important to the success of constraint programming. Two important aspects of modeling are symmetry and global constraints. A common and effective method of dealing with symmetry is to introduce constraints which eliminate some or all of the symmetric solutions [1]. Such symmetry breaking constraints are usually considered separately to other (global) constraints in a problem. However, the interaction between problem and symmetry breaking constraints can often have a significant impact on search. For instance, the interaction between problem and symmetry breaking constraints gives an exponential reduction in the search required to solve certain pigeonhole problems [2]. In this paper, we consider even tighter links between problem and symmetry breaking constraints. We introduce a family of global constraints which combine together a common type of symmetry breaking constraint with a range of common problem constraints. This family of global constraints is useful for modeling scheduling, rostering and other problems.

Our focus here is on matrix models [3]. Matrix models are constraint programs containing matrices of decision variables on which common patterns of constraints are posted. For example, in a rostering problem, we might have a matrix of decision variables with the rows representing different employees and the columns representing different shifts. A problem constraint might be posted along each row to ensure no one works too many night shifts in any 7 day period, and along each column to ensure sufficient employees work each shift. A common type of symmetry on such matrix models is row interchangeability [4]. Returning to our rostering example, rows representing equally skilled employees might be interchangeable. An effective method to break such symmetry is to order lexicographically the rows of the matrix[4]. To increase the propagation between such symmetry breaking and problem constraints, we