How Tight is the Corner Relaxation? Insights Gained from the Stable Set Problem

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 12, 2012
Accession Number
ADA586516

Entities

People

  • Carla Michini
  • Giacomo Nannicini
  • Gérard Cornuéjols

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Abstracts
  • Applied Mathematics
  • Construction
  • Convex Programming
  • Inequalities
  • Information Operations
  • Interdisciplinary Science
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Operations Research
  • Optimization
  • Probability
  • Schools
  • Standards
  • Systems Science
  • Triangles

Readers

  • Operations Research