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

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

0.00 Avg rating0 Votes
Article ID: iaor20124028
Volume: 9
Issue: 2
Start Page Number: 109
End Page Number: 121
Publication Date: May 2012
Journal: Discrete Optimization
Authors: , ,
Keywords: programming: linear, programming: integer
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.

Reviews

Required fields are marked *. Your email address will not be published.