How tight is the corner relaxation? Insights gained from the stable set problem

DOI10.1016/j.disopt.2012.02.004zbMath1252.90052OpenAlexW2139431443MaRDI QIDQ448970

Giacomo Nannicini, Carla Michini, Cornuéjols, Gérard

Publication date: 11 September 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2012.02.004

zbMATH Keywords

stable setcutting planescorner relaxation

Mathematics Subject Classification ID

Mixed integer programming (90C11) Linear programming (90C05)

Related Items

Theoretical challenges towards cutting-plane selection, The Hirsch conjecture for the fractional stable set polytope, Can Cut-Generating Functions Be Good and Efficient?, On the Circuit Diameter of Some Combinatorial Polytopes, The strength of Dantzig-Wolfe reformulations for the stable set and related problems, On the complexity of surrogate and group relaxation for integer linear programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A heuristic to generate rank-1 GMI cuts
• Chvátal closures for mixed integer programming problems
• How tight is the corner relaxation?
• Stable sets, corner polyhedra and the Chvàtal closure
• Random near-regular graphs and the node packing problem
• An exact threshold theorem for random graphs and the node-packing problem
• A recursive procedure to generate all cuts for 0-1 mixed integer programs
• Some polyhedra related to combinatorial problems
• Vertex packings: Structural properties and algorithms
• Triangle Factors in Random Graphs
• On the facial structure of set packing polyhedra
• On the maximal number of independent circuits in a graph