We study the computational complexity of finding extremal principal minors of a positive definite matrix. In particular, we focus on the NP-hard problem of maximizing the determinant over the set of principal submatrices of a given order. This problem arises in the area of statistical design,...

The boolean quadric polytope Pn is the convex hull in d:= (n;l) dimensions of the binary solutions of XiXj = Yij, for all i j in N := {l, 2, ... , n} (n ~ 2). The polytope is naturally modeled by a somewhat larger polytope; namely, Qn the solution set of Yij :5 Xi, Yij :5 Xj, X, + Xj :5 1 + Yij,...

We consider a new nonlinear relaxation for the Constrained Maximum-Entropy Sampling Prob- lem - the problem of choosing the s x s principal submatrix with maximal determinant from a given n x n positive definite matrix, subject to linear constraints. We implement a branch-and- bound algorithm...

We present new facets for the linear ordering polytope. These new facets generalize facets induced by sub graphs called fences, introduced by Grotschel, Junger and Reinelt (1985), and augmented fences, introduced by McLennan (1990). One novelty of the facets introduced here is that each sub...