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