Designing minimum total cost networks using iterative rounding approximation methods

An approximation method for designing a minimum total cost network by selecting from a collection of available network elements which include nodes and links connecting the nodes, comprising:

• selecting graph edges to correspond to the available links;
• assigning edge costs that correspond to the link costs;
• selecting graph vertices to correspond to nodes;
• selecting pairs of vertices that are required to be in the network;
• assigning connectivity requirements for all required pairs of vertices;
• assigning penalty costs to the required pairs if their connectivity requirements are not satisfied;
• constructing an LP relaxation incorporating values for edge costs, pair requirements, connectivity requirements and penalty costs and having coefficients for edge costs and penalty costs as variables;
• finding an optimal basic feasible solution to the LP;
• applying a selection criterion to pair connectivities and edges in the optimal basic solution;
• paying a penalty cost for each pair connectivity selected according to the selection criterion and including the penalty cost in the network solution;
• including each edge selected according to the selection criterion in the network solution;
• forming a residual graph including all remaining required pairs with unpaid connectivity requirements and including all edges;
• constructing a residual LP for the residual graph in which edge coefficients for edges selected according to the selection criterion are set to 1 and other edge coefficients are variables;
• iteratively repeating the previous steps from the finding step to the constructing step until all connectivity requirements of the required pairs are determined to be satisfied;
• and
• selecting network links corresponding to at least some edges identified in the network solution to include in the minimum cost network.

A system for designing a minimum cost network from defined available network elements having values for cost, required pairs, connectivity requirements and penalty costs for insufficient connectivity by selecting from these available elements, comprising:

• means for providing an LP relaxation for a graph having edges and vertices with values corresponding to those of the available network elements;
• means for finding an optimal basic solution to the LP;
• means for applying a selection criterion to penalty costs and edge costs identified in the optimal basic solution and including the selected penalty costs and edges in the minimum cost network;
• means for providing a residual LP relaxation including remaining pairs with unsatisfied connectivity and edges;
• and
• means for fixing selected edge coefficient values to 1 in the residual LP;
• means for repeating the steps of the method to include additional penalty costs and edge costs in the minimum cost network until all connectivity requirements are satisfied.

A computer program product for causing a computer to design a minimum total cost network from defined available network elements having values for cost, required pairs, connectivity requirements and penalty costs for insufficient connectivity by selecting from these available elements, comprising:

• computer readable program code means for providing an LP relaxation for a graph having edges and vertices with values corresponding to those of the available network elements;
• computer readable program code means for finding an optimal basic solution to the LP;
• computer readable program code means for applying a selection criterion to penalty costs and edge costs identified in the optimal basic solution and including the selected penalty costs and edges in the minimum cost network;
• computer readable program code means for providing a residual LP relaxation including remaining pairs with unsatisfied connectivity and edges;
• and
• computer readable program code means for fixing selected edge coefficient values to 1 in the residual LP;
• computer readable program code means for repeating the steps of the method to include additional penalty costs and edge costs in the minimum cost network until all connectivity requirements are satisfied.

A minimum cost network assembled from defined available network elements having values for cost, required pairs, connectivity requirements and penalty costs for insufficient connectivity by selecting from these available elements using a method comprising:

• constructing an LP relaxation for a graph having edges and vertices with values corresponding to those of the available network elements;
• finding an optimal basic solution to the LP;
• applying a selection criterion to penalty costs and edge costs identified in the optimal basic solution and including the selected penalty costs and edges in the minimum cost network;
• constructing a residual LP relaxation including remaining pairs with unsatisfied connectivity and edges;
• and
• fixing selected edge coefficient values to 1 in the residual LP;
• repeating the steps of the method to include additional penalty costs and edge costs in the minimum cost network until all connectivity requirements are satisfied;
• selecting from the available network elements at least some that correspond to edges selected for inclusion in the minimum cost network.