How tight is the corner relaxation? Insights gained from the stable set problem
Gérard Cornuéjols (gc0vandrew.cmu.edu)
Abstract: The corner relaxation of a mixed-integer linear program is a central concept in cutting plane theory. In a recent paper Fischetti and Monaci provide an empirical assessment of the strength of the corner and other related relaxations on benchmark problems. In this paper we give a precise characterization of the bounds given by these relaxations for the edge formulation of the maximum stable set problem in a graph.
Keywords: Stable set, corner relaxation, cutting planes
Category 1: Integer Programming ((Mixed) Integer Linear Programming )
Category 2: Combinatorial Optimization (Polyhedra )
Category 3: Integer Programming (Cutting Plane Approaches )
Citation: Gérard Cornuéjols, Carla Michini, Giacomo Nannicini. How tight is the corner relaxation? Insights gained from the stable set problem, Discrete Optimization(2012), http://dx.doi.org/10.1016/j.disopt.2012.02.004.
Entry Submitted: 10/28/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|