  


A smaller extended formulation for the odd cycle inequalities of the stable set polytope
Sven de Vries (devriesunitrier.de) Abstract: 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 can 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 (01 Programming ) Citation: Download: [PDF] Entry Submitted: 09/12/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  