自动调参框架让约束求解器性能提升,省时省力。
Hyperparameter Optimization of Constraint Programming Solvers
- 分探查与求解两阶段,用贝叶斯优化找最优参数
- 在114个实例上,超80%情况优于默认配置
- 适合想提升求解器效率的算法工程师和研究人员
约束编程求解器的性能高度依赖其超参数设置。手动调优耗时且需专业知识。本文提出一种集成于CPMpy库的新型两阶段自动化超参数优化方法——探查-求解算法:将时间预算分为两部分,先通过可配置的超参数优化方法(贝叶斯优化或汉明距离搜索)探索不同参数组合,再用最佳配置求解问题。在ACE和Choco两个求解器上,对114个组合优化实例进行评估。结果显示,采用贝叶斯优化时,该算法在25.4%的实例中显著提升ACE求解质量,57.9%保持与默认配置相当;在Choco上,38.6%实例表现更优。该方法始终优于汉明距离搜索,验证了基于模型探索优于简单局部搜索。整体而言,探查-求解算法是一种资源感知、鲁棒性强的求解器调优方案。
原文摘要 · Abstract (English)
The performance of constraint programming solvers is highly sensitive to the choice of their hyperparameters. Manually finding the best solver configuration is a difficult, time-consuming task that typically requires expert knowledge. In this paper, we introduce probe and solve algorithm, a novel two-phase framework for automated hyperparameter optimization integrated into the CPMpy library. This approach partitions the available time budget into two phases: a probing phase that explores different sets of hyperparameters using configurable hyperparameter optimization methods, followed by a solving phase where the best configuration found is used to tackle the problem within the remaining time. We implement and compare two hyperparameter optimization methods within the probe and solve algorithm: Bayesian optimization and Hamming distance search. We evaluate the algorithm on two different constraint programming solvers, ACE and Choco, across 114 combinatorial problem instances, comparing their performance against the solver's default configurations. Results show that using Bayesian optimization, the algorithm outperforms the solver's default configurations, improving solution quality for ACE in 25.4% of instances and matching the default performance in 57.9%, and for Choco, achieving superior results in 38.6% of instances. It also consistently surpasses Hamming distance search within the same framework, confirming the advantage of model-based exploration over simple local search. Overall, the probe and solve algorithm offers a practical, resource-aware approach for tuning constraint solvers that yields robust improvements across diverse problem types.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。