Dynamic Symmetry Breaking in Constraint Programming and Linear Programming Hybrids: Still Life as a Case Study

Petrie, K. E., Smith, B. M., and Yorke-Smith, N. Dynamic Symmetry Breaking in Constraint Programming and Linear Programming Hybrids: Still Life as a Case Study. Proceedings of the 2nd European Starting AI Researcher Symposium (STAIRS'04), Valencia, Spain, August 2004.

Abstract: Symmetry in Constraint Satisfaction Problems (CSPs) can lead to redundant search, since subtrees may be explored which are symmetric to subtrees previously explored. Symmetry can be excluded by Symmetry Breaking During Search (SBDS), a dynamic method that adds constraints during search so that partial assignments symmetric to those already considered will not be visited. The efficient solving of many CSPs has been achieved by hybrid methods that combine Constraint Programming (CP) and Linear Programming (LP). This paper presents a novel integration of hybrid methods with SBDS and a related method GAP-SBDS. The dynamic symmetry breaking methods have been successfully integrated with a full CP-LP hybrid, and with a hybrid where LP solves the constraints while CP controls search. The latter combination shows that CP symmetry breaking methods can be used with stand-alone linear programs. We apply the CP-LP-SBDS combination to the `maximum density still life problem'. We show that CP modelling techniques which improve the performance of a pure CP approach can also be integrated with the hybrid, increasing its efficiency still further.

An earlier version of this paper appeared as APES Technical Report 81.

Postscript (39K) | PDF (112K) | Bibtex entry

Symposium homepage