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

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 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,...

We survey some analytic methods of volume calculation and introduce a distance function for pairs of polytopes based on their volumes. We study the distance function in the context of three familiar settings of combinatorial optimization: (i) ChvatalGomory rounding, (ii) fixed charge problems,...

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 study thep olytopes of binary n-strings that encode (positive) integers that are not divisible by a particular positive integer p - the indivisibility polytopes, as well as the more general "clipped cubes". Also, we discuss a potential application to factoring. Finally, we present some...

For matroids representable over both GF[3] and GF[5], we provide a recipe for constructing an orientation

We develop and experiment with new upper bounds for the constrained maximum-entropy sampling problem. Our partition bounds are based on Fischer's inequality. Further new upper bounds combine the use of Fischer's inequality with previously developed bounds. We demonstrate this in detail by using...

Motivated by the NP-Hard problem of finding a minimum-weight balanced bipartition of an edge-weighted complete graph, we study the class of graphs having the same degrees as bipartite 'fur.an graphs. In particular, we establish a maximal set of linear equations satisfied by the counts of the...