Constraint-Based Local Search
We proposed the use of set variables and set constraints for simplifying the modelling task [ÅFP05a]. We showed that even search time or memory consumption can be saved by reasoning at this higher level of abstraction, and not just modelling time [G11].
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, section 8 of HFP13a, section 6 of BCFFP14].
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 argued 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 monadic existential second-order logic [ÅFP09].
We proposed solution neighbourhoods, which contain only solutions to a chosen constraint, so as to save the time needed for neighbourhood evaluation of that constraint. This may be useful especially for constraints for which there exists no known constant-time algorithm for neighbour evaluation [HFP12]
We investigated local search over massive datasets, by performing the search inside a relational database via a small extension of SQL to model the problem and the primitives offered by a database management system for computing and evaluating the moves [MFP12].
We showed that the sectorisation of airspace for air traffic management purposes is amenable to efficient solving [JFP13, EK14] by constraint-based local search, using novel special-purpose global constraints [FP14].