کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141814 957093 2012 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
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
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 9, Issue 2, May 2012, Pages 109–121
نویسندگان
, , ,