Automatically exploiting high-level problem structure in local-search

  • Saad Wasim A Attieh

Student thesis: Doctoral Thesis (PhD)

Abstract

Constraint Programming is the study of modelling and solving complex combinatorial
problems. Systematic-search and local-search are both well-researched approaches to
solving constraint problems. Systematic-search exhaustively explores the entire search
space and can be used to guarantee optimality, prove infeasibility or enumerate all possible
solutions. Conversely, local-search is a heuristic-based approach to solving constraint
problems. Often used in industrial applications, local-search is used to discover
high-quality solutions quickly, usually sacrificing the ability to cover the entire search
space. For this reason, it is preferred in applications where the scale of the problems
being solved are beyond what can be feasibly searched using systematic methods.

This work investigates methods of using information derived from high-level specifications
of problems to augment the performance and scalability of local-search systems.
Typically, abstract high-level constraint specifications or models are refined into lowlevel
representations suitable for input to a constraint solver, erasing any knowledge
of the specifications' high-level structures. We propose that whilst these lower-level
models are equivalent in their description of the problems being solved, the original
high-level specification, if retained, can be used to augment both the performance and
scalability of local-search systems.

In doing this, two approaches have been implemented and benchmarked. In the first
approach, Structured Neighbourhood Search (SNS), a systematic solver is adapted to
support declarative large neighbourhood search, using the high-level types such as sets,
sequences and partitions in the original problem specification to automatically construct
higher-quality, structured neighbourhoods. Our experiments demonstrate the
performance of SNS when applied to structured problems. In the second approach, a
novel constraint-based local-search solver is designed to operate on the high-level structures
without refining these structures into lower-level representations. The new solver
Athanor can directly instantiate and operate on the types in the Essence abstract
specification language, supporting arbitrarily nested types such as sets of partitions,
multi-sets of sequences and so on. Athanor retains the performance of SNS but boasts
a unique benefit; on some classes of problems, the high-level solver is shown to be able
to efficiently operate on instances that are too large for low-level solvers to even begin
search.
Date of Award30 Nov 2022
Original languageEnglish
Awarding Institution
  • University of St Andrews
SupervisorChristopher Anthony Jefferson (Supervisor) & Ian James Miguel (Supervisor)

Access Status

  • Full text open

Cite this

'