Capacitated Trees, Capacitated Routing, and Associated Polyhedra
We study the polyhedral structure of two related core combinatorial problems: the subtree cardinalityconstrained minimal spanning tree problem and the identical customer vehicle routing problem. For each of these problems, and for a forest relaxation of the minimal spanning tree problem, we introduc...
| 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/5194 |
| _version_ | 1826202622218993664 |
|---|---|
| author | Araque, Jésus Rafael Hall, Leslie A. Magnanti, Thomas L. |
| author_facet | Araque, Jésus Rafael Hall, Leslie A. Magnanti, Thomas L. |
| author_sort | Araque, Jésus Rafael |
| collection | MIT |
| description | We study the polyhedral structure of two related core combinatorial problems: the subtree cardinalityconstrained minimal spanning tree problem and the identical customer vehicle routing problem. For each of these problems, and for a forest relaxation of the minimal spanning tree problem, we introduce a number of new valid inequalities and specify conditions for ensuring when these inequalities are facets for the associated integer polyhedra. The inequalities are defined by one of several underlying support graphs: (i) a multistar, a "star" with a clique replacing the central vertex; (ii) a clique cluster, a collection of cliques intersecting at a single vertex, or more generally at a central" clique; and (iii) a ladybug, consisting of a multistar as a head and a clique as a body. We also consider packing (generalized subtour elimination) constraints, as well as several variants of our basic inequalities, such as partial multistars, whose satellite vertices need not be connected to all of the central vertices. Our development highlights the relationship between the capacitated tree and capacitated forest polytopes and a so-called path-partitioning polytope,and shows how to use monotone polytopes and a set of simple exchange arguments to prove that valid inequalities are facets. |
| first_indexed | 2024-09-23T12:10:48Z |
| format | Working Paper |
| id | mit-1721.1/5194 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:10:48Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/51942019-04-10T08:59:27Z Capacitated Trees, Capacitated Routing, and Associated Polyhedra Araque, Jésus Rafael Hall, Leslie A. Magnanti, Thomas L. We study the polyhedral structure of two related core combinatorial problems: the subtree cardinalityconstrained minimal spanning tree problem and the identical customer vehicle routing problem. For each of these problems, and for a forest relaxation of the minimal spanning tree problem, we introduce a number of new valid inequalities and specify conditions for ensuring when these inequalities are facets for the associated integer polyhedra. The inequalities are defined by one of several underlying support graphs: (i) a multistar, a "star" with a clique replacing the central vertex; (ii) a clique cluster, a collection of cliques intersecting at a single vertex, or more generally at a central" clique; and (iii) a ladybug, consisting of a multistar as a head and a clique as a body. We also consider packing (generalized subtour elimination) constraints, as well as several variants of our basic inequalities, such as partial multistars, whose satellite vertices need not be connected to all of the central vertices. Our development highlights the relationship between the capacitated tree and capacitated forest polytopes and a so-called path-partitioning polytope,and shows how to use monotone polytopes and a set of simple exchange arguments to prove that valid inequalities are facets. 2004-05-28T19:27:25Z 2004-05-28T19:27:25Z 1990-11 Working Paper http://hdl.handle.net/1721.1/5194 en_US Operations Research Center Working Paper;OR 232-90 1744 bytes 3642903 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Araque, Jésus Rafael Hall, Leslie A. Magnanti, Thomas L. Capacitated Trees, Capacitated Routing, and Associated Polyhedra |
| title | Capacitated Trees, Capacitated Routing, and Associated Polyhedra |
| title_full | Capacitated Trees, Capacitated Routing, and Associated Polyhedra |
| title_fullStr | Capacitated Trees, Capacitated Routing, and Associated Polyhedra |
| title_full_unstemmed | Capacitated Trees, Capacitated Routing, and Associated Polyhedra |
| title_short | Capacitated Trees, Capacitated Routing, and Associated Polyhedra |
| title_sort | capacitated trees capacitated routing and associated polyhedra |
| url | http://hdl.handle.net/1721.1/5194 |
| work_keys_str_mv | AT araquejesusrafael capacitatedtreescapacitatedroutingandassociatedpolyhedra AT halllesliea capacitatedtreescapacitatedroutingandassociatedpolyhedra AT magnantithomasl capacitatedtreescapacitatedroutingandassociatedpolyhedra |