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

Kurt M. Anstreicher, Marcia Fampa, Jon Lee and Joy Williams
Additional contact information
Kurt M. Anstreicher: Department of Management Sciences, University of Iowa, United States
Marcia Fampa: Department of Systmes Engineering and Computer Sciences, Federal University of Rio de Janeiro
Jon Lee: Department of Mathematics, University of Kentucky
Joy Williams: Department of Mathematics, University of Kentucky

No 1997029, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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

Date: 1997-04-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1997.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1997029

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().