12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > An approach to the stable set problem based on ...
View graph of relations

« Back

An approach to the stable set problem based on ellipsoids

Research output: Contribution in Book/Report/ProceedingsChapter (peer-reviewed)

Published

Publication date2011
Host publicationInteger Programming and Combinatorial Optimization : Proceedings of the 15th International IPCO Conference
EditorsOktay Günlük, Gerhard Woeginger
Place of publicationBerlin
PublisherSpringer
Pages223-234
Number of pages12
ISBN (Print)9783642208065
Original languageEnglish

Conference

Conference15th International Conference, IPCO 2011
CountryUnited States
CityNew York
Period15/06/1117/06/11

Publication series

NameLecture Notes in Computer Science
Volume6655

Conference

Conference15th International Conference, IPCO 2011
CountryUnited States
CityNew York
Period15/06/1117/06/11

Abstract

A new exact approach to the stable set problem is presented, which attempts to avoids the pitfalls of existing approaches based on linear and semidefinite programming. The method begins by constructing an ellipsoid that contains the stable set polytope and has the property that the upper bound obtained by optimising over it is equal to the Lovasz theta number. This ellipsoid is then used to derive cutting planes, which can be used within a linear programming-based branch-and-cut algorithm. Preliminary computational results indicate that the cutting planes are strong and easy to generate.