Minimization of Akaike's information criterion in linear regression analysis via mixed integer nonlinear program

Akaike's information criterion (AIC) is a measure of evaluating statistical models for a given data set. We can determine the best statistical model for a particular data set by finding the model with the smallest AIC value. Since there are exponentially many candidates of the best model, the computation of the AIC values for all the models is impractical. Instead, stepwise methods, which are local search algorithms, are commonly used to find a better statistical model, though it may not be the best model. We propose a branch-and-bound search algorithm for a mixed integer nonlinear programming formulation of the AIC minimization presented by Miyashiro and Takano [Mixed integer second-order cone programming formulations for variable selection, Eur. J. Oper. Res. 247 (2015), pp. 721-731]. More concretely, we propose procedures to find lower and upper bounds, and branching rules for this minimization. We then combine such procedures and branching rules with SCIP, a mathematical optimization software and the branch-and-bound framework. We show that the proposed method can provide the best AIC-based statistical model for small- or medium-sized benchmark data sets in the UCI Machine Learning Repository. Furthermore, the proposed method finds high-quality solutions for large-sized benchmark data sets.