کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141470 957004 2013 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope
چکیده انگلیسی

The pedigree is a combinatorial object defined over the cartesian product of certain subsets of edges in a complete graph. There is a 1–1 correspondence between the pedigrees and Hamiltonian cycles (tours) in a complete graph. Linear optimization over Hamiltonian cycles, also known as the symmetric traveling salesman problem (STSPSTSP) has several 0–1 integer and mixed integer formulations. The Multistage Insertion formulation (MI-formulationMI-formulation) is one such 0–1 integer formulation of the STSPSTSP. Any solution to the MIMI-formulation is a pedigree and vice versa. However the polytope corresponding to the pedigrees has properties not shared by the STSPSTSP polytope. For instance, (i) the pedigree polytope is a combinatorial polytope, in the sense, given any two nonadjacent vertices of the polytope W1,W2W1,W2, we can find two other nonadjacent vertices, W3,W4W3,W4, such that W1+W2=W3+W4W1+W2=W3+W4 and (ii) testing the nonadjacency of tours is an NPNP-complete problem, while the corresponding problem for the pedigrees is strongly polynomial. In this paper we demonstrate how the study of the nonadjacency structure is useful in understanding that of the tour polytope. We prove that a sufficiency condition for nonadjacency in the tour polytope is nonadjacency of the corresponding pedigrees in the pedigree polytope. This proof makes explicit use of properties of both the pedigree polytope and the MI-relaxationMI-relaxation problem.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 10, Issue 3, August 2013, Pages 224–232
نویسندگان
,