Conflict based backjumping for constraints optimization problems Academic Article uri icon

abstract

  • Constraints Optimization problems are commonly solved using a Branch and Bound algorithm enhanced by a consistency maintenance procedures [WF93] [LM96,LMS99,LS04]. All these algorithms traverse the search space in a chrono-logical order and gain their efficiency from the quality of the consistency mainte-nance procedure. The present study introduces Conflict-based Backjumping (CBJ) in Branch and Bound algorithms. The proposed algorithm maintains Conflict Sets which include only assignments whose replacement can lead to a better solution and backtracks according to these sets. CBJ can be added to Branch and Bound which uses the most advanced consistency maintenance heuristics, N C* and AC*. The exper-imental evaluation of of B&B CBJ on random Max-CSPs shows that the per-formance of the algorithms are improved by a large factor.

publication date

  • January 1, 2005