Computing Lower Bound for MAX-CSP Problems

摘要

The inefficiency of the branch and bound method for solving Constraint Optimization Problems is due in most cases to the poor quality of the lower bound used by this method. Many works have been proposed to improve the quality of this bound. In this, paper we investigate a set of lower bounds by considering two criteria: the quality and the computing cost. We study different ways to compute the parameters of the parametric lower bound and we propose heuristics for searching the parameters maximizing the parametric lower bound. Computational experiments performed over randomly generated problems show the advantages of our new branch and bound scheme.