A Dual-Based Algorithm for Multi-Level Network Design
Given an undirected network with L possible facility types for each edge, and a partition of the nodes into L levels, the Multi-level Network Design (MLND) problem seeks a fixed cost minimizing design that spans all the nodes and connects the nodes at each level by facilities of the corresponding or...
| Main Authors: | , , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/5218 |
| _version_ | 1826203524406444032 |
|---|---|
| author | Balakrishnan, Anantaram Magnanti, Thomas L. Mirchandani, Prakash |
| author_facet | Balakrishnan, Anantaram Magnanti, Thomas L. Mirchandani, Prakash |
| author_sort | Balakrishnan, Anantaram |
| collection | MIT |
| description | Given an undirected network with L possible facility types for each edge, and a partition of the nodes into L levels, the Multi-level Network Design (MLND) problem seeks a fixed cost minimizing design that spans all the nodes and connects the nodes at each level by facilities of the corresponding or higher type. This problem generalizes the well-known Steiner network problem and the hierarchical network design problem, and has applications in telecommunication, transportation, and electric power distribution network design. In a companion paper we introduced the problem, studied alternative model formulations, and analyzed the worst-case performance of heuristics based on Steiner network and spanning tree solutions. This paper develops and tests a dual-based algorithm for the Multi-level Network Design (MLND) problem. The method first performs problem preprocessing to fix certain design variables, and then applies a dual ascent procedure to generate upper and lower bounds on the optimal value. We report extensive computational results on large, random networks (containing up to 500 nodes, and 5000 edges) with varying cost structures. The integer programming formulation of the largest of these problems has 20,000 integer variables and over 5 million constraints. Our tests indicate that the dualbased algorithm is very effective, producing solutions guaranteed to be within 0 to 0.9% of optimality. |
| first_indexed | 2024-09-23T12:38:24Z |
| format | Working Paper |
| id | mit-1721.1/5218 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:38:24Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/52182019-04-12T08:16:07Z A Dual-Based Algorithm for Multi-Level Network Design Balakrishnan, Anantaram Magnanti, Thomas L. Mirchandani, Prakash Network design, integer programming, dual ascent algorithm Given an undirected network with L possible facility types for each edge, and a partition of the nodes into L levels, the Multi-level Network Design (MLND) problem seeks a fixed cost minimizing design that spans all the nodes and connects the nodes at each level by facilities of the corresponding or higher type. This problem generalizes the well-known Steiner network problem and the hierarchical network design problem, and has applications in telecommunication, transportation, and electric power distribution network design. In a companion paper we introduced the problem, studied alternative model formulations, and analyzed the worst-case performance of heuristics based on Steiner network and spanning tree solutions. This paper develops and tests a dual-based algorithm for the Multi-level Network Design (MLND) problem. The method first performs problem preprocessing to fix certain design variables, and then applies a dual ascent procedure to generate upper and lower bounds on the optimal value. We report extensive computational results on large, random networks (containing up to 500 nodes, and 5000 edges) with varying cost structures. The integer programming formulation of the largest of these problems has 20,000 integer variables and over 5 million constraints. Our tests indicate that the dualbased algorithm is very effective, producing solutions guaranteed to be within 0 to 0.9% of optimality. 2004-05-28T19:28:37Z 2004-05-28T19:28:37Z 1991-12 Working Paper http://hdl.handle.net/1721.1/5218 en_US Operations Research Center Working Paper;OR 261-91 2308080 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Network design, integer programming, dual ascent algorithm Balakrishnan, Anantaram Magnanti, Thomas L. Mirchandani, Prakash A Dual-Based Algorithm for Multi-Level Network Design |
| title | A Dual-Based Algorithm for Multi-Level Network Design |
| title_full | A Dual-Based Algorithm for Multi-Level Network Design |
| title_fullStr | A Dual-Based Algorithm for Multi-Level Network Design |
| title_full_unstemmed | A Dual-Based Algorithm for Multi-Level Network Design |
| title_short | A Dual-Based Algorithm for Multi-Level Network Design |
| title_sort | dual based algorithm for multi level network design |
| topic | Network design, integer programming, dual ascent algorithm |
| url | http://hdl.handle.net/1721.1/5218 |
| work_keys_str_mv | AT balakrishnananantaram adualbasedalgorithmformultilevelnetworkdesign AT magnantithomasl adualbasedalgorithmformultilevelnetworkdesign AT mirchandaniprakash adualbasedalgorithmformultilevelnetworkdesign AT balakrishnananantaram dualbasedalgorithmformultilevelnetworkdesign AT magnantithomasl dualbasedalgorithmformultilevelnetworkdesign AT mirchandaniprakash dualbasedalgorithmformultilevelnetworkdesign |