Learning for Spatial Branching: An Algorithm Selection Approach
From MaRDI portal
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 non-linear 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.
Recommendations
- On learning and branching: a survey
- A machine learning-based approximation of strong branching
- Polynomial optimization: tightening RLT-based branch-and-bound schemes with conic constraints
- Learning generalized strong branching for set covering, set packing, and 0-1 knapsack problems
- On branching rules for convex mixed-integer nonlinear optimization
Cited in
(4)- Polynomial optimization: tightening RLT-based branch-and-bound schemes with conic constraints
- Impact of domain reduction techniques in polynomial optimization: a computational study
- Artificial intelligence for optimization: unleashing the potential of parameter generation, model formulation, and solution methods
- Extending a continuous RLT-based algorithm to mixed-integer polynomial problems
This page was built for publication: Learning for Spatial Branching: An Algorithm Selection Approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6200138)
