Title: Branch-and-bound for D-Optimality with fast local search and variable-bound tightening
 

Abstract:  We develop a branch-and-bound algorithm for the D-optimality problem (D-opt), a central problem in statistical design theory, based on two bounds derived from convex relaxations, the "natural bound'' and the "Γ-bound''. We describe a procedure to fix variables based on convex duality. We demonstrate that the Γ-bound for the binary version of D-opt with a particular variable fixing is precisely the "complementary Γ-bound'' for the so-called "Data-Fusion problem''. Further, we present theoretical results showing some relations between different bounds. We propose local-search heuristics for D-opt and analyze different strategies to compute search directions and step sizes for each iteration of them. Finally, we present numerical experiments concerning a B&B algorithm based on our results. This is a joint work with Jon Lee and Gabriel Ponte.