Valid Inequalities and Facets for the Steinger Problem in a Directed Graph
In this paper, we describe the facial structure of the steiner problem in a directed graph by formulating it as a set covering problem. We first characterize trivial facets and derive a necessary condition for nontrivial facets. We also introduce a class of valid inequalities with 0-1 coefficients a...
| Main Author: | |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/5223 |
| _version_ | 1811070919586611200 |
|---|---|
| author | Myung, Young-soo |
| author_facet | Myung, Young-soo |
| author_sort | Myung, Young-soo |
| collection | MIT |
| description | In this paper, we describe the facial structure of the steiner problem in a directed graph by formulating it as a set covering problem. We first characterize trivial facets and derive a necessary condition for nontrivial facets. We also introduce a class of valid inequalities with 0-1 coefficients and show when such inequalities define facets. |
| first_indexed | 2024-09-23T08:43:42Z |
| format | Working Paper |
| id | mit-1721.1/5223 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:43:42Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/52232019-04-14T07:17:58Z Valid Inequalities and Facets for the Steinger Problem in a Directed Graph Myung, Young-soo Steiner problem in a directed graph, valid inequalities, facets. In this paper, we describe the facial structure of the steiner problem in a directed graph by formulating it as a set covering problem. We first characterize trivial facets and derive a necessary condition for nontrivial facets. We also introduce a class of valid inequalities with 0-1 coefficients and show when such inequalities define facets. 2004-05-28T19:28:52Z 2004-05-28T19:28:52Z 1991-06 Working Paper http://hdl.handle.net/1721.1/5223 en_US Operations Research Center Working Paper;OR 253-91 1159153 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Steiner problem in a directed graph, valid inequalities, facets. Myung, Young-soo Valid Inequalities and Facets for the Steinger Problem in a Directed Graph |
| title | Valid Inequalities and Facets for the Steinger Problem in a Directed Graph |
| title_full | Valid Inequalities and Facets for the Steinger Problem in a Directed Graph |
| title_fullStr | Valid Inequalities and Facets for the Steinger Problem in a Directed Graph |
| title_full_unstemmed | Valid Inequalities and Facets for the Steinger Problem in a Directed Graph |
| title_short | Valid Inequalities and Facets for the Steinger Problem in a Directed Graph |
| title_sort | valid inequalities and facets for the steinger problem in a directed graph |
| topic | Steiner problem in a directed graph, valid inequalities, facets. |
| url | http://hdl.handle.net/1721.1/5223 |
| work_keys_str_mv | AT myungyoungsoo validinequalitiesandfacetsforthesteingerprobleminadirectedgraph |