Athanor: High-Level Local Search Over Abstract Constraint Specifications in Essence

Saad Attieh, Nguyen Dang, Christopher Jefferson, Ian Miguel, Peter NightingaleIJCAI 2019 · DOI

TL;DR

This paper introduces ATHANOR, a novel local search solver that operates directly on high-level, abstract constraint specifications written in the ESSENCE language. By leveraging the rich structure of these specifications, ATHANOR automatically generates more meaningful neighborhoods, leading to improved performance and scalability compared to existing methods that rely on lower-level representations.

What Problem Does This Paper Address?

Solving complex combinatorial optimization problems often involves defining a problem's variables and constraints. Traditional local search algorithms typically work with simplified, low-level representations of these problems (e.g., using only integers and booleans). This abstraction can lead to a loss of valuable structural information present in the original problem definition, making it harder to design efficient search strategies. While some approaches try to generate better "neighborhoods" (sets of moves to explore) from higher-level specifications, they often still require refining these neighborhoods into a lower-level format before the search can begin. This refinement step can be a bottleneck, limiting scalability. The authors aim to bridge this gap by creating a local search solver that operates directly on these rich, high-level constraint specifications, thereby exploiting their inherent structure for more effective and scalable search.

Methods

ATHANOR's core innovation lies in its direct manipulation of ESSENCE specifications, which use abstract types like sets, multisets, and sequences. Key techniques include:

  • Direct High-Level Operation: Unlike other solvers, ATHANOR doesn't refine ESSENCE specifications into simpler forms. It works directly with nested, abstract types.
  • Automatic Neighborhood Generation: The structure of ESSENCE types (e.g., set of sequence of int) is used to automatically derive semantically meaningful neighborhoods. These neighborhoods are designed to preserve type invariants (e.g., ensuring elements in a set remain distinct).
  • Incremental Evaluation: To speed up the search, ATHANOR incrementally updates the state of the solver when a variable's value changes. This avoids recomputing the entire problem state from scratch.
  • Violation Counts: For Boolean expressions, ATHANOR tracks "violation counts" to quantify how much a constraint is violated. These counts are propagated through nested structures, helping the solver identify which parts of the problem are causing issues and guide its search.
  • Dynamic Unrolling of Quantifiers: ESSENCE allows for quantifiers (e.g., "for all elements in a set..."). ATHANOR dynamically generates and deletes constraints related to these quantifiers as elements are added or removed from variables, enabling it to handle problems with potentially vast numbers of elements that would overwhelm static approaches.
  • Search Strategy: ATHANOR employs a search strategy that first aims to find a feasible solution (one that satisfies all hard constraints) and then optimizes the objective function. It uses a regret minimization multi-armed bandit to intelligently select which neighborhood to apply.

Datasets

The paper evaluates ATHANOR on several benchmark problem classes, including:

  • Capacitated Vehicle Routing Problem (CVRP)
  • SONET
  • Traveling Salesman Problem (TSP)
  • Knapsack
  • MEB (Multi-objective Evolutionary Benchmark)
  • Social Golfers Problem

Instances for these problems were sourced from standard benchmarks (TSPLIB, VRP-REP, Pisinger's knapsack instances, CSPLib) and custom-generated instances.

Key Insights and Ideas

  • Structure is Power: The paper strongly suggests that the rich, abstract structure provided by languages like ESSENCE is not just for modeling convenience but is a crucial source of information for designing effective search heuristics.
  • Scalability through Dynamism: The ability to dynamically create and delete values and constraints, particularly for quantified expressions over variable-sized structures, is key to ATHANOR's scalability on large instances.
  • Semantically Rich Neighborhoods: By operating at a higher level, ATHANOR can generate neighborhoods that are more aligned with the problem's inherent structure, leading to more informed search steps.
  • Type Invariants as Search Guides: ATHANOR leverages type invariants (e.g., uniqueness in sets, order in sequences) to prune the search space and generate more relevant moves.

Key Results

ATHANOR demonstrates strong performance across various problem classes:

  • Structured Problems (CVRP, Sonet): ATHANOR significantly outperforms other local search solvers, often finding better solutions faster. It handles these problems effectively without needing artificial limits on variable sizes, unlike lower-level solvers.
  • Unstructured Problems (TSP, Knapsack): While ATHANOR still performs competitively, the advantage over other solvers is less pronounced when the problem structure is minimal.
  • Large Knapsack Instances: For very large knapsack problems (100,000 items), ATHANOR finds feasible solutions rapidly and makes steady progress, while other solvers struggle to find any solution at all.
  • Social Golfers Problem: ATHANOR excels in this satisfaction problem, demonstrating its ability to leverage specific problem attributes (like regular and numParts) for efficient search.

Limitations and Future Work

  • Tuning Constants: The paper mentions that constants used in the search algorithm (e.g., random walk length, exploration parameters) are tunable and their optimal values might vary. Future work could involve investigating more advanced search strategies and automatic tuning of these constants.
  • Symmetry Breaking: The authors note that while they compared symmetry-broken and non-symmetry-broken models, some solvers (like Oscar-CBLS) had issues with symmetry-broken models. ATHANOR's approach of operating directly on abstract specifications might offer a more unified way to handle symmetry.
  • Advanced Search Strategies: The current search strategy alternates between hill climbing and random walk. Exploring more sophisticated metaheuristics or search techniques could further enhance performance.

Summary updated

BibTeX
@inproceedings{attieh2019athanor,
  author = {Saad Attieh and Nguyen Dang and Christopher Jefferson and Ian Miguel and Peter Nightingale},
  title = {{Athanor: High-Level Local Search Over Abstract Constraint Specifications in Essence}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/148},
}
Figure