The Concentrator Location ProblemProblem descriptionThe additional difficulty in this task, in comparison with the terminal as-signment problem, is that now neither the number nor the locations of theconcentrators are fixed, choosing them is part of the optimization. This, asexpected, makes it more difficult.Itemized description• Given n terminals and m concentrator sites.• Task: select which sites will be used for concentrators and connecteach terminal to a concentrator, so that the connection cost plus theconcentrator cost is minimized.• The cost of connecting terminal i to concentrator site j is cij.• The cost of placing a concentrator at site j is dj.• Each concentrator can accomodate at most k terminals.Formulation as a mathematical programLet us introduce variables. The first set of variables indicates which terminalis connected to which site:xij=1 if terminal i is connected to site j0 otherwiseThe second set of variables will indicate which sites are selected for placinga concentrator:yj=1 if concentrator is placed at site j0 otherwiseThe objective is minimizing the total cost. This includes now the concentra-tor placement cost, too:min Z =nXi=1mXj=1cijxij+mXj=1djyj.Constraints:• Each concentrator can accomodate at most q terminals. Furthermore,if there is no concentrator at a site, then no terminal is connected toit:nXi=1xij≤ kyj(∀j)Note that if yj= 0, i.e., there is no concentrator at site j, then it forcesthe lefthand-side to 0, that is, no terminal can connect to the site.• Each terminal is connected to exactly one concentrator:mXj=1xij= 1 (∀i)Summarizing, the mathematical program is:min Z =nXi=1mXj=1cijxij+mXj=1djyj.Subject tonXi=1xij≤ kyj(∀j)mXj=1xij= 1 (∀i)xij, yj∈ {0, 1} (∀i, j)Comment: Trade-off. If concentrator costs dominate, then there will befew concentrators, each serving many terminals. If the terminal assignment(cabling) cost dominates, then there will be many concentrators, each servingonly a few nearby terminals.SolutionThe problem can be treated as a 0-1 linear integer program, but then thecomplexity is high. It is reasonable to use a heuristic solution.ADD heuristicsThis heuristics is based on increasing the number of concentrators one byone. Initially the constraint of serving at most k terminals per concentratoris violated, but it will be satisfied as the number of concentrators grows.The algorithm proceeds as follows:• Select the concentrator site with minimum cost, place a single con-centrator there. In this initial solution the assignment is trivial: allterminals are assigned to the single concentrator.• Choose the cheapest of the remaining sites and place the second con-centrator there.• Solve the terminal assignment problem for this 2-concentrator systemwith q = dn/2e. (Recall that q was the parameter in the terminalassignment problem that controlled how many terminals can be servedby a concentrator).• Choose again a cheapest remaining site and place the 3rd concentratorthere.• Solve the terminal assignment problem for the 3-concentrator systemwith q = dn/3e.• Continue the same way, by adding new concentrators one by one, untilq ≤ k and adding a new concentrator already does not decrease thetotal cost.Comment: After adding the ith concentrator, we use q = dn/ie in the cor-responding terminal assignment problem, to make sure that every terminalcan be accomodated. We stop if by adding a new concentrator no savingresults and already q ≤ k holds, that is, the concentrator capacity constraintcan be satisfied with the required parameter k.DROP heuristicsWorks similarly, but we start from the other end: initially all sites have con-centrators and they are dropped one by one, until no further cost reductionresults while the constraints can still be
View Full Document
Unlocking...