-

 

 

 




Optimization Online





 

An improved extended formulation for the odd cycle inequalities of the stable set polytope

Sven de Vries (devries***at***uni-trier.de)
Bernd Perscheid (perscheid***at***uni-trier.de)

Abstract: Especially for sparse graphs, the odd cycle polytope can be used to compute useful bounds for the maximum stable set problem quickly. Yannakakis introduced an extended formulation for the odd cycle inequalities of the stable set polytope in 1991, which provides a direct way to optimize over the odd cycle polytope in polynomial time, although there exist exponentially many odd cycles in given graphs in general. We present another extended formulation for the odd cycle polytope that uses less variables and inequalities than Yannakakis’ formulation. Moreover, we compare the running time of both formulations as relaxations of the maximum stable set problem in a computational study.

Keywords: Stable set, Odd cycle inequalities, Separation algorithm, Extended formulation, Linear programming

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Category 3: Integer Programming (0-1 Programming )

Citation:

Download: [PDF]

Entry Submitted: 09/12/2019
Entry Accepted: 09/12/2019
Entry Last Modified: 10/18/2019

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society