Journal article
Maximum-entropy sampling and the Boolean quadric polytope
Journal of global optimization, Vol.72(4), pp.603-618
12/2018
DOI: 10.1007/s10898-018-0662-x
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.
Details
- Title: Subtitle
- Maximum-entropy sampling and the Boolean quadric polytope
- Creators
- Kurt M Anstreicher
- Resource Type
- Journal article
- Publication Details
- Journal of global optimization, Vol.72(4), pp.603-618
- DOI
- 10.1007/s10898-018-0662-x
- ISSN
- 0925-5001
- eISSN
- 1573-2916
- Language
- English
- Date published
- 12/2018
- Academic Unit
- Business Analytics; Industrial and Systems Engineering; Computer Science
- Record Identifier
- 9984065709102771
Metrics
13 Record Views