Conflict Directed Backjumping for Max-CSPs

Contents

Constraint Optimization problems are commonly solved using a Branch and Bound algorithm enhanced by consistency 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 algorithm maintains Conflict Sets which include only assignments 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 and Bound that use advanced maintenance procedures of soft local consistency levels, NC*, AC* and FDAC. 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.