کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6895773 | 1445981 | 2016 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Integer programming formulations for the elementary shortest path problem
ترجمه فارسی عنوان
فرمولاسیون برنامه نویسی صحیح برای مشکل کمترین مسیر اولیه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
برنامه ریزی عدد صحیح کوتاهترین مسیر اولیه، شعبه و برش، فرمول های توسعه یافته، محدودیت حذف زیرزمینی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
Given a directed graph G=(V,A) with arbitrary arc costs, the Elementary Shortest Path Problem (ESPP) consists of finding a minimum-cost path between two nodes s and t such that each node of G is visited at most once. If negative costs are allowed, the problem is NP-hard. In this paper, several integer programming formulations for the ESPP are compared. We present analytical results based on a polyhedral study of the formulations, and computational experiments where we compare their linear programming relaxation bounds and their behavior within a branch-and-cut framework. The computational results show that a formulation with dynamically generated cutset inequalities is the most effective.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 252, Issue 1, 1 July 2016, Pages 122-130
Journal: European Journal of Operational Research - Volume 252, Issue 1, 1 July 2016, Pages 122-130
نویسندگان
Leonardo Taccari,