Optimization Online


Maximum-Entropy Sampling and the Boolean Quadric Polytope

Kurt Anstreicher(kurt-anstreicher***at***uiowa.edu)

Abstract: We consider a bound for the maximum-entropy sampling problem (MESP) that is based on solving a max-det problem over a relaxation of the Boolean Quadric Polytope (BQP). This approach to MESP was first suggested by Christoph Helmberg over 15 years ago, but has apparently never been further elaborated or computationally investigated. We find that the use of a relaxation of BQP that imposes semidefiniteness and a small number of equality constraints gives excellent bounds on many benchmark instances. These bounds can be further tightened by imposing additional inequality constraints that are valid for the BQP. Duality information associated with the BQP-based bounds can be used to fix variables to 0/1 values, and also as the basis for the implementation of a "strong branching" strategy. A branch-and-bound algorithm using the BQP-based bounds solves some benchmark instances of MESP to optimality for the first time.

Keywords: Maximum-entropy sampling, semidefinite programming, semidefinite optimization, Boolean quadric polytope

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Applications -- Science and Engineering (Statistics )

Citation: Dept. of Management Sciences, University of Iowa, December 2017

Download: [PDF]

Entry Submitted: 12/14/2017
Entry Accepted: 12/14/2017
Entry Last Modified: 12/14/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society