Extensions to the repetitive branch and bound algorithm for globally optimal clusterwise regression |
| |
Authors: | Réal A Carbonneau Gilles CaporossiPierre Hansen |
| |
Affiliation: | GERAD and HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada H3T 2A7 |
| |
Abstract: | A branch and bound strategy is proposed for solving the clusterwise regression problem, extending Brusco's repetitive branch and bound algorithm (RBBA). The resulting strategy relies upon iterative heuristic optimization, new ways of observation sequencing, and branch and bound optimization of a limited number of ending subsets. These three key features lead to significantly faster optimization of the complete set and the strategy has more general applications than only for clusterwise regression. Additionally, an efficient implementation of incremental calculations within the branch and bound search algorithm eliminates most of the redundant ones. Experiments using both real and synthetic data compare the various features of the proposed optimization algorithm and contrasts them against a benchmark mixed logical-quadratic programming formulation optimized by CPLEX. The results indicate that all components of the proposed algorithm provide significant improvements in processing times, and, when combined, generally provide the best performance, significantly outperforming CPLEX. |
| |
Keywords: | Global optimization Combinatorial optimization Clusterwise regression Branch and bound Sequencing Heuristics |
本文献已被 ScienceDirect 等数据库收录! |
|