On the partial order polytope of a digraph

DOI10.1007/BF02592097zbMath0848.90105MaRDI QIDQ1915807

Rudolf Müller

Publication date: 24 October 1996

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

digraphvalid inequalitiespolyhedral combinatoricspolynomial separation algorithmpartial order polytopeclique partitioning polytopeflexible manufacturing problemmaximum weighted acyclic subdigraph problemmaximum weighted linear ordering problemtransitive acyclic arc sets

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial optimization (90C27)

Related Items (12)

The clique partitioning problem: Facets and patching facets ⋮ Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables ⋮ Derivations of large classes of facet defining inequalities of the weak order polytope using ranking structures ⋮ Optimizing the Layout of Proportional Symbol Maps: Polyhedra and Computation ⋮ A polyhedral study of lifted multicuts ⋮ Facets from gadgets ⋮ Arc-based integer programming formulations for three variants of proportional symbol maps ⋮ Exact algorithms for cluster editing: Evaluation and experiments ⋮ Multiprocessor scheduling under precedence constraints: polyhedral results ⋮ Primary facets of order polytopes ⋮ Optimal facility layout design ⋮ A combinatorial study of partial order polytopes

Uses Software

• LOLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Facets of the clique partitioning polytope
• A cutting plane algorithm for a clustering problem
• Induced binary probabilities and the linear ordering polytope: A status report
• Geometric algorithms and combinatorial optimization
• More facets from fences for linear ordering and acyclic subgraph polytopes
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• The partition problem
• A note on small linear-ordering polytopes
• Edmonds polytopes and a hierarchy of combinatorial problems
• On the acyclic subgraph polytope
• Facets of the linear ordering polytope
• Clique-Web Facets for Multicut Polytopes
• On the cut polytope
• Binary Probabilities Induced by Rankings

This page was built for publication: On the partial order polytope of a digraph