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