Solving Constraint Optimization Problems (COPs) can be dramatically simplified by boundary estimation, that is, providing tight boundaries of cost functions. By feeding a supervised Machine Learning (ML) model with data composed of known boundaries and extracted features of COPs, it is possible to train the model to estimate boundaries of a new COP instance. In this paper, we first give an overview of the existing body of knowledge on ML for Constraint Programming (CP) which learns from problem instances. Second, we introduce a boundary estimation framework that is applied as a tool to support a CP solver. Within this framework, different ML models are discussed and evaluated regarding their suitability for boundary estimation, and countermeasures to avoid unfeasible estimations that avoid the solver to find an optimal solution are shown. Third, we present an experimental study with distinct CP solvers on seven COPs. Our results show that near-optimal boundaries can be learned for these COPs with only little overhead. These estimated boundaries reduce the objective domain size by 60-88% and can help the solver to find near-optimal solutions early during search.
翻译:解决限制优化问题可以通过边界估计大大简化,即提供严格的费用功能界限。通过将一个由已知边界和COP的抽取特征组成的数据输入监督的机器学习模型,有可能对模型进行模型培训,以估计新的COP的边界。在本文件中,我们首先概述从问题实例中学习的关于限制程序(CP)的现有ML知识。第二,我们引入一个边界估计框架,作为支持CP解答器的工具。在这个框架内,讨论和评价不同的ML模型,以了解这些模型是否适合边界估计,并展示避免不可行的估计,避免解决者找到最佳解决办法的对策。第三,我们提出了在7个COP上与不同的CP解答器的实验性研究。我们的结果显示,这些COP的近优度边界只有很小的间接费用。这些估计边界将目标域缩小60-88%,有助于解决者在早期搜索时找到近于最优的解决方案。