TWO-PHASE HEURISTIC FOR CAPACITATED DEGREE CONSTRAINED MIN-SUM ARBORESCENCE

Rakesh Kawatra ()
Additional contact information
Rakesh Kawatra: Minnesota State University-Mankato

No 201371, Proceedings of International Academic Conferences from International Institute of Social and Economic Sciences

Abstract: We present a two-phase heuristic for designing a capacitated degree constrained min sum arborescence. For a given directed graph G(V,E) where V={0, 1,?,n} with nonnegative costs Cij for each (i,j) ? E, our heuristic finds a minimum cost arborescence rooted at node 1 that spans the set {0, 1,?,n} with a constraint that the number of edges incident on each node i ? {1,2,?,n} is limited to a predetermined number constrained by the number of ports available on them (degree constraint). Additionally, the polling and response time constraints limit the number of nodes in the sub-trees rooted at node 1 (capacity constraint) predefined number. Lower bounds given for the integer programming formulation of the problem by our heuristic is used to estimate the quality of the solutions. Experimental results over a wide range of problem structures show that the two-phase heuristic gives verifiably good solutions to this problem.

Keywords: Integer programming; network design; heuristics; Lagrangian relaxation (search for similar items in EconPapers)
JEL-codes: C00 C60 C61 (search for similar items in EconPapers)
Pages: 1 page
Date: 2014-06
References: Add references at CitEc
Citations:

Published in Proceedings of the Proceedings of the 10th International Academic Conference, Vienna, Jun 2014, pages 347-347

Downloads: (external link)
https://iises.net/proceedings/10th-international-a ... id=2&iid=53&rid=1371 First version, 2014

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sek:iacpro:0201371

Access Statistics for this paper

More papers in Proceedings of International Academic Conferences from International Institute of Social and Economic Sciences
Bibliographic data for series maintained by Klara Cermakova ().