کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
474879 699161 2007 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The generalized fixed-charge network design problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
The generalized fixed-charge network design problem
چکیده انگلیسی

In this paper we present the generalized fixed-charge network design (GFCND) problem. The GFCND problem is an instance of the so-called generalized network design problems. In such problems, clusters instead of nodes have to be interconnected by a network. The network interconnecting the clusters is a fixed-charge network, and thus the GFCND problem generalizes the fixed-charge network design problem. The GFCND problem is related to the more general problem of designing hierarchical telecommunication networks.A mixed integer programming model is described and a branch-cut-and-price algorithm is implemented. Violated constraints and variables with negative reduced costs are found using enumeration. The algorithm is capable of obtaining optimal solutions for problems with up to 30 clusters and up to 300 nodes. This is possible, since the linear programming relaxation bound is very tight and there are few non-zero variables and few binding constraints.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 34, Issue 4, April 2007, Pages 997–1007
نویسندگان
, ,