Hybrid Search and Declarative Search

Time period:

1 January 2026 – 31 December 2029

Project leader:

Pierre Flener

Funder:

Swedish Research Council

Type of award:

Project grant

Total funding:

4,100,000 SEK

Society, industry, and science often require quickly finding good solutions to hard problems where, given data, values must be found for unknowns in order to satisfy constraints and minimise a cost. For example, given addresses and a depot with vehicles, find minimal-energy routes to drop or collect objects at all addresses, constrained by time windows on the visits, the available cargo space and energy, and labour regulations.To solve such optimisation problems, one either crafts a special-purpose program or expresses the unknowns, constraints, and cost in a mathematical model and feeds it with the data to a general-purpose program, called a solver, which cleverly combines smart algorithms.Global search ultimately finds optimal solutions. Local search drops that guarantee and is crucial when the speed of global search does not scale to the difficulty of one´s data. With global search, high speed and high solution quality are usually achieved easier by modellers than by programmers. With local search, the use of programming still dominates modelling, and solvers either expect a procedural hint at a search strategy or perform autonomous search from just the model.I propose (1) the automated hybridisation of search, where a local solver gainfully uses a global solver, and (2) declarative search, where a declarative hint at a search strategy is added to the model.This will reduce the time to implement high-performance local search, compared to programming from first principles.