Efficient Solution of Maximum-Entropy Sampling Problems

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 $\text{ldet}M\left(x\right)$ over linear constraints, where $M\left(\mathit{x}\right)$ is linear in the $\mathit{n}$-vector $\mathit{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.