The maximum-entropy sampling problem (MESP) is a difficult nonlinear integer programming problem that arises in spatial statistics, for example in the design of weather monitoring networks. We describe a new bound for the MESP that is based maximizing a function of the form ldet M(x) over linear constraints, where M(x) is an n-by-n matrix function that 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.
Personal website of Kurt Anstreicher