A Framework for Constraint Based Local Search using Essence

Özgür Akgün, Saad Attieh, Ian P. Gent, Christopher Jefferson, Ian Miguel, Peter Nightingale, András Z. Salamon, Patrick Spracklen, James WetterIJCAI 2018 · DOI

TL;DR

This paper introduces Structured Neighbourhood Search (SNS), a novel framework that automatically generates semantically meaningful local search neighborhoods directly from high-level constraint specifications written in the ESSENCE language. This approach significantly improves the quality of neighborhoods compared to traditional methods, leading to better performance on complex combinatorial optimization problems.

What Problem Does This Paper Address?

Constraint Programming (CP) is powerful for solving complex optimization problems, but its systematic search can be slow. Local search methods offer speed by iteratively improving solutions, but their effectiveness hinges on the quality of "neighborhoods" – the set of neighboring solutions a search can explore. Constraint-Based Local Search (CBLS) attempts to bridge this gap by using constraint solvers to define these neighborhoods. However, a common limitation is that constraint models often represent problems at a low level of abstraction (individual variables and constraints), obscuring the original problem's inherent structure. This makes it difficult to generate neighborhoods that are truly meaningful and exploit this structure, potentially limiting the performance of local search. The authors aim to overcome this by leveraging high-level problem specifications to automatically derive powerful, structure-aware neighborhoods.

Methods

The core of the paper is the Structured Neighbourhood Search (SNS) framework. SNS operates on specifications written in the ESSENCE language, which allows for high-level, abstract descriptions of combinatorial problems. The key innovation is the automatic generation of neighborhoods. This is achieved through a pipeline involving:

  • CONJURE: This system analyzes an ESSENCE specification and automatically generates neighborhoods based on the abstract types and structures present (e.g., sets, sequences, functions). It uses a set of neighborhood generation rules (direct, lifted, and synchronized) to create these transformations.
  • ESSENCE PRIME: The generated neighborhoods are then translated into a lower-level, solver-independent constraint modeling language.
  • SAVILE ROW: This system further refines and optimizes the models for specific constraint solvers.
  • SNS Solver: A local search algorithm that utilizes these automatically generated neighborhoods. It employs a multi-armed bandit algorithm (UCB1) to dynamically select the most promising neighborhood at each step, balancing exploration and exploitation.

Crucially, SNS ensures that even when using a low-level constraint solver, the explored neighborhoods remain semantically meaningful with respect to the original high-level ESSENCE specification.

Datasets

The paper evaluates SNS on five standard problem classes:

  • Capacitated Vehicle-Routing Problem (CVRP)
  • Progressive Party Problem (PPP)
  • Minimum Energy Broadcast (MEB)
  • SONET
  • Rack Configuration Problem (RackConf)

These are standard benchmarks used in constraint programming research. No new datasets were introduced.

Key Insights and Ideas

  • Structure is King: The paper strongly supports the hypothesis that exploiting the high-level combinatorial structure of a problem, as expressed in languages like ESSENCE, is crucial for generating effective local search neighborhoods.
  • Automatic Neighborhood Generation: The ability to automatically derive semantically rich neighborhoods from abstract specifications is a significant advancement over manual or low-level constraint-based generation.
  • Bridging High-Level and Low-Level: SNS effectively bridges the gap between high-level declarative modeling and low-level search mechanisms, allowing for powerful search strategies without requiring specialized search procedures for each problem.
  • Multi-Armed Bandit for Neighborhood Selection: Using UCB1 to dynamically select neighborhoods is an effective way to manage a large set of generated neighborhoods, especially when their performance is initially unknown.

Key Results

SNS demonstrated strong performance across the evaluated problem classes, often outperforming other state-of-the-art methods:

  • SNS found the best results (or tied) on a significant number of instances, particularly for CVRP, which has a complex nested structure (set of sequences).
  • It was the only solver to successfully find a solution in every run for all tested instances, indicating robustness.
  • Compared to other Large Neighbourhood Search (LNS) variants, SNS generally outperformed them, especially on CVRP and SONET. For example, on CVRP, SNS showed wins of 6.7% (LNS EB) and 19% (LNS PG) in mean best score.
  • While LNS variants sometimes outperformed SNS on specific problems (e.g., RackConf), SNS's overall performance and robustness were notable.

Limitations and Future Work

  • Parameter Tuning: The authors acknowledge that the parameters for the multi-armed bandit (α and β) were set empirically and suggest future work to explore tuning these parameters or investigating policies for non-stationary bandit problems (e.g., Exp3 algorithms).
  • Exploration of Neighborhoods: While SNS generates neighborhoods, the paper mentions that future work could focus on optimizing the exploration of these automatically constructed neighborhoods.
  • Non-Stationary Bandit: The current multi-armed bandit approach assumes some stationarity. Future work could explore more advanced techniques to handle potential non-stationarity in neighborhood performance during search.

Summary updated

BibTeX
@inproceedings{akgun2018framework,
  author = {Özgür Akgün and Saad Attieh and Ian P. Gent and Christopher Jefferson and Ian Miguel and Peter Nightingale and András Z. Salamon and Patrick Spracklen and James Wetter},
  title = {{A Framework for Constraint Based Local Search using Essence}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/173},
}

Loading related content...

Figure