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

DOI10.1016/J.DISOPT.2012.02.004MaRDI QIDQ448970zbMATH OpenOpenAlexFDO

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

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

cutting planesstable setcorner relaxation

Mathematics Subject Classification ID

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

Recommendations

• How tight is the corner relaxation?
• Computational Experience with Stable Set Relaxations
• Stable sets, corner polyhedra and the Chvàtal closure
• Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem
• Strong lift-and-project cutting planes for the stable set problem

Cites work

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

Cited in

(8)

• The Hirsch conjecture for the fractional stable set polytope
• Stable sets, corner polyhedra and the Chvàtal closure
• How tight is the corner relaxation?
• Can cut-generating functions be good and efficient?
• The strength of Dantzig-Wolfe reformulations for the stable set and related problems
• On the circuit diameter of some combinatorial polytopes
• On the complexity of surrogate and group relaxation for integer linear programs
• Theoretical challenges towards cutting-plane selection

This page was built for publication: How tight is the corner relaxation? Insights gained from the stable set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q448970)