Networks with redundant points of presence using approximation methods and systems

1. An approximation method carried out by computer-usable program code operable by a computer system for designing a minimum cost network with k-fold redundant coverage of objects to be served by the network, by starting from a collection of potential network elements each having a defined cost value and each having a defined object coverage parameter, and by transforming the collection of potential network elements into a set of network elements that provide the required k-fold redundant coverage at approximate minimum cost, comprising:

providing a k-set coverage formulation with the cost values and the object coverage parameter values of the collection of potential network elements;

providing a Lagrangian relaxation formulation of the k-set coverage formulation;

applying an iterative subgradient optimization algorithm to the Lagrangian relaxation;

determining an initial solution found by an iteration of the subgradient optimization algorithm;

applying a greedy construction algorithm to add selected elements to the initial solution to form a feasible solution by

determining the cardinality of an unselected element as the number of objects not in previously selected elements that the unselected element covers,

selecting from the remaining unselected elements based on the ratio of cost to cardinality, and

repeating the determining and selecting steps until a feasible solution has been obtained,

using the feasible solution to select parameters for the next iteration of the subgradient optimization algorithm,

continuing to perform iterations until a set of network elements having an approximate minimum cost solution is identified, and

selecting for the network design network elements which are identified in the approximate minimum cost solution from the collection of potential network elements so that the resulting network design will have the required redundancy and approximate minimum cost.

2. The method claimed in claim 1 wherein the subgradient optimization algorithm updates Lagrangian multipliers using a step size, and wherein the feasible solution is used to adjust the step size at each subgradient optimization iteration.

3. The method claimed in claim 1 further comprising:

evaluating each element in the feasible solution constructed with the greedy construction algorithm in decreasing order of its cost to determine whether if the element is removed the resulting solution remains a feasible solution, and

removing the element if the resulting solution remains a feasible solution.

4. The method claimed in claim 1 wherein the greedy construction algorithm selects from the remaining unselected elements the one with the lowest ratio of cost to cardinality.

5. The method claimed in claim 1 wherein the greedy construction algorithm randomly selects the next element from a portion of the remaining unselected elements with the lowest cost to cardinality ratios to find a feasible solution, and further comprising:

applying a local search algorithm to the feasible solution found by the greedy construction algorithm to obtain a first least cost feasible solution,

forming a pool of elite feasible solutions,

applying a path-relinking algorithm between the first feasible solution and a second feasible solution selected from the pool of elite feasible solutions,

adding the solution found by path-relinking to the elite pool of feasible solutions if it satisfies predetermined cost and diversity tests, and

selecting the least cost feasible solution in the elite pool as the one used to select parameters for the next iteration of the subgradient optimization algorithm.

6. A computer system operable with computer-usable program code for designing a minimum cost network with k-fold redundant coverage of objects to be served by the network, by starting from a collection of potential network elements each having a defined cost value and each having a defined coverage parameter, and by transforming these potential network elements into a set of network elements that provides the required k-fold redundant coverage at approximate minimum cost, comprising:

means for providing a k-set coverage formulation with the cost values and the object coverage parameter values of the collection of potential network elements;

means for providing a Lagrangian relaxation of the k-set coverage formulation;

means for applying an iterative subgradient optimization algorithm to the Lagrangian relaxation;

means for determining an initial solution found by an iteration of the subgradient optimization algorithm;

means for applying a greedy construction algorithm to add selected elements to the initial solution to form a feasible solution by

determining the cardinality of an unselected element as the number of objects not in previously selected elements that the unselected element covers,

selecting from the remaining unselected elements based on the ratio of cost to cardinality, and

repeating the determining and selecting steps until a feasible solution has been obtained,

means for using the feasible solution to select parameters for the next iteration of the subgradient optimization algorithm, and

means for continuing to perform iterations until a set of network elements having an approximate minimum cost solution is identified, whereby the network elements which are identified in the approximate minimum cost solution from the collection of potential network elements will produce a network design with the required redundancy and approximate minimum cost.

7. The system claimed in claim 6 wherein the subgradient optimization algorithm updates Lagrangian multipliers using a step size, and wherein the feasible solution is used to adjust the step size at each subgradient optimization iteration.

8. The system claimed in claim 6 further comprising:

means for evaluating each element in the feasible solution constructed with the greedy construction algorithm in decreasing order of its cost to determine whether if the element is removed the resulting solution remains a feasible solution, and means for removing the element if the resulting solution remains a feasible solution.

9. The system claimed in claim 6 wherein the means for applying the greedy construction algorithm selects from the remaining unselected elements the one with the lowest ratio of cost to cardinality.

10. The system claimed in claim 6 wherein the means for applying the greedy construction algorithm randomly selects the next element from a portion of the remaining unselected elements with the lowest cost to cardinality ratios to find a feasible solution, and further comprising:

means for applying a local search algorithm to the feasible solution found by the greedy construction algorithm to obtain a first least cost feasible solution,

means for forming a pool of elite feasible solutions,

means for applying a path-relinking algorithm between the first feasible solution and a second feasible solution selected from the pool of elite feasible solutions,

means for adding the solution found by path-relinking to the elite pool of feasible solutions if it satisfies predetermined cost and diversity tests, and

means for selecting the least cost feasible solution in the elite pool as the one used to select parameters for the next iteration of the subgradient optimization algorithm.

11. The method claimed in claim 1 wherein the network is a cellular communications network, the objects served by the network are cellular telephone customers, the potential network elements are cellular antennas, the defined cost value is the associated cost of a potential cellular antenna, the defined object coverage parameter is the associated cellular customer coverage of a potential cellular antenna, the k-fold redundant coverage of objects is a desired multiple coverage of cellular customers by cellular antennas to be provided in the designed network, and the approximate minimum cost network design is a cellular antenna network with required redundant coverage and approximate minimum cost.

12. The method claimed in claim 1 wherein the network is a network of modem locations for telephone ISP access, the potential network elements are modems, the objects served by the network are ISP customers who access the modems with telephones, the defined cost value is the associated cost of a modem, the defined object coverage parameter is the associated ISP customer coverage of a potential modem, the k-fold redundant coverage of objects is desired multiple coverage of ISP customers by modems to be provided in the designed network, and the approximate minimum cost network design is a modem network with required redundant coverage and approximate minimum cost.

13. The method claimed in claim 1 wherein the network is a network of DSL hubs for Internet access, the potential network elements are DSL hubs, the objects served by the network are customer who access the Internet through DSL hubs, the defined cost value is the associated cost of a potential DSL hub, the defined object coverage parameter is the associated transmission range of a potential DSL hub, the k-fold redundant coverage of objects is desired multiple coverage of customers by DSL hubs to be provided in the designed network, and the approximate minimum cost network design is a DSL hub network with required redundant coverage and approximate minimum cost.

14. The system claimed in claim 6 wherein the network is a cellular communications network, the objects served by the network are cellular telephone customers, the potential network elements are cellular antennas, the defined cost value is the associated cost of a potential cellular antenna, the defined object coverage parameter is the associated cellular customer coverage of a potential cellular antenna, the k-fold redundant coverage of objects is a desired multiple coverage of cellular customers by cellular antennas to be provided in the designed network, and the approximate minimum cost network design is a cellular antenna network with required redundant coverage and approximate minimum cost.

15. The system claimed in claim 6 wherein the network is a network of modem locations for telephone ISP access, the potential network elements are modems, the objects served by the network are ISP customers who access the modems with telephones, the defined cost value is the associated cost of a modem, the defined object coverage parameter is the associated ISP customer coverage of a potential modem, the k-fold redundant coverage of objects is desired multiple coverage of ISP customers by modems to be provided in the designed network, and the approximate minimum cost network design is a modem network with required redundant coverage and approximate minimum cost.

16. The system claimed in claim 6 wherein the network is a network of DSL hubs for Internet access, the potential network elements are DSL hubs, the objects served by the network are customer who access the Internet through DSL hubs, the defined cost value is the associated cost of a potential DSL hub, the defined object coverage parameter is the associated transmission range of a potential DSL hub, the k-fold redundant coverage of objects is desired multiple coverage of customers by DSL hubs to be provided in the designed network, and the approximate minimum cost network design is a DSL hub network with required redundant coverage and approximate minimum cost.