Optimization Online


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

Gérard Cornuéjols (gc0v***at***andrew.cmu.edu)
Carla Michini (michini***at***dis.uniroma1.it)
Giacomo Nannicini (nannicini***at***sutd.edu.sg)

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
Entry Accepted: 10/28/2011
Entry Last Modified: 03/08/2012

Modify/Update this entry

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


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