Beyond the Holy Grail - Automatically Generating Constraint Propagators for Conjunctions of Time-Series Constraints

Abstract : The Holy Grail of programming was described in [7] as the separation of modelling which problem we want to solve, and the application of a tool (a Constraint Solver) to provide a solution from the model. This requires a sophisticated system, which up to now needed to be hand-coded by an expert. We want to go beyond this paradigm, by automatically discovering gaps in existing propagators, deriving a hypothesis about missing propagation, proving or disproving the hypothesis, and finally automatically generating an implementation of the improved constraint propagator. As an example we use the area of time-series constraints. We describe a method for discovering and proving generic invariants linking together several characteristics of an integer sequence; generic invariants are independent of the integer values used in the sequence, but are possibly parameterized by the sequence size. The method consists of three steps, namely (1) a mining phase where we systematically generate integer sequences up to a given size, and extract conjectures from the corresponding data sets, (2) a proof phase where we try to prove conjectures by checking whether the conjunction of multiple time-series constraints over this sequence is infeasible. We do this by exploiting the descriptions of time-series constraints as automata with accumula-tors. Finally we use proven conjectures in an (3) exploitation phase to improve the propagators for the constraints. Preliminary tests indicate that the discovered generic invariants can significantly speed up, both, the proof of infeasibility, and more surprisingly, the generation of solutions for a conjunction of time-series constraints on a common sequence.
Document type :
Conference papers
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-01651610
Contributor : Ekaterina Arafailova <>
Submitted on : Wednesday, November 29, 2017 - 11:15:55 AM
Last modification on : Tuesday, March 26, 2019 - 9:25:22 AM

File

workshop_holygrail.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01651610, version 1

Citation

Ekaterina Arafailova, Nicolas Beldiceanu, Helmut Simonis. Beyond the Holy Grail - Automatically Generating Constraint Propagators for Conjunctions of Time-Series Constraints. Workshop on Progress Towards the Holy Grail, Aug 2017, Melbourne, Australia. ⟨hal-01651610⟩

Share

Metrics

Record views

508

Files downloads

38