The Terminal Assignment ProblemThe Terminal Assignment ProblemThe Terminal Assignment ProblemThe Terminal Assignment ProblemSlide 5The Concentrator Location ProblemThe Concentrator Location ProblemThe Concentrator Location ProblemThe Concentrator Location ProblemSlide 10Slide 11Slide 12Slide 13ADD heuristicsADD heuristicsADD heuristicsADD heuristicsDROP heuristicsThe Terminal Assignment Problem•Problem description–Given n terminals and m concentrators.–Task: connect each terminal to a concentrator, so that the connection cost is minimized.–The cost of connecting terminal i to concentrator j is cij–Each concentrator can accomodate at most q terminals.The Terminal Assignment Problem•The Terminal Assignment Problem•The Terminal Assignment Problem••The Concentrator Location Problem•The additional difficulty in this task, in comparison with the terminal assignment problem, is that now neither the number nor the locations of the concentrators are fixed, choosing them is part of the optimization. This, as expected, makes it more difficult.The Concentrator Location Problem•Itemized description–Given n terminals and m concentrator sites.–Task: select which sites will be used for concentrators and connect each terminal to a concentrator, so that the connection cost plus the concentrator 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.The Concentrator Location Problem•The Concentrator Location Problem••••Comment: Trade-off. –If concentrator costs dominate, then there will be few concentrators, each serving many terminals. –If the terminal assignment (cabling) cost dominates, then there will be many concentrators, each serving only a few nearby terminals.•Solution–The problem can be treated as a 0-1 linear integer program, but then the complexity is high. It is reasonable to use a heuristic solution.ADD heuristics•This heuristics is based on increasing the number of concentrators one by one. Initially the constraint of serving at most k terminals per concentrator is violated, but it will be satisfied as the number of concentrators grows.ADD heuristics•The algorithm proceeds as follows:–Select the concentrator site with minimum cost, place a single concentrator there. In this initial solution the assignment is trivial: all terminals are assigned to the single concentrator.–Choose the cheapest of the remaining sites and place the second concentrator there.–Solve the terminal assignment problem for this 2-concentrator system with q = ⌈n/2⌉. (Recall that q was the parameter in the terminal assignment problem that controlled how many terminals can be served by a concentrator).ADD heuristics–Choose again a cheapest remaining site and place the 3rd concentrator there.–Solve the terminal assignment problem for the 3-concentrator system with q = ⌈n/3⌉.–Continue the same way, by adding new concentrators one by one, until q ≤ k and adding a new concentrator already does not decrease the total cost.ADD heuristics–After adding the ith concentrator, we use q = ⌈n/i⌉ in the corresponding terminal assignment problem, to make sure that every terminal can be accomodated. We stop if by adding a new concentrator no saving results and already q ≤ k holds, that is, the concentrator capacity constraint can be satisfied with the required parameter k.DROP heuristics•Works similarly, but we start from the other end: initially all sites have concentrators and they are dropped one by one, until no further cost reduction results while the constraints can still be
View Full Document
Unlocking...