uu.seUppsala universitets publikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Time-series constraints: Improvements and application in CP and MIP contexts
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datalogi. (ASTRA)
Visa övriga samt affilieringar
2016 (Engelska)Ingår i: Integration of AI and OR Techniques in Constraint Programming, Springer, 2016, s. 18-34Konferensbidrag, Publicerat paper (Refereegranskat)
Ort, förlag, år, upplaga, sidor
Springer, 2016. s. 18-34
Serie
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9676
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:uu:diva-298447DOI: 10.1007/978-3-319-33954-2_2ISI: 000378993700002ISBN: 978-3-319-33953-5 (tryckt)OAI: oai:DiVA.org:uu-298447DiVA, id: diva2:946173
Konferens
CPAIOR 2016, May 29 – June 1, Banff, Canada
Tillgänglig från: 2016-05-12 Skapad: 2016-07-04 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
Ingår i avhandling
1. Analysis, synthesis and application of automaton-based constraint descriptions
Öppna denna publikation i ny flik eller fönster >>Analysis, synthesis and application of automaton-based constraint descriptions
2017 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

Constraint programming (CP) is a technology in which a combinatorial problem is modelled as a conjunction of constraints on variables ranging over given initial domains, and optionally an objective function on the variables. Such a model is given to a general-purpose solver performing systematic search to find constraint-satisfying domain values for the variables, giving an optimal value to the objective function. A constraint predicate (also known as a global constraint) does two things: from the modelling perspective, it allows a modeller to express a commonly occurring combinatorial substructure, for example that a set of variables must take distinct values; from the solving perspective, it comes with a propagation algorithm, called a propagator, which removes some but not necessarily all impossible values from the current domains of its variables when invoked during search.

Although modern CP solvers have many constraint predicates, often a predicate one would like to use is not available. In the past, the choices were either to reformulate the model or to write one's own propagator. In this dissertation, we contribute to the automatic design of propagators for new predicates.

Integer time series are often subject to constraints on the aggregation of the features of all maximal occurrences of some pattern. For example, the minimum width of the peaks may be constrained. Automata allow many constraint predicates for variable sequences, and in particular many time-series predicates, to be described in a high-level way. Our first contribution is an algorithm for generating an automaton-based predicate description from a pattern, a feature, and an aggregator.

It has previously been shown how to decompose an automaton-described constraint on a variable sequence into a conjunction of constraints whose predicates have existing propagators. This conjunction provides the propagation, but it is unknown how to propagate it efficiently. Our second contribution is a tool for deriving, in an off-line process, implied constraints for automaton-induced constraint decompositions to improve propagation. Further, when a constraint predicate functionally determines a result variable that is unchanged under reversal of a variable sequence, we provide as our third contribution an algorithm for deriving an implied constraint between the result variables for a variable sequence, a prefix thereof, and the corresponding suffix.

Ort, förlag, år, upplaga, sidor
Uppsala: Acta Universitatis Upsaliensis, 2017. s. 79
Serie
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1591
Nyckelord
constraint programming, constraint predicates, global constraints, automata, automaton-described constraint predicates, automaton-induced constraint decompositions, implied constraints, time-series constraints, transducers, automaton invariants
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Datavetenskap
Identifikatorer
urn:nbn:se:uu:diva-332149 (URN)978-91-513-0132-7 (ISBN)
Disputation
2017-12-15, ITC 2446, Polacksbacken, Lägerhyddsvägen 2, Uppsala, 13:15 (Engelska)
Opponent
Handledare
Tillgänglig från: 2017-11-22 Skapad: 2017-10-24 Senast uppdaterad: 2018-03-07

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Flener, PierreFrancisco Rodríguez, María AndreínaPearson, Justin

Sök vidare i DiVA

Av författaren/redaktören
Flener, PierreFrancisco Rodríguez, María AndreínaPearson, Justin
Av organisationen
Datalogi
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 796 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf