基于在线学习的约束求解方法研究

Constraint Programming is a foundational method for solving combinatorial search problems in computer science. Constraint solving has been always a hot research topic. The solving ability of the traditional methods is limited, because they cannot identify the structures of problems, so the future trends in this area will be the methods that identify problem structures by learning automatically. At present, the research of applying machine learning and data mining methods in constraint solving is still in the early stage. Taking the opportunity, the proposed research is going to develop online-learning-based constraint solving methods. We are going to propose a new constraint solving framework that does learning during the solving procedures. It would efficiently solves real-world problems by identifying problem structures automatically. The framework includes: 1. We employ data mining techniques to recognize the particular areas containing high quality solutions and to find high quality searching entrances. A constraint solving method based on Frequent Pattern Mining is going to be developed. 2. We do online-learning to identify the associations between variable values and design heuristic function based on the associations. A heuristic search strategy learning fine-grained information is going to be developed. 3. Utilizing the efficient filtering power of strong bound consistency, an adaptive constraint propagation for linear constraints is going to be developed with the Multi-Armed Bandits method from reinforcement learning. The developments of the proposed research will provide more useful and powerful methods for solving the complex combinatorial problems in real world.

约束程序是计算机科学领域解决组合搜索问题的基础方法。约束求解一直是研究热点，但传统求解方法无法识别问题结构，求解能力有限，因此，通过在线学习来识别问题结构的求解方法成为新发展方向。目前在约束求解中使用机器学习与数据挖掘方法的研究处于起步阶段，本项目抓住时机，开展基于在线学习的约束求解方法研究，拟提出一个新约束求解流程，通过在求解过程中进行学习，自动识别问题结构，快速求解实际问题。具体包括以下三方面：1.使用数据挖掘方法发现解空间中包含高质量解的特殊区域，寻找高质量搜索入口，研究基于频繁模式挖掘的完备约束求解方法；2.通过在线学习识别变量值之间的关联，根据这种关联设计启发式函数，研究基于细粒度信息学习的启发式搜索策略；3.使用强化学习中“多摇臂赌博机”方法研究线性约束的自适应约束传播机制，自动利用强边界相容的高效剪枝能力。本项目研究成果将为解决现实世界复杂组合问题提供更加有效的方法和手段。

约束满足问题（CSP）在理论计算机科学、人工智能、运筹学等领域均具有重要研究价值。约束满足问题的根本挑战是约束求解，即为所有变量找到一组赋值，使得所有约束均被满足。本项目围绕基于在线学习的约束求解方法开展研究，主要取得了以下几方面研究进展：（1）我们研究了一种方法对问题解空间进行模式分析，可在搜索开始前找到包含最优解的子空间，提出了基于频繁模式挖掘的约束优化问题（CSP的优化版本）求解方法，显著缩减了分支限界搜索算法寻找最优解的代价；（2）在约束传播方面，我们以最有效的弧相容为标准，研究剪枝能力更强或更弱的新相容性，提出了一种新相容性算法，其用于回溯搜索的求解性能在多个问题上均优于弧相容；（3）在搜索策略方面，我们针对不同启发式函数下的变量相关性进行研究，提出了一种细粒度方法组合不同的变量排序启发式用于求解约束满足问题；（4）遵循经典的“失败优先原则”，我们提出了两种基于失败信息的变量排序启发式用于求解约束满足问题，通过直接统计变量赋值后的失败比例与失败深度，直观体现了失败优先的策略，在MiniZinc标准库测试用例全集上了较好的实验效果，该方法已被Choco求解器收录。