報告題目：二元編碼和約束求解
報告人：王瑞偉
報告時間：2023年09月18日09:30
報告地點：信息科學(xué)與技術(shù)學(xué)院324會議室
報告人簡介：王瑞偉，新加坡國立大學(xué)博士后，主要研究方向是約束問題的求解算法研究（人工智能和形式化方法以及運籌學(xué)的一個交叉方向）。他目前工作主要是通過利用約束之間的互相轉(zhuǎn)化來化簡約束，從而提升約束問題求解的效率，在AAAI，ASE，IJCAI，CP，SAT等相關(guān)國際會議上發(fā)表論文10來篇。
報告內(nèi)容簡介：日常生活中很多約束問題可以被自然地建模成有限域約束，比如排班問題，排課問題和產(chǎn)品配置問題。不同于整型和實數(shù)域約束，任意類型的有限域約束都可以通過暴力搜索來進行求解，所以人們可以采用各種不同類型的有限域約束來構(gòu)建更自然的約束問題模型。歷史上對于有限域約束的研究是從二元約束開始的，很多求解技術(shù)是先在二元約束上進行研究，然后才擴展到其他有限域約束，比如常用的弧相容技術(shù)。從理論的角度看，二元約束是NP-完全的，可以用二元編碼將任意有限域約束轉(zhuǎn)化成二元約束，但是已有的研究表明二元編碼并不是一種高效的求解方法。我們將討論人們?yōu)槭裁磿Χ幋a產(chǎn)生誤解，同時我們將展示怎么通過二元編碼來對表約束，有限自動機約束和決策圖約束等有限域約束進行化簡并提升約束問題的求解效率。
