کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
480003 1446061 2013 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Enhanced formulations and branch-and-cut for the two level network design problem with transition facilities
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Enhanced formulations and branch-and-cut for the two level network design problem with transition facilities
چکیده انگلیسی

We consider a new combinatorial optimization problem that combines network design and facility location aspects. Given a graph with two types of customers and two technologies that can be installed on the edges, the objective is to find a minimum cost subtree connecting all customers while the primary customers are served by a primary subtree that is embedded into the secondary subtree. In addition, besides fixed link installation costs, facility opening costs, associated to each node where primary and secondary subtree connect, have to be paid. The problem is called the Two Level Network Design Problem with Transition Facilities (TLNDF).We first model the problem on an extended graph where an additional set of arcs corresponds to the installation of node facilities and propose a cut set based model for the TLNDF that is defined on this extended graph. We present several theoretical results relating families of cut set inequalities on the extended graph with subfamilies of cut set inequalities on the original graph. We then show how a standard multi-commodity flow model defined on the original graph can be strengthened using disaggregation “by technology”. We prove that the disaggregated compact formulation on the original graph provides the same lower bound as the cut set formulation on the extended graph.We develop a branch-and-cut algorithm for solving the TLNDF. The performance of this algorithm is improved by separating subfamilies of cut set inequalities on the original graph. Our computational study confirms the efficiency and applicability of the new approach.


► A new optimization problem combining facility location and network design decisions.
► Three extended formulations are proposed and projected onto the original variable space.
► Disaggregated flow model is equivalent to the model on extended graph.
► Polynomial separation of subfamilies of cuts is proposed and computationally tested.
► Branch-and-cut variants are compared.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 225, Issue 2, 1 March 2013, Pages 211–222
نویسندگان
, , ,