New Optimality Test for Branch-and-Bound--Based Comprehensive Subset Search

• Activity Number: 107
• Type: Contributed
• Date/Time: Monday, July 30, 2007 : 8:30 AM to 10:20 AM
• Sponsor: IMS
• Author(s): Xuelei Ni*+ and Xiaoming Huo
• Companies: Kennesaw State University and Georgia Institute of Technology
• Keywords: subset selection ; branch-and-bound ; leaps and bounds ; optimality test ; inverse tree ; pair tree

Abstract

In subset selection in regressions, branch-and-bound algorithms and the Furnival and Wilson (1974) test have been combined to search all subsets. Furnival and Wilson test reduces the number of subsets that needed to be computed, and is completely based on a monotonic property of the residual sum of squares. We design a new test, which brings in other quantities (e.g., the least square coefficients and the residuals) into consideration. The new test supplements the Furnival-Wilson test. Simulations demonstrate improvements brought by the newly proposed test. We describe a branch-and-bound structure|pair tree|within which the new optimality test can be easily integrated. The pair tree is comparable with other contemporary branch-and-bound designs, for which pointers are given.