The Convex Hull of Two Core Capacitated Network Design Problems
The network loading problem (NLP) is a specialized capacitated network design problem in which prescribed point-to-point demand between various pairs of nodes of a network must be met by installing (loading) a capacitated facility. We can load any number of units of the facility on each of the arcs...
| 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/5164 |
| _version_ | 1826207204469899264 |
|---|---|
| author | Magnanti, Thomas L. Mirchandani, Prakash Vachani, Rita |
| author_facet | Magnanti, Thomas L. Mirchandani, Prakash Vachani, Rita |
| author_sort | Magnanti, Thomas L. |
| collection | MIT |
| description | The network loading problem (NLP) is a specialized capacitated network design problem in which prescribed point-to-point demand between various pairs of nodes of a network must be met by installing (loading) a capacitated facility. We can load any number of units of the facility on each of the arcs at a specified arc dependent cost. The problem is to determine the number of facilities to be loaded on the arcs that will satisfy the given demand at minimum cost. This paper studies two core subproblems of the NLP. The first problem, motivated by a Lagrangian relaxation approach for solving the problem, considers a multiple commodity, single arc capacitated network design problem. The second problem is a three node network; this specialized network arises in larger networks if we aggregate nodes. In both cases, we develop families of facets and completely characterize the convex hull of feasible solutions to the integer programming formulation of the problems. These results in turn strengthen the formulation of the NLP. |
| first_indexed | 2024-09-23T13:45:40Z |
| format | Working Paper |
| id | mit-1721.1/5164 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:45:40Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/51642019-04-10T15:18:07Z The Convex Hull of Two Core Capacitated Network Design Problems Magnanti, Thomas L. Mirchandani, Prakash Vachani, Rita Convex hull, Facets, Network design, Capacitated facilities. The network loading problem (NLP) is a specialized capacitated network design problem in which prescribed point-to-point demand between various pairs of nodes of a network must be met by installing (loading) a capacitated facility. We can load any number of units of the facility on each of the arcs at a specified arc dependent cost. The problem is to determine the number of facilities to be loaded on the arcs that will satisfy the given demand at minimum cost. This paper studies two core subproblems of the NLP. The first problem, motivated by a Lagrangian relaxation approach for solving the problem, considers a multiple commodity, single arc capacitated network design problem. The second problem is a three node network; this specialized network arises in larger networks if we aggregate nodes. In both cases, we develop families of facets and completely characterize the convex hull of feasible solutions to the integer programming formulation of the problems. These results in turn strengthen the formulation of the NLP. 2004-05-28T19:26:00Z 2004-05-28T19:26:00Z 1990-06 Working Paper http://hdl.handle.net/1721.1/5164 en_US Operations Research Center Working Paper;OR 217-90 1716245 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Convex hull, Facets, Network design, Capacitated facilities. Magnanti, Thomas L. Mirchandani, Prakash Vachani, Rita The Convex Hull of Two Core Capacitated Network Design Problems |
| title | The Convex Hull of Two Core Capacitated Network Design Problems |
| title_full | The Convex Hull of Two Core Capacitated Network Design Problems |
| title_fullStr | The Convex Hull of Two Core Capacitated Network Design Problems |
| title_full_unstemmed | The Convex Hull of Two Core Capacitated Network Design Problems |
| title_short | The Convex Hull of Two Core Capacitated Network Design Problems |
| title_sort | convex hull of two core capacitated network design problems |
| topic | Convex hull, Facets, Network design, Capacitated facilities. |
| url | http://hdl.handle.net/1721.1/5164 |
| work_keys_str_mv | AT magnantithomasl theconvexhulloftwocorecapacitatednetworkdesignproblems AT mirchandaniprakash theconvexhulloftwocorecapacitatednetworkdesignproblems AT vachanirita theconvexhulloftwocorecapacitatednetworkdesignproblems AT magnantithomasl convexhulloftwocorecapacitatednetworkdesignproblems AT mirchandaniprakash convexhulloftwocorecapacitatednetworkdesignproblems AT vachanirita convexhulloftwocorecapacitatednetworkdesignproblems |