Learning for Spatial Branching: An Algorithm Selection Approach

Bissan Ghaddar (), Ignacio Gómez-Casares (), Julio González-Díaz (), Brais González-Rodríguez (), Beatriz Pateiro-López () and Sofía Rodríguez-Ballesteros ()
Additional contact information
Bissan Ghaddar: Ivey Business School, Western University, London, Ontario N6G 0N1, Canada
Ignacio Gómez-Casares: CITMAga (Galician Center for Mathematical Research and Technology), 15782 Santiago de Compostela (A Coruña), Spain; Department of Statistics, Mathematical Analysis and Optimization and MODESTYA Research Group, University of Santiago de Compostela, 15782 Santiago de Compostela (A Coruña), Spain
Julio González-Díaz: CITMAga (Galician Center for Mathematical Research and Technology), 15782 Santiago de Compostela (A Coruña), Spain; Department of Statistics, Mathematical Analysis and Optimization and MODESTYA Research Group, University of Santiago de Compostela, 15782 Santiago de Compostela (A Coruña), Spain
Brais González-Rodríguez: CITMAga (Galician Center for Mathematical Research and Technology), 15782 Santiago de Compostela (A Coruña), Spain; Department of Statistics, Mathematical Analysis and Optimization and MODESTYA Research Group, University of Santiago de Compostela, 15782 Santiago de Compostela (A Coruña), Spain
Beatriz Pateiro-López: CITMAga (Galician Center for Mathematical Research and Technology), 15782 Santiago de Compostela (A Coruña), Spain; Department of Statistics, Mathematical Analysis and Optimization and MODESTYA Research Group, University of Santiago de Compostela, 15782 Santiago de Compostela (A Coruña), Spain
Sofía Rodríguez-Ballesteros: CITMAga (Galician Center for Mathematical Research and Technology), 15782 Santiago de Compostela (A Coruña), Spain

INFORMS Journal on Computing, 2023, vol. 35, issue 5, 1024-1043

Abstract: The use of machine learning techniques to improve the performance of branch-and-bound optimization algorithms is a very active area in the context of mixed integer linear problems, but little has been done for nonlinear optimization. To bridge this gap, we develop a learning framework for spatial branching and show its efficacy in the context of the Reformulation-Linearization Technique for polynomial optimization problems. The proposed learning is performed offline, based on instance-specific features and with no computational overhead when solving new instances. Novel graph-based features are introduced, which turn out to play an important role for the learning. Experiments on different benchmark instances from the literature show that the learning-based branching rule significantly outperforms the standard rules.

Keywords: spatial branching; non-linear optimization; polynomial optimization; machine learning; statistical learning (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0090 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:35:y:2023:i:5:p:1024-1043

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().