Article ID: | iaor20124028 |
Volume: | 9 |
Issue: | 2 |
Start Page Number: | 109 |
End Page Number: | 121 |
Publication Date: | May 2012 |
Journal: | Discrete Optimization |
Authors: | Cornujols Grard, Nannicini Giacomo, Michini Carla |
Keywords: | programming: linear, programming: integer |
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.