A column generation approach to exact experimental design

Abstract In this work, we address the exact D-optimal experimental design problem when the number of design vectors is large. First, we propose a customized column generation algorithm to solve the continuous relaxation of the problem. In the approach, each restricted master problem is constructed carefully so that the number of variables stays small and therefore the subproblem can be solved efficiently by a Primal-Dual Interior-Point-based Semidefinite Programming solver. The support of this solution provides a subset of design points to be used in a local search algorithm for the solution of the integer problem. We prove that a local search algorithm restricted to points of this subset provides an exact design that is provably close to the exact D-optimal design. Our numerical experiments show that, for large-scale instances in which the number of regression points exceeds by far the number of experiments, our approach achieves superior performance compared to existing branch-and-bound-based algorithms in both computational efficiency and solution quality.