uu.seUppsala University Publications
Change search
Link to record
Permanent link

Direct link
BETA
Pearson, Justin
Alternative names
Publications (10 of 97) Show all publications
Björdal, G., Flener, P., Pearson, J. & Stuckey, P. J. (2019). Exploring declarative local-search neighbourhoods with constraint programming. In: Thomas Schiex and Simon de Givry (Ed.), Principles and Practice of Constraint Programming: . Paper presented at 25th International Conference, CP 2019, Stamford, CT, USA, September 30 – October 4, 2019 (pp. 37-53). Switzerland: Springer, 11802
Open this publication in new window or tab >>Exploring declarative local-search neighbourhoods with constraint programming
2019 (English)In: Principles and Practice of Constraint Programming / [ed] Thomas Schiex and Simon de Givry, Switzerland: Springer, 2019, Vol. 11802, p. 37-53Conference paper, Published paper (Refereed)
Abstract [en]

Using constraint programming (CP) to explore a local-search neighbourhood was first tried in the mid 1990s. The advantage is that constraint propagation can quickly rule out uninteresting neighbours, sometimes greatly reducing the number actually probed. However, a CP model of the neighbourhood has to be handcrafted from the model of the problem: this can be difficult and tedious. That research direction appears abandoned since large-neighbourhood search (LNS) and constraint-based local search (CBLS) arose as alternatives that seem easier to use. Recently, the notion of declarative neighbourhood was added to the technology-independent modelling language MiniZinc, for use by any backend to MiniZinc, but currently only used by a CBLS backend. We demonstrate that declarative neighbourhoods are indeed technology-independent by using the old idea of CP-based neighbourhood exploration: we explain how to encode automatically a declarative neighbourhood into a CP model of the neighbourhood. This enables us to lift any CP solver into a local-search backend to MiniZinc. Our prototype is competitive with CP, CBLS, and LNS backends to MiniZinc.

Place, publisher, year, edition, pages
Switzerland: Springer, 2019
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 11802
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-396813 (URN)10.1007/978-3-030-30048-7_3 (DOI)
Conference
25th International Conference, CP 2019, Stamford, CT, USA, September 30 – October 4, 2019
Funder
Swedish Research Council, 2015-04910
Available from: 2019-11-18 Created: 2019-11-18 Last updated: 2019-11-29Bibliographically approved
Björdal, G., Flener, P. & Pearson, J. (2019). Generating compound moves in local search by hybridisation with complete search. In: L.-M. Rousseau and K. Stergiou (Ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research: . Paper presented at CPAIOR 2019, 4 – 7 June, Thessaloniki, Greece (pp. 95-111). Springer, 11494
Open this publication in new window or tab >>Generating compound moves in local search by hybridisation with complete search
2019 (English)In: Integration of Constraint Programming, Artificial Intelligence, and Operations Research / [ed] L.-M. Rousseau and K. Stergiou, Springer, 2019, Vol. 11494, p. 95-111Conference paper, Published paper (Refereed)
Abstract [en]

A black-box local-search backend to a solving-technology-independent modelling language, such as MiniZinc, automatically infers from the structure of a declarative model for a satisfaction or optimisation problem a combination of a neighbourhood, heuristic, and meta-heuristic. These ingredients are then provided to a local-search solver, but are manually designed in a handcrafted local-search algorithm. However, such a backend can perform poorly due to model structure that is inappropriate for local search, for example when it considers moves modifying only variables that represent auxiliary information. Towards overcoming such inefficiency, we propose compound-move generation, an extension to local-search solvers that uses a complete-search solver in order to augment moves modifying non-auxiliary variables so that they also modify auxiliary ones. Since compound-move generation is intended to be applied to such models, we discuss how to identify them.

We present several refinements of compound-move generation and show its very positive impact on several third-party models. This helps reduce the unavoidable gap between black-box local search and local-search algorithms crafted by experts.

Place, publisher, year, edition, pages
Springer, 2019
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 11494
National Category
Computer Sciences
Research subject
Computing Science
Identifiers
urn:nbn:se:uu:diva-396494 (URN)10.1007/978-3-030-19212-9_7 (DOI)978-3-030-19212-9 (ISBN)
Conference
CPAIOR 2019, 4 – 7 June, Thessaloniki, Greece
Funder
Swedish Research Council, 2015-04910
Available from: 2019-11-18 Created: 2019-11-18 Last updated: 2019-11-29Bibliographically approved
Björdal, G., Flener, P., Pearson, J., Stuckey, P. J. & Tack, G. (2018). Declarative local-search neighbourhoods in MiniZinc. In: PROCEEDINGS OF THE 2018 IEEE 30TH INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE (ICTAI): . Paper presented at 30th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), NOV 05-07, 2018, Volos, GREECE (pp. 98-105). IEEE Computer Society
Open this publication in new window or tab >>Declarative local-search neighbourhoods in MiniZinc
Show others...
2018 (English)In: PROCEEDINGS OF THE 2018 IEEE 30TH INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE (ICTAI), IEEE Computer Society, 2018, p. 98-105Conference paper, Published paper (Refereed)
Abstract [en]

The aim of solver-independent modelling is to create a model of a satisfaction or optimisation problem independent of a particular technology. This avoids early commitment to a solving technology and allows easy comparison of technologies. MiniZinc is a solver-independent modelling language, supported by CP, MIP, SAT, SMT, and constraint-based local search (CBLS) backends. Some technologies, in particular CP and CBLS, require not only a model but also a search strategy. While backends for these technologies offer default search strategies, it is often beneficial to include in a model a user-specified search strategy for a particular technology, especially if the strategy can encapsulate knowledge about the problem structure. This is complex since a local-search strategy (comprising a neighbourhood, a heuristic, and a meta-heuristic) is often tightly tied to the model. Hence we wish to use the same language for specifying the model and the local search. We show how to extend MiniZinc so that one can attach a fully declarative neighbourhood specification to a model, while maintaining the solver-independence of the language. We explain how to integrate a model-specific declarative neighbourhood with an existing CBLS backend for MiniZinc.

Place, publisher, year, edition, pages
IEEE Computer Society, 2018
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-368077 (URN)10.1109/ICTAI.2018.00025 (DOI)000457750200015 ()978-1-5386-7449-9 (ISBN)
Conference
30th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), NOV 05-07, 2018, Volos, GREECE
Funder
Swedish Research Council, 2015-04910
Available from: 2018-12-17 Created: 2018-12-03 Last updated: 2019-02-28Bibliographically approved
Dubois, C., Grinchtein, O., Pearson, J. & Carlsson, M. (2018). Exploring properties of a telecommunication protocol with message delay using interactive theorem prover. In: Software Engineering and Formal Methods: . Paper presented at SEFM 2018, June 27–29, Toulouse, France (pp. 239-253). Springer
Open this publication in new window or tab >>Exploring properties of a telecommunication protocol with message delay using interactive theorem prover
2018 (English)In: Software Engineering and Formal Methods, Springer, 2018, p. 239-253Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Springer, 2018
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 10886
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-366393 (URN)10.1007/978-3-319-92970-5_15 (DOI)000445248600015 ()978-3-319-92969-9 (ISBN)
Conference
SEFM 2018, June 27–29, Toulouse, France
Available from: 2018-05-30 Created: 2018-11-21 Last updated: 2018-11-30Bibliographically approved
Francisco Rodríguez, M. A., Flener, P. & Pearson, J. (2017). Automatic generation of descriptions of time-series constraints. In: IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI): . Paper presented at IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI), Boston, MA, November 6–8, 2017 (pp. 102-109). IEEE Computer Society
Open this publication in new window or tab >>Automatic generation of descriptions of time-series constraints
2017 (English)In: IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI), IEEE Computer Society, 2017, p. 102-109Conference paper, Published paper (Refereed)
Abstract [en]

Integer time series are often subject to constraints on the aggregation of the features of all occurrences of some pattern within the series. For example, the number of inflexions may be constrained, or the sum of the peak maxima, or the minimum of the valley widths. Many time-series constraints can be described by transducers. The output alphabet of such a transducer consists of symbols that denote the phases of identifying the maximal occurrences of a pattern. It was recently shown how to synthesise automatically a constraint propagator and a constraint checker from such a transducer, which however has to be designed manually from a pattern. Here we define a large class of patterns, present an algorithm for automatically generating a low-level transducer from such a high-level pattern, and prove it correct. This class covers all 20 patterns of the Time-Series Constraint Catalogue, which can now be automatically extended at will.

Place, publisher, year, edition, pages
IEEE Computer Society, 2017
Series
Proceedings-International Conference on Tools With Artificial Intelligence, ISSN 1082-3409
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-332145 (URN)10.1109/ICTAI.2017.00027 (DOI)000435294700016 ()978-1-5386-3876-7 (ISBN)
Conference
IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI), Boston, MA, November 6–8, 2017
Funder
Swedish Research Council, 2012-4908Swedish Research Council, 2015-0491
Available from: 2018-06-07 Created: 2017-10-24 Last updated: 2019-08-28Bibliographically approved
Scott, J. D., Flener, P., Pearson, J. & Schulte, C. (2017). Design and implementation of bounded-length sequence variables. In: Integration of AI and OR Techniques in Constraint Programming: . Paper presented at CPAIOR 2017, June 5–8, Padua, Italy (pp. 51-67).
Open this publication in new window or tab >>Design and implementation of bounded-length sequence variables
2017 (English)In: Integration of AI and OR Techniques in Constraint Programming, 2017, p. 51-67Conference paper, Published paper (Refereed)
Abstract [en]

We present the design and implementation of bounded length sequence (BLS) variables for a CP solver. The domain of a BLS variable is represented as the combination of a set of candidate lengths and a sequence of sets of candidate characters. We show how this representation, together with requirements imposed by propagators, affects the implementation of BLS variables for a copying CP solver, most importantly the closely related decisions of data structure, domain restriction operations, and propagation events. The resulting implementation outperforms traditional bounded-length string representations for CP solvers, which use a fixed-length array of candidate characters and a padding symbol.

Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 10335
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-334654 (URN)10.1007/978-3-319-59776-8_5 (DOI)000434086200005 ()978-3-319-59775-1 (ISBN)
Conference
CPAIOR 2017, June 5–8, Padua, Italy
Funder
Swedish Research Council, 2015-4910
Available from: 2017-05-31 Created: 2017-11-25 Last updated: 2018-11-12Bibliographically approved
Amadini, R., Flener, P., Pearson, J., Scott, J. D., Stuckey, P. J. & Tack, G. (2017). MiniZinc with strings. In: Logic-Based Program Synthesis and Transformation: . Paper presented at 26th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR), September 6–8, 2016, Edinburgh, Scotland (pp. 59-75). Springer
Open this publication in new window or tab >>MiniZinc with strings
Show others...
2017 (English)In: Logic-Based Program Synthesis and Transformation, Springer, 2017, p. 59-75Conference paper, Published paper (Refereed)
Abstract [en]

Strings are extensively used in modern programming languages and constraints over strings of unknown length occur in a wide range of real-world applications such as software analysis and verification, testing, model checking, and web security. Nevertheless, practically no constraint programming solver natively supports string constraints. We introduce string variables and a suitable set of string constraints as builtin features of the MiniZinc modelling language. Furthermore, we define an interpreter for converting a MiniZinc model with strings into a FlatZinc instance relying only on integer variables. This conversion is obtained via rewrite rules, and does not require any extension of the existing FlatZinc specification. This provides a user-friendly interface for modelling combinatorial problems with strings, and enables both string and non-string solvers to actually solve such problems.

Place, publisher, year, edition, pages
Springer, 2017
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 10184
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-309538 (URN)10.1007/978-3-319-63139-4_4 (DOI)000441349700004 ()978-3-319-63138-7 (ISBN)978-3-319-63139-4 (ISBN)
Conference
26th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR), September 6–8, 2016, Edinburgh, Scotland
Funder
Swedish Research Council, 2015-04910Australian Research Council, LP140100437
Available from: 2017-07-25 Created: 2016-12-05 Last updated: 2019-02-28Bibliographically approved
Carlsson, M., Grinchtein, O. & Pearson, J. (2017). Modelling and verification of user interactions using constraint programming. In: Proc. 3rd International Conference on Software Quality, Reliability and Security: . Paper presented at IEEE International Conference On Software Quality, Reliability And Security Companion (Qrs-C), 2017, July 25–29, Prague, Czech Republic. (pp. 541-547). IEEE Computer Society
Open this publication in new window or tab >>Modelling and verification of user interactions using constraint programming
2017 (English)In: Proc. 3rd International Conference on Software Quality, Reliability and Security, IEEE Computer Society, 2017, p. 541-547Conference paper, Published paper (Refereed)
Abstract [en]

Graphical user interfaces are important components of today's software. User interfaces often require checking correctness of user interactions. In web applications such checks can be a part of the JavaScript code. User interfaces in web applications can evolve, some elements can be removed and new elements can be added. To check JavaScript code covers all possible incorrect scenarios in user interactions in web application, constraint programming is used. We use the MiniZinc constraint modelling language to model incorrect user behaviour and to convert JavaScript code into a constraint model. Then we perform an equivalence check to find deviations in JavaScript code. The approach was applied to design user interface of an industrial software product.

Place, publisher, year, edition, pages
IEEE Computer Society, 2017
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-334655 (URN)10.1109/QRS-C.2017.92 (DOI)000426819400084 ()978-1-5386-2072-4 (ISBN)978-1-5386-2073-1 (ISBN)
Conference
IEEE International Conference On Software Quality, Reliability And Security Companion (Qrs-C), 2017, July 25–29, Prague, Czech Republic.
Funder
Swedish Foundation for Strategic Research
Available from: 2017-08-18 Created: 2017-11-25 Last updated: 2018-06-12Bibliographically approved
Monette, J.-N., Beldiceanu, N., Flener, P. & Pearson, J. (2016). A parametric propagator for pairs of SUM constraints with a discrete convexity property. Artificial Intelligence, 241, 170-190
Open this publication in new window or tab >>A parametric propagator for pairs of SUM constraints with a discrete convexity property
2016 (English)In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 241, p. 170-190Article in journal (Refereed) Published
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-309537 (URN)10.1016/j.artint.2016.08.006 (DOI)000387518000007 ()
Available from: 2016-09-14 Created: 2016-12-05 Last updated: 2018-01-13Bibliographically approved
Arafailova, E., Beldiceanu, N., Douence, R., Carlsson, M., Flener, P., Francisco Rodríguez, M. A., . . . Simonis, H. (2016). Global Constraint Catalog: Volume II, time-series constraints.
Open this publication in new window or tab >>Global Constraint Catalog: Volume II, time-series constraints
Show others...
2016 (English)Report (Other academic)
Series
Computing Research Repository ; 1609.08925
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-309541 (URN)
Available from: 2016-09-26 Created: 2016-12-05 Last updated: 2018-01-13Bibliographically approved
Organisations

Search in DiVA

Show all publications