Using continuous nonlinear relaxations to solve constrained maximum-entropy sampling problems
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 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 which were heretofore intractable.
Year of publication: |
1997-04-01
|
---|---|
Authors: | ANSTREICHER, Kurt M. ; FAMPA, Marcia ; LEE, Jon ; WILLIAMS, Joy |
Institutions: | Center for Operations Research and Econometrics (CORE), École des Sciences Économiques de Louvain |
Saved in:
freely available
Saved in favorites
Similar items by person
-
Maximum-entropy remote sampling
ANSTREICHER, Kurt M.,
-
Using continuous nonlinear relaxations to solve constrained maximum-entropy sampling problems
ANSTREICHER, Kurt M.,
-
Using continuous nonlinear relaxations to solve constrained maximum-entropy sampling problems
ANSTREICHER, Kurt M.,
- More ...