On Computing with Some Convex Relaxations for the Maximum-Entropy Sampling Problem

Zhongzhu Chen (), Marcia Fampa () and Jon Lee ()
Additional contact information
Zhongzhu Chen: Industrial and Operations Engineering Department, University of Michigan, Ann Arbor, Michigan 48109
Marcia Fampa: Programa de Engenharia de Sistemas e Computação, COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, RJ 21941-901, Brazil
Jon Lee: Industrial and Operations Engineering Department, University of Michigan, Ann Arbor, Michigan 48109

INFORMS Journal on Computing, 2023, vol. 35, issue 2, 368-385

Abstract: Based on a factorization of an input covariance matrix, we define a mild generalization of an upper bound of Nikolov and of Li and Xie for the NP-hard constrained maximum-entropy sampling problem ( CMESP ). We demonstrate that this factorization bound is invariant under scaling and independent of the particular factorization chosen. We give a variable-fixing methodology that could be used in a branch-and-bound scheme based on the factorization bound for exact solution of CMESP , and we demonstrate that its ability to fix is independent of the factorization chosen. We report on successful experiments with a commercial nonlinear programming solver. We further demonstrate that the known “mixing” technique can be successfully used to combine the factorization bound with the factorization bound of the complementary CMESP and with the “linx bound” of Anstreicher.

Keywords: maximum-entropy sampling; convex relaxation; integer nonlinear optimization; mixing bounds (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1264 (application/pdf)

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:inm:orijoc:v:35:y:2023:i:2:p:368-385

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().