arXiv:2410.05937cs.AI2024-10被引 3

用抽象语法自动生成高质量搜索邻域,提升组合优化求解效率。

Athanor: Local Search over Abstract Constraint Specifications

  • 从抽象约束语言Essence出发,避免低层建模干扰
  • 自动生成高质量邻域,显著提升求解性能
  • 适合需要高效求解组合优化问题的研究者

局部搜索是求解组合优化问题的常用方法。现有方法通常以MiniZinc等独立于求解器的约束建模语言输入问题模型。本文提出的Athanor求解器则基于抽象约束规范语言Essence,允许在不承诺底层建模决策的情况下描述问题,其支持丰富的抽象类型。优势在于:从简洁的抽象规格中可自动挖掘问题结构,生成高质量的邻域,无需在等效约束模型中手动识别该结构。基于高层类型生成邻域和直接在其上搜索的双重优势,实验表明Athanor在实际应用中表现优于现有方法。

原文摘要 · Abstract (English)

Local search is a common method for solving combinatorial optimisation problems. We focus on general-purpose local search solvers that accept as input a constraint model - a declarative description of a problem consisting of a set of decision variables under a set of constraints. Existing approaches typically take as input models written in solver-independent constraint modelling languages like MiniZinc. The Athanor solver we describe herein differs in that it begins from a specification of a problem in the abstract constraint specification language Essence, which allows problems to be described without commitment to low-level modelling decisions through its support for a rich set of abstract types. The advantage of proceeding from Essence is that the structure apparent in a concise, abstract specification of a problem can be exploited to generate high quality neighbourhoods automatically, avoiding the difficult task of identifying that structure in an equivalent constraint model. Based on the twin benefits of neighbourhoods derived from high level types and the scalability derived by searching directly over those types, our empirical results demonstrate strong performance in practice relative to existing solution methods.

组合优化局部搜索抽象建模

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。