On Computing with Some Convex Relaxations for the Maximum-Entropy Sampling Problem
From MaRDI portal
Publication:6203371
DOI10.1287/IJOC.2022.1264arXiv2112.14291MaRDI QIDQ6203371FDOQ6203371
Zhongzhu Chen, Marcia Fampa, Jon Lee
Publication date: 28 February 2024
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Abstract: Based on a factorization of an input covariance matrix, we define a mild generalization of an upper bound of Nikolov (2015) and Li and Xie (2020) for the NP-Hard constrained maximum-entropy sampling problem (CMESP). We demonstrate that this factorization bound is invariant under scaling and also 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. 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 also with the "linx bound" of Anstreicher (2020).
Full work available at URL: https://arxiv.org/abs/2112.14291
Cited In (1)
This page was built for publication: On Computing with Some Convex Relaxations for the Maximum-Entropy Sampling Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6203371)
