Skip to main content
Department of Information Technology

Constraint-Based Local Search

See LSCS: The International Workshops on Local Search Techniques in Constraint Satisfaction.

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

Modelling Abstractions for Stochastic Local Search

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

Search Abstractions for Stochastic Local Search

We proposed declarative local-search neighbourhoods [BFPST18] for the MiniZinc modelling language, which only had search abstractions for systematic CP-style search, so that the blackbox local search (see above) can be overridden. We also showed how such neighbourhoods can profitably be explored by systematic search within each iteration of local search [BFPS19].

Large-Neighbourhood Search for Satisfaction Problems

We introduced the notion of a non-failing propagator [BFPST20], which is subsumed just before causing a back- track and can be obtained for any propagator by just a few changes to the fixpoint algorithm of any CP solver, in order to solve the soft version of a satisfaction problem by large-neighbourhood search (LNS), or to find the initial solution to an optimisation problem that is to be solved by another round of LNS.

Efficiency

We showed that local-search moves can profitably be extended into compound moves [BFP19] by systematic search prior to being committed.

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]

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.

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  2021-04-15 10:51:45 by Pierre Flener.