Exploiting Semidefinite Relaxations in Constraint Programming

Details Exploiting Semidefinite Relaxations in Constraint Programming Exploiting Semidefinite Relaxations in Constraint Programming

2004-07-16

arxiv.org/abs/cs/0407041v1

Computer Science

Discrete Mathematics

18 pages, 4 figures. Submitted preprint

Scientific paper

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 produces a bound for the solution value, which is used to prune parts of the search tree. Experimental results on stable set and maximum clique problem instances show that constraint programming can indeed greatly benefit from semidefinite relaxations.

Affiliated with

Also associated with

No associations

Rating

Exploiting Semidefinite Relaxations in Constraint Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Exploiting Semidefinite Relaxations in Constraint Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exploiting Semidefinite Relaxations in Constraint Programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-636287