Local Search

We propose the use of set variables and set constraints for simplifying the modelling task [ÅFP05a]. The hope is to show eventually that even search time or memory consumption can be saved by reasoning at this higher level of abstraction, and not just modelling time.

We designed generic algorithms for [incrementally] maintaining the violations of a constraint and its decisions variables:

• for a constraint on set decision variables, given by a specification in monadic existential second-order logic [ÅFP07c];
• for a constraint on a sequence of scalar decision variables, given by a specification as a deterministic finite automaton [HFP11].

This allows one to evaluate the merits of a model before handcrafting such algorithms for a constraint that is not yet built into the used local search framework.

We argue that constraint-directed neighbourhoods, where the value or sign of penalty change of each particular move is known, simplify the design of local search algorithms; furthermore, they can be synthesised from a specification of a constraint in MSO [ÅFP09].

We investigate local search over massive datasets, by performing the search inside a relational database using a small extension of SQL to model the problem and using the primitives offered by a database management system for computing and evaluating the moves [MFHMP09].