We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Using continuous nonlinear relaxations to solve. constrained maximum-entropy sampling problems.
- Authors
Anstreicher, Kurt M.; Fampa, Marcia; Lee, Jon; Williams, Joy
- Abstract
Abstract. 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.
- Subjects
MAXIMUM entropy method; NONLINEAR theories; RELAXATION methods (Mathematics); ALGORITHMS; EIGENVALUES
- Publication
Mathematical Programming, 1999, Vol 85, Issue 2, p221
- ISSN
0025-5610
- Publication type
Article
- DOI
10.1007/s101070050055