Continuous relaxations for Constrained Maximum-Entropy Sampling

Kurt M. Anstreicher; Marcia Fampa; Jon Lee; Joy Williams

doi:10.1007/3-540-61310-2_18

Back

Continuous relaxations for Constrained Maximum-Entropy Sampling

Book chapter

Peer reviewed

Continuous relaxations for Constrained Maximum-Entropy Sampling

Kurt M. Anstreicher, Marcia Fampa, Jon Lee and Joy Williams

Integer Programming and Combinatorial Optimization, pp.234-248

Lecture Notes in Computer Science, Springer Berlin Heidelberg

06/03/2005

DOI: 10.1007/3-540-61310-2_18

View Online

Abstract

We consider a new nonlinear relaxation for the Constrained Maximum Entropy Sampling Problem — the problem of choosing the s × s principal submatrix with maximal determinant from a given n × 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.

Continuous Relaxation

Dual Solution

Principal Submatrix

Relative Interior

Unconstrained Case

Details

Title: Subtitle: Continuous relaxations for Constrained Maximum-Entropy Sampling
Creators: Kurt M. Anstreicher - University of Iowa
Marcia Fampa - Universidade Federal do Rio de Janeiro
Jon Lee - University of Kentucky
Joy Williams - University of Kentucky
Resource Type: Book chapter
Publication Details: Integer Programming and Combinatorial Optimization, pp.234-248
Publisher: Springer Berlin Heidelberg; Berlin, Heidelberg
Series: Lecture Notes in Computer Science
DOI: 10.1007/3-540-61310-2_18
eISSN: 1611-3349
ISSN: 0302-9743
Language: English
Date published: 06/03/2005
Academic Unit: Industrial and Systems Engineering; Computer Science; Business Analytics
Record Identifier: 9984380429102771

Metrics

7 Record Views