Transitive Packing: A Unifying Concept in Combinatorial Optimization
This paper attempts to give a better understanding of the facial structure of previously separately investigated polyhedra. It introduces the notion of transitive packing and the transitive packing polytope. Polytopes that turn out to be special cases of the transitive packing polytope are, among ot...
| 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/5412 |
| _version_ | 1811090729225682944 |
|---|---|
| author | Schulz, Andreas S. Müller, Rudolf |
| author_facet | Schulz, Andreas S. Müller, Rudolf |
| author_sort | Schulz, Andreas S. |
| collection | MIT |
| description | This paper attempts to give a better understanding of the facial structure of previously separately investigated polyhedra. It introduces the notion of transitive packing and the transitive packing polytope. Polytopes that turn out to be special cases of the transitive packing polytope are, among others, the node packing polytope, the acyclic subdigraph polytope, the bipartite subgraph polytope, the planar subgraph polytope, the clique partitioning polytope, the partition polytope, the transitive acyclic subdigraph polytope, the interval order polytope, and the relatively transitive subgraph polytope. We give cutting plane proofs for several rich classes of valid inequalities of the transitive packing polytope,in this way introducing generalized cycle, generalized clique, generalized antihole, generalized antiweb, and odd partition inequalities. These classes subsume several known classes of valid inequalities for several of the special cases and give also many new inequalities for several other special cases. For some of the classes we also prove a lower bound for their Gomory-Chvdtal rank. Finally, we relate the concept of transitive packing to generalized (set) packing and covering as well as to balanced and ideal matrices. |
| first_indexed | 2024-09-23T14:51:02Z |
| format | Working Paper |
| id | mit-1721.1/5412 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:51:02Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/54122019-04-12T08:16:40Z Transitive Packing: A Unifying Concept in Combinatorial Optimization Schulz, Andreas S. Müller, Rudolf This paper attempts to give a better understanding of the facial structure of previously separately investigated polyhedra. It introduces the notion of transitive packing and the transitive packing polytope. Polytopes that turn out to be special cases of the transitive packing polytope are, among others, the node packing polytope, the acyclic subdigraph polytope, the bipartite subgraph polytope, the planar subgraph polytope, the clique partitioning polytope, the partition polytope, the transitive acyclic subdigraph polytope, the interval order polytope, and the relatively transitive subgraph polytope. We give cutting plane proofs for several rich classes of valid inequalities of the transitive packing polytope,in this way introducing generalized cycle, generalized clique, generalized antihole, generalized antiweb, and odd partition inequalities. These classes subsume several known classes of valid inequalities for several of the special cases and give also many new inequalities for several other special cases. For some of the classes we also prove a lower bound for their Gomory-Chvdtal rank. Finally, we relate the concept of transitive packing to generalized (set) packing and covering as well as to balanced and ideal matrices. 2004-06-01T16:43:19Z 2004-06-01T16:43:19Z 1999-10 Working Paper http://hdl.handle.net/1721.1/5412 en_US Operations Research Center Working Paper;OR 346-00 2959101 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Schulz, Andreas S. Müller, Rudolf Transitive Packing: A Unifying Concept in Combinatorial Optimization |
| title | Transitive Packing: A Unifying Concept in Combinatorial Optimization |
| title_full | Transitive Packing: A Unifying Concept in Combinatorial Optimization |
| title_fullStr | Transitive Packing: A Unifying Concept in Combinatorial Optimization |
| title_full_unstemmed | Transitive Packing: A Unifying Concept in Combinatorial Optimization |
| title_short | Transitive Packing: A Unifying Concept in Combinatorial Optimization |
| title_sort | transitive packing a unifying concept in combinatorial optimization |
| url | http://hdl.handle.net/1721.1/5412 |
| work_keys_str_mv | AT schulzandreass transitivepackingaunifyingconceptincombinatorialoptimization AT mullerrudolf transitivepackingaunifyingconceptincombinatorialoptimization |