Conflict directed Backjumping for Max-CSPs

Roie Zivan, Amnon Meisels

Max-CSPs are Constraint Optimization Problems that are commonly solved using a Branch and Bound algorithm. The B\B algorithm was enhanced by consistency maintenance procedures. 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 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.