The equipartition polytope. I: Formulations, dimension and basic facets
Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Boolean programming (90C09) Integer programming (90C10) Quadratic programming (90C20) Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90) Clustering in the social and behavioral sciences (91C20)
The quadratic problem \[ \min H=\sum^{n-1}_{i=1}\sum^{n}_{j=i+1}- w_{ij}s_ is_ j\quad s.t.\quad \sum^{n}_{i=1}s_ i=0,\quad s_ i\in \{1,-1\},\quad i=1,...,n \] arising in some physical framework can be reduced to the following equipartition problem: Given a graph \(G=(V,E)\) with edge weights \(w_{ij}\), (i,j)\(\in E\), find a subset \(U\subset V\) with \(| U| =[| V|]\) such that \[ w(U)=\sum_{i\in U}\sum_{j\in V| U}w_{ij} \] is as small as possible. An equicut is a feasible solution of this problem and the equicut polytope Q(G) is the convex hull of the incidence vectors of equicuts in G. The authors give some integer programming formulations, study the dimension of Q(G) and describe some basic classes of fact inducing inequalities. [For part II see the authors, ibid. 49, No.1, 71-90 (1990; Zbl 0718.90093).]
- A polynomial characterization of some graph partitioning problems
- A solvable case of quadratic 0-1 programming
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- An Efficient Heuristic Procedure for Partitioning Graphs
- Bottleneck extrema
- Facets of the Bipartite Subgraph Polytope
- scientific article; zbMATH DE number 3756243 (Why is no real title available?)
- scientific article; zbMATH DE number 3345048 (Why is no real title available?)
- scientific article; zbMATH DE number 3409134 (Why is no real title available?)
- On the cut polytope
- On the magnetisation of the ground states in two dimensional Ising spin glasses
- Some New Matroids on Graphs: Cut Sets and the Max Cut Problem
- Facets for the cut cone. I
- Facets for the cut cone. II: Clique-web inequalities
- Min-cut clustering
- A computational study of graph partitioning
- 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
- Hamiltonian path and symmetric travelling salesman polytopes
- Formulations and valid inequalities of the node capacitated graph partitioning problem
- Application of cut polyhedra. I
- Some new classes of facets for the equicut polytope
- A projection technique for partitioning the nodes of a graph
- An overview of graph covering and partitioning
- 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
- The equipartition polytope. II: Valid inequalities and facets
- Engineering branch-and-cut algorithms for the equicut problem
- Equipartition sets of hypercubes. II
- scientific article; zbMATH DE number 432993 (Why is no real title available?)
- Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables
- A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
- On the polyhedral structure of uniform cut polytopes
- From equipartition to uniform cut polytopes: extended polyhedral results
- Size-constrained graph partitioning polytopes
- Equipartite polytopes
- Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
- \texttt{CP-Lib}: benchmark instances of the clique partitioning problem
- Optimizing connected components graph partitioning with minimum size constraints using integer programming and spectral clustering techniques
This page was built for publication: The equipartition polytope. I: Formulations, dimension and basic facets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2639779)
