عرض بسيط للتسجيلة

المؤلفHaouari, Mohamed
المؤلفMaculan, Nelson
المؤلفMrad, Mehdi
تاريخ الإتاحة2023-01-23T08:18:13Z
تاريخ النشر2013
اسم المنشورComputers and Operations Research
المصدرScopus
معرّف المصادر الموحدhttp://dx.doi.org/10.1016/j.cor.2013.01.002
معرّف المصادر الموحدhttp://hdl.handle.net/10576/38708
الملخصWe investigate the minimum-weight connected subgraph problem. The importance of this problem stems from the fact that it constitutes the backbone of many network design problems having applications in several areas including telecommunication, energy, and distribution planning. We show that this problem is NP-hard, and we propose a new polynomial-size nonlinear mixed-integer programming model. We apply the Reformulation-Linearization Technique (RLT) to linearize the proposed model while keeping a polynomial number of variables and constraints. Furthermore, we show how similar modelling techniques enable an enhanced polynomial size formulation to be derived for the shortest elementary path. This latter problem is known to be intractable and has many applications (in particular, within the context of column generation). We report the results of extensive computational experiments on graphs with up to 1000 nodes. These results attest to the efficacy of the proposed compact formulations. In particular, we show that the proposed formulations consistently outperform compact formulations from the literature. 2013 Elsevier Ltd.
اللغةen
الموضوعConnected subgraphs
Reformulation-Linearization Technique (RLT)
Shortest paths with negative cycles
العنوانEnhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles
النوعArticle
الصفحات2485-2492
رقم العدد10
رقم المجلد40
dc.accessType Abstract Only


الملفات في هذه التسجيلة

الملفاتالحجمالصيغةالعرض

لا توجد ملفات لها صلة بهذه التسجيلة.

هذه التسجيلة تظهر في المجموعات التالية

عرض بسيط للتسجيلة