论文标题
学习约束优化问题的目标边界
Learning Objective Boundaries for Constraint Optimization Problems
论文作者
论文摘要
约束优化问题（COP）通常在没有足够了解目标变量的边界以进行优化的情况下考虑。如果有的话，紧密的边界有助于修剪搜索空间或估计问题特征。在不实际解决COP的情况下，找到正确和高估最佳的近距离界限，几乎是不可能的。本文介绍了Bion，这是一种通过从先前解决的COP实例中学习来进行边界估计的新方法。基于有监督的机器学习，Bion是特定于问题的和独立于解决方案的，可以应用于任何通过不同的数据输入来反复解决的COP。对七个现实的警察进行的实验评估表明，可以训练估计模型，以修剪客观变量的域以上80％以上。通过评估与各种COP求解器的估计边界，我们发现Bion改善了某些问题的求解过程，尽管更紧密的界限的影响通常依赖于问题。
Constraint Optimization Problems (COP) are often considered without sufficient knowledge on the boundaries of the objective variable to optimize. When available, tight boundaries are helpful to prune the search space or estimate problem characteristics. Finding close boundaries, that correctly under- and overestimate the optimum, is almost impossible without actually solving the COP. This paper introduces Bion, a novel approach for boundary estimation by learning from previously solved instances of the COP. Based on supervised machine learning, Bion is problem-specific and solver-independent and can be applied to any COP which is repeatedly solved with different data inputs. An experimental evaluation over seven realistic COPs shows that an estimation model can be trained to prune the objective variables' domains by over 80%. By evaluating the estimated boundaries with various COP solvers, we find that Bion improves the solving process for some problems, although the effect of closer bounds is generally problem-dependent.
