کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420782 683981 2008 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the general routing polytope
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the general routing polytope
چکیده انگلیسی

The General Routing Problem (GRP) consists of finding a minimum length closed walk in an edge-weighted undirected graph, subject to containing certain sets of required nodes and edges. It is related to the Rural Postman Problem and the Graphical Traveling Salesman Problem.We examine the 0/1-polytope associated with the GRP introduced by Ghiani and Laporte [A branch-and-cut algorithm for the Undirected Rural Postman Problem, Math. Program. Ser. A 87 (3) (2000) 467–481]. We show that whenever it is not full-dimensional, the set of equations and facets can be characterized, and the polytope is isomorphic to the full-dimensional polytope associated with another GRP instance which can be obtained in polynomial time. We also offer a node-lifting method. Both results are applied to prove the facet-defining property of some classes of valid inequalities. As a tool, we study more general polyhedra associated to the GRP.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 3, 1 February 2008, Pages 368–384
نویسندگان
, ,