A hybrid constraint programming and semidefinite programming approach for the stable set problem

Details A hybrid constraint programming and semidefinite programming approach for the stable set problem A hybrid constraint programming and semidefinite programming approach for the stable set problem

2003-02-25

arxiv.org/abs/math/0302307v1

Mathematics

Combinatorics

14 pages

Scientific paper

This work presents a hybrid approach to solve the maximum stable set problem, using constraint and semidefinite programming. The approach consists of two steps: subproblem generation and subproblem solution. First we rank the variable domain values, based on the solution of a semidefinite relaxation. Using this ranking, we generate the most promising subproblems first, by exploring a search tree using a limited discrepancy strategy. Then the subproblems are being solved using a constraint programming solver. To strengthen the semidefinite relaxation, we propose to infer additional constraints from the discrepancy structure. Computational results show that the semidefinite relaxation is very informative, since solutions of good quality are found in the first subproblems, or optimality is proven immediately.

Affiliated with

Also associated with

No associations

Rating

A hybrid constraint programming and semidefinite programming approach for the stable set problem 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 A hybrid constraint programming and semidefinite programming approach for the stable set problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A hybrid constraint programming and semidefinite programming approach for the stable set problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-482852