Exploiting Semidefinite Relaxations in Constraint Programming

Constraint programming uses enumeration and search tree pruning to solve combinatorial optimization problems. In order to speed up this solution process, we investigate the use of semidefinite relaxations within constraint programming. In principle, we use the solution of a semidefinite relaxation to guide the traversal of the search tree, using a limited discrepancy search strategy. Furthermore, a semidefinite relaxation generally produces a tight bound for the solution value, which improves the pruning behaviour. Experimental results on stable set problem instances and maximum clique problem instances show that constraint programming can indeed greatly benfiet from semidefinite relaxations.