Using continuous nonlinear relaxations to solve constrained maximum-entropy sampling problems

We consider a new nonlinear relaxation for the Constrained Maximum-Entropy Sampling Problem – the problem of choosing the s × s principal submatrix with maximal determinant from a given n × n positive definite matrix, subject to linear constraints. We implement a branch-and-bound algorithm for the problem, using the new relaxation. The performance on test problems is far superior to a previous implementation using an eigenvalue-based relaxation. A parallel implementation of the algorithm exhibits approximately linear speed-up for up to 8 processors, and has successfully solved problem instances that were heretofore intractable.