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

Anstreicher, KM.;Fampa, M;Lee, Jon;Williams, J.
(1999) Mathematical Programming — Vol. 85, n° 2, p. 221-240 (1999)

Files

pdfdocument.pdf
  • Restricted Access
  • Adobe PDF
  • 139.77 KB
No access

Details

Authors
  • Anstreicher, KM.
    Author
  • Fampa, M
    Author
  • Lee, JonUniversity of Kentucky, Lexington
    Author
  • Williams, J.
    Author
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Anstreicher, KM., Fampa, M., Lee, J., & Williams, J. (1999). Using continuous nonlinear relaxations to solve constrained maximum-entropy sampling problems. Mathematical Programming, 85(2), 221-240. https://doi.org/10.1007/s101070050055 (Original work published 1999)