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.
翻译:使用机器学习技术来改进分支和约束优化算法的性能,在混合整数线性问题的背景下是一个非常活跃的领域,但在非线性优化方面没有做多少工作。为了缩小这一差距,我们为空间分支开发了一个学习框架,并展示了其在多边优化改造-远程化技术问题背景下的功效。拟议的学习是在离线进行,以具体实例特征为基础,在解决新案例时没有计算间接费用。引入了基于新图表的功能,结果为学习发挥了重要作用。对文献中不同基准实例的实验表明,基于学习的分支规则大大超过标准规则。