Efficient Solution of Maximum-Entropy Sampling Problems

• 成果类型: Article
• 署名作者: Anstreicher, Kurt M.
• 署名单位: University of Iowa
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1962
• 发表日期: 2020
• 页码: 1826-1835
• 关键词: maximum-entropy sampling; convex programming; nonlinear integer programming

摘要

We consider a new approach for the maximum-entropy sampling problem (MESP) that is based on bounds obtained by maximizing a function of the form ldet M(x) over linear constraints, where M(x) is linear in the n-vector x. These bounds can be computed very efficiently and are superior to all previously known bounds for MESP on most benchmark test problems. A branch-and-bound algorithm using the new bounds solves challenging instances of MESP to optimality for the first time.