Partial ARTIAL Incompatible based Lower Bound of NC* For MAX-CSPs

Abstract

Maximal Constraint Satisfaction Problems (Max-CSPs) are constraint optimization problems, in which the goal is to maximize the number of satisfied constraints. Max-CSPs are, in general, solved using Branch and Bound (B&B) algorithms. Their respective efficiency highly depends on the quality of the lower bound. The naive B&B has been improved by using consistency maintenance procedures and conflict backjumping. In this paper, the authors give a new treatment for improving NC*-CBJ algorithm for solving a Max-CSP which is the B&B algorithm using advanced Node Consistency procedure (NC*) and performing Conflict-directed Backjumbing (CBJ), [17]. The goal of this improvement is increasing the lower bound of NC*-CBJ via taking into account more inconsistencies which resulted from the proposed partially incompatible relation between the future variables. The introduced treatment leads to suggesting new algorithm, M-NC*-CBJ, which is a natural successor of NC*-CBJ algorithm including the modification of the lower bound. By comparing with the results of NC*-CBJ, the experimental results of M-NC*-CBJ on random CSPs show improvement both in execution times and number of assignments.