کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4959537 1445954 2017 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Models for the piecewise linear unsplittable multicommodity flow problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Models for the piecewise linear unsplittable multicommodity flow problems
چکیده انگلیسی
In this paper, we consider multicommodity flow problems, with unsplittable flows and piecewise linear routing costs. We first focus on the case where the piecewise linear routing costs are convex. We show that this problem is NP-hard for the general case, but polynomially solvable when there is only one commodity. We then propose a strengthened mixed-integer programming formulation for the problem. We show that the linear relaxation of this formulation always gives the optimal solution of the problem for the single commodity case. We present a wide array of computational experiments, showing this formulation also produces very tight linear programming bounds for the multi-commodity case. Finally, we also adapt our formulation for the non-convex case. Our experimental results imply that the linear programming bounds for this case, are only slightly weaker than the ones of state-of-the-art models for the splittable flow version of the problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 261, Issue 1, 16 August 2017, Pages 30-42
نویسندگان
, , ,