Block-diagonal semidefinite programming hierarchies for 0/1 programming

Details Block-diagonal semidefinite programming hierarchies for 0/1 programming Block-diagonal semidefinite programming hierarchies for 0/1 programming

2007-12-19

arxiv.org/abs/0712.3079v2

Oper. Res. Lett., 37 (2009), 27-31

Mathematics

Optimization and Control

11 pages, (v2) revision based on suggestions by referee, computation of N+(TH(P_q)) included in Table 2

Scientific paper

10.1016/j.orl.2008.10.003

Lovasz and Schrijver, and later Lasserre, proposed hierarchies of semidefinite programming relaxations for general 0/1 linear programming problems. In this paper these two constructions are revisited and two new, block-diagonal hierarchies are proposed. They have the advantage of being computationally less costly while being at least as strong as the Lovasz-Schrijver hierarchy. Our construction is applied to the stable set problem and experimental results for Paley graphs are reported.

Affiliated with

Also associated with

No associations

Rating

Block-diagonal semidefinite programming hierarchies for 0/1 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 Block-diagonal semidefinite programming hierarchies for 0/1 programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Block-diagonal semidefinite programming hierarchies for 0/1 programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-145992