The Multi-Network Design Problem
This paper studies a new multi-facility network synthesis problem, called the Multi-level Network Design (MLND) problem, that arises in the topological design of hierarchical communication, transportation, and electric power distribution networks whose nodes have varying levels of importance:the mor...
| Main Authors: | , , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5200 |
| _version_ | 1826207117782024192 |
|---|---|
| author | Balakrishnan, Anantaram Magnanti, Thomas L. Mirchandani, Prakash |
| author_facet | Balakrishnan, Anantaram Magnanti, Thomas L. Mirchandani, Prakash |
| author_sort | Balakrishnan, Anantaram |
| collection | MIT |
| description | This paper studies a new multi-facility network synthesis problem, called the Multi-level Network Design (MLND) problem, that arises in the topological design of hierarchical communication, transportation, and electric power distribution networks whose nodes have varying levels of importance:the more critical or higher level nodes require higher grade interconnections. Given an undirected network with L possible facility types for each edge, and a partition of the nodes into L levels, the MLND problem seeks a connected design that minimizes total fixed cost while spanning all the nodes, and connecting nodes at each level via facilities of the corresponding or higher type. This problem generalizes the well-known Steiner network problem and the hierarchical network design problem. In this paper, we describe alternative model formulations for this problem and analyze the worst-case performance for heuristics based upon Steiner and spanning tree computations. For one model that we consider, the heuristic worst-case bounds on the performance ratio are either 4/3 or the worst-case performance ratio p of the embedded Steiner tree heuristic. A companion paper develops and tests a dual ascent procedure that generates tight upper and lower bounds on the optimal value of the problem. Keywords: Network design, integer programming, valid inequalities, worstcase analysis of heuristics. |
| first_indexed | 2024-09-23T13:44:24Z |
| format | Working Paper |
| id | mit-1721.1/5200 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:44:24Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/52002019-04-12T13:40:49Z The Multi-Network Design Problem Balakrishnan, Anantaram Magnanti, Thomas L. Mirchandani, Prakash This paper studies a new multi-facility network synthesis problem, called the Multi-level Network Design (MLND) problem, that arises in the topological design of hierarchical communication, transportation, and electric power distribution networks whose nodes have varying levels of importance:the more critical or higher level nodes require higher grade interconnections. Given an undirected network with L possible facility types for each edge, and a partition of the nodes into L levels, the MLND problem seeks a connected design that minimizes total fixed cost while spanning all the nodes, and connecting nodes at each level via facilities of the corresponding or higher type. This problem generalizes the well-known Steiner network problem and the hierarchical network design problem. In this paper, we describe alternative model formulations for this problem and analyze the worst-case performance for heuristics based upon Steiner and spanning tree computations. For one model that we consider, the heuristic worst-case bounds on the performance ratio are either 4/3 or the worst-case performance ratio p of the embedded Steiner tree heuristic. A companion paper develops and tests a dual ascent procedure that generates tight upper and lower bounds on the optimal value of the problem. Keywords: Network design, integer programming, valid inequalities, worstcase analysis of heuristics. 2004-05-28T19:27:44Z 2004-05-28T19:27:44Z 1991-12 Working Paper http://hdl.handle.net/1721.1/5200 en_US Operations Research Center Working Paper;OR 262-91 2908776 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Balakrishnan, Anantaram Magnanti, Thomas L. Mirchandani, Prakash The Multi-Network Design Problem |
| title | The Multi-Network Design Problem |
| title_full | The Multi-Network Design Problem |
| title_fullStr | The Multi-Network Design Problem |
| title_full_unstemmed | The Multi-Network Design Problem |
| title_short | The Multi-Network Design Problem |
| title_sort | multi network design problem |
| url | http://hdl.handle.net/1721.1/5200 |
| work_keys_str_mv | AT balakrishnananantaram themultinetworkdesignproblem AT magnantithomasl themultinetworkdesignproblem AT mirchandaniprakash themultinetworkdesignproblem AT balakrishnananantaram multinetworkdesignproblem AT magnantithomasl multinetworkdesignproblem AT mirchandaniprakash multinetworkdesignproblem |