The equipartition polytope. I: Formulations, dimension and basic facets (Q2639779)

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).]