Exploiting Semidefinite Relaxations in Constraint Programming
journal contributionposted on 01.01.1976 by Willem-Jan Van Hoeve
Any type of content formally published in an academic journal, usually following a peer-review process.
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.