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

2023/02/14 by Ponte, Gabriel, Fampa, Marcia, Lee, Jon
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2302.07386

Abstract

We apply a branch-and-bound (B&B) algorithm to the D-optimality problem based on a convex mixed-integer nonlinear formulation. We discuss possible methodologies to accelerate the convergence of the B&B algorithm, by combining the use of different upper bounds, variable-bound tightening inequalities, and local-search procedures. Different methodologies to compute the determinant of a matrix after a rank-one update are investigated to accelerate the local-searches. We discuss our findings through numerical experiments with randomly generated test problem.

Related

• Branch-and-bound for integer D-Optimality with fast local search and variable-bound tightening
• Improving the filtering of Branch-And-Bound MDD solver (extended)
• Disjunctive Branch-And-Bound for Certifiably Optimal Low-Rank Matrix Completion
• Computing D-Optimal solutions for huge-scale linear and quadratic response-surface models
• Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends