01380nas a2200157   4500008004100000245009300041210006900134260000900203300001200212490000700224520082200231653000801053100001501061700002101076856012501097       2003                        eng d00aAn Efficient Heuristic for Solving an Extended Capacitated Concentrator Location Problem0 aEfficient Heuristic for Solving an Extended Capacitated Concentr  c2003  a171-1990 v233 aIn this paper, a mathematical model and a solution algorithm are developed for solving an extended capacitated concentrator location problem. Our model extends the conventional formulation by simultaneously addressing the two capacity constraints, total connection ports and maximum data processing rate, on each concentrator to be selected for satisfying the communication demands of the given end-user nodes. Since the problem is NP-complete, an efficient and effective Lagrangian heuristic is developed and tested by solving 100 randomly generated test problems with sizes ranging from 30(nodes)×30(concentrators) to150×30. Altogether 58% of the tested problems are solved optimally with an average solution gap 0.36% from the optimality and average solution times are from a few seconds to one half of a minute.10aBIS1 aRaja, V.T.1 aHan, Bernard, T.  u/biblio/efficient-heuristic-solving-extended-capacitated-concentrator-location-problem-0