报告题目：二元编码和约束求解

　　报告人：王瑞伟

　　报告时间：2023年09月18日09:30

　　报告地点：信息科学与技术学院324会议室

　　报告人简介：王瑞伟，新加坡国立大学博士后，主要研究方向是约束问题的求解算法研究（人工智能和形式化方法以及运筹学的一个交叉方向）。他目前工作主要是通过利用约束之间的互相转化来化简约束，从而提升约束问题求解的效率，在AAAI，ASE，IJCAI，CP，SAT等相关国际会议上发表论文10来篇。

　　报告内容简介：日常生活中很多约束问题可以被自然地建模成有限域约束，比如排班问题，排课问题和产品配置问题。不同于整型和实数域约束，任意类型的有限域约束都可以通过暴力搜索来进行求解，所以人们可以采用各种不同类型的有限域约束来构建更自然的约束问题模型。历史上对于有限域约束的研究是从二元约束开始的，很多求解技术是先在二元约束上进行研究，然后才扩展到其他有限域约束，比如常用的弧相容技术。从理论的角度看，二元约束是NP-完全的，可以用二元编码将任意有限域约束转化成二元约束，但是已有的研究表明二元编码并不是一种高效的求解方法。我们将讨论人们为什么会对二元编码产生误解，同时我们将展示怎么通过二元编码来对表约束，有限自动机约束和决策图约束等有限域约束进行化简并提升约束问题的求解效率。