Partial ARTIAL Incompatible based Lower Bound of NC* For MAX-CSPsAshraf M. Bhery, and Wafaa A. Kabela ; Khamis, Soheir
AbstractMaximal 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), . 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.
|Keywords||Constraint satisfaction; Max-CSP; Branch and Bound; Lower bound; Node consistency; NC*-CBJ||Issue Date||1-Jan-2013||Journal||Egyptian Computer Science Journal||URI||http://research.asu.edu.eg/123456789/1127|
Recommend this item
|Partial ARTIAL Incompatible based Lower Bound of NC For MAX-CSPs.pdf||567.98 kB||Adobe PDF||View/Open|
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.