Department of Information Technology

Constraint-Based Local Search

In constraint-based local search (CBLS), we address the following issues, covered also in various theses [Å07, H13, B14]:

MiniZinc Back-End

We proposed the first CBLS back-end [B14, BMFP15] (software) for the solving-technology independent modelling language MiniZinc. It uses the CBLS solver of the OscaR toolkit.

Versatility

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].

Extensibility

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.

Efficiency

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]

Massive Data

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].

Applications

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].

Updated  2016-09-23 16:32:27 by Anneli Folkesson.