Conflict Directed Backjumping for Max-CSPs. Conference Paper uri icon

abstract

  • Constraint Optimization problems are commonly solved us- ing a Branch and Bound algorithm enhanced by consis- tency maintenance procedures (Wallace and Freuder 1993; Larrosa and Meseguer 1996; Larrosa et al. 1999; Larrosa and Schiex 2003; 2004). All these algorithms traverse the search space in a chronological order and gain their efficiency from the quality of the consistency maintenance procedure. The present study introduces Conflict-directed Backjumping (CBJ) for Branch and Bound algorithms. The proposed al- gorithm maintains Conflict Sets which include only assign- ments whose replacement can lead to a better solution. The algorithm backtracks according to these sets. CBJ can be added to all classes of the Branch and Bound algorithm. In particular to versions of Branch & Bound that use ad- vanced maintenance procedures of soft local consistency lev- els, NC ∗, AC∗ and FD AC (Larrosa and Schiex 2003; 2004). The experimental evaluation of B&B CBJ on random Max-CSPs shows that the performance of all algorithms is improved both in the number of assignments and in the time for completion.

publication date

  • January 1, 2007

presented at event