The equipartition polytope. II: Valid inequalities and facets

DOI10.1007/BF01588779MaRDI QIDQ2639780zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 1990

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

Full work available at URL https://doi.org/10.1007/bf01588779

zbMATH Keywords

cut polytopeequicut polytopeequipartition polytopefacet inducing inequalities

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Boolean programming (90C09) Integer programming (90C10) Quadratic programming (90C20) Programming involving graphs or networks (90C35)

Review text

[For part I see the authors, ibid. 49, No.1, 49-70 (1990; Zbl 0718.90092).] In this second part further facet inducing inequalities of the equicut polytope are described.

Cites work

• Facets of the Bipartite Subgraph Polytope
• On the cut polytope
• The equipartition polytope. I: Formulations, dimension and basic facets

Cited in

(24)

• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Min-cut clustering
• Cardinality constrained Boolean quadratic polytope
• A branch-and-cut algorithm for the equicut problem
• Solution of large weighted equicut problems
• Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Application of cut polyhedra. I
• Facets of the \(k\)-partition polytope
• Some new classes of facets for the equicut polytope
• Political districting to minimize cut edges
• The partition problem
• A polyhedral approach for a constrained quadratic 0-1 problem
• LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
• Facet-defining inequalities for the simple graph partitioning polytope
• Engineering branch-and-cut algorithms for the equicut problem
• Equipartition sets of hypercubes. II
• On the polyhedral structure of uniform cut polytopes
• Valid inequalities and cutting planes for some polytopes
• From equipartition to uniform cut polytopes: extended polyhedral results
• Size-constrained graph partitioning polytopes
• The inequicut cone
• Optimizing connected components graph partitioning with minimum size constraints using integer programming and spectral clustering techniques
• A branch-and-cut algorithm for the partitioning-hub location-routing problem

This page was built for publication: The equipartition polytope. II: Valid inequalities and facets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2639780)