LLM2D
阿萨纳:抽象约束规范上的局部搜索
Athanor: Local Search over Abstract Constraint Specifications
作者: Saad Attieh, Nguyen Dang, Christopher Jefferson, Ian Miguel, Peter Nightingale
发布日期: 10/10/2024
arXiv ID: oai:arXiv.org:2410.05937v1

摘要

局部搜索是解决组合优化问题的常用方法。我们关注的是通用局部搜索求解器,它们接受约束模型作为输入,约束模型是对问题的声明式描述,包含一组决策变量和一组约束。现有方法通常以独立于求解器的约束建模语言(如 MiniZinc)编写的模型作为输入。本文描述的 Athanor 求解器与之不同,它从抽象约束规范语言 Essence 中对问题的规范开始,Essence 支持一组丰富的抽象类型,允许在不承诺低级建模决策的情况下描述问题。从 Essence 出发的好处是,可以利用简洁、抽象的规范中显现的结构自动生成高质量的邻域,从而避免在等效约束模型中识别该结构的困难任务。基于从高级类型派生的邻域和直接在这些类型上搜索的扩展性的双重优势,我们的实证结果表明,在实践中相对于现有的解决方案方法具有很强的性能。