An Exact Algorithm for Hierarchically Well-Formulated Subsets in Second-Order Polynomial Regression

Abstract

Variable selection in multiple regression requires identifying the best subset from among a set of candidate predictors. In the case of polynomial regression, the variable selection process can be further complicated by the need to obtain subsets that are hierarchically well formulated. We present a branch-and-bound algorithm for selection of the best hierarchically well-formulated subset in second-order polynomial regression. We apply the new algorithm to a well-known data set from the regression literature and compare the results with those obtained from a branch-and-bound algorithm that does not impose the hierarchical constraints. This comparison reveals that the hierarchical constraints yield only a small penalty in explained variation. We offer Fortran and MATLAB implementations of the branch-and-bound algorithms as supplemental materials associated with this work.

Keywords:  :

• Branch and bound
• Combinatorial optimization
• Regression
• Variable selection