| 1. |
|
|
| 2. |
- Amadini, Roberto, et al.
(författare)
-
MiniZinc with strings
- 2017
-
Ingår i: Logic-Based Program Synthesis and Transformation. - Cham : Springer. - 9783319631387 - 9783319631394 ; , s. 59-75
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 3. |
|
|
| 4. |
- Arafailova, Ekaterina, et al.
(författare)
-
Global Constraint Catalog Volume II: Time-Series Constraints
- 2016
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- First this report presents a restricted set of finite transducers used to synthesise structural time-series constraints described by means of a multi-layered function composition scheme. Second it provides the corresponding synthesised catalogue of structural time-series constraints where each constraint is explicitly described in terms of automata with accumulators.
|
|
| 5. |
- Arafailova, Ekaterina, et al.
(författare)
-
Systematic Derivation of Bounds and Glue Constraints for Time-Series Constraints
- 2016
-
Ingår i: Principles and Practice of Constraint Programming. - Cham : Springer Publishing Company. - 9783319449524 - 9783319449531 ; , s. 13-29
-
Konferensbidrag (refereegranskat)abstract
- Integer time series are often subject to constraints on the aggregation of the integer 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 peak widths. It is currently unknown how to maintain domain consistency efficiently on such constraints. We propose parametric ways of systematically deriving glue constraints, which are a particular kind of implied constraints, as well as aggregation bounds that can be added to the decomposition of time-series constraints [5]. We evaluate the beneficial propagation impact of the derived implied constraints and bounds, both alone and together.
|
|
| 6. |
|
|
| 7. |
|
|
| 8. |
- Beldiceanu, Nicolas, et al.
(författare)
-
A Modelling Pearl with Sortedness Constraints
- 2015. - 9
-
Ingår i: GCAI 2015. Global Conference on Artificial Intelligence. - : EasyChair. ; , s. 27-41
-
Konferensbidrag (refereegranskat)abstract
- Some constraint programming solvers and constraint modelling languages feature the Sort(L,P,S) constraint, which holds if S is a nondecreasing rearrangement of the list L, the permutation being made explicit by the optional list P. However, such sortedness constraints do not seem to be used much in practice. We argue that reasons for this neglect are that it is impossible to require the underlying sort to be stable, so that Sort cannot be guaranteed to be a total-function constraint, and that L cannot contain tuples of variables, some of which form the key for the sort. To overcome these limitations, we introduce the StableKeysort constraint, decompose it using existing constraints, and propose a propagator. This new constraint enables a powerful modelling idiom, which we illustrate by elegant and scalable models of two problems that are otherwise hard to encode as constraint programs.
|
|
| 9. |
|
|
| 10. |
|
|
| 11. |
|
|
| 12. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Combining Tree Partitioning, Precedence, Incomparability, and Degree Constraints, with an Application to Phylogenetic and Ordered-Path Problems
- 2006
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- The \emphtree and \emphpath constraints, for digraph partitioning by vertex disjoint trees and paths respectively, are unified within a single global constraint, including a uniform treatment of a variety of useful side constraints, such as precedence, incomparability, and degree constraints. The approach provides a sharp improvement over an existing \emphpath constraint, but can also efficiently handle tree problems, such as the phylogenetic supertree construction problem. The key point of the filtering is to take partially into account the strong interactions between the tree partitioning problem and all the side constraints.
|
|
| 13. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Linking Prefixes and Suffixes for Constraints Encoded Using Automata with Accumulators
- 2014. - 7
-
Ingår i: Principles and Practice of Constraint Programming. - Cham : Springer International Publishing. - 9783319104270 ; , s. 142-157
-
Konferensbidrag (refereegranskat)abstract
- Consider a constraint on a sequence of variables functionally determining a result variable that is unchanged under reversal of the sequence. Most such constraints have a compact encoding via an automaton augmented with accumulators, but it is unknown how to maintain domain consistency efficiently for most of them. Using such an automaton for such a constraint, we derive an implied constraint between the result variables for a sequence, a prefix thereof, and the corresponding suffix. We show the usefulness of this implied constraint in constraint solving, both by local search and by propagation-based systematic search.
|
|
| 14. |
- Beldiceanu, Nicolas, et al.
(författare)
-
On matrices, automata, and double counting
- 2010
-
Ingår i: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. - Berlin : Springer-Verlag. ; , s. 10-24
-
Konferensbidrag (refereegranskat)
|
|
| 15. |
|
|
| 16. |
- Beldiceanu, Nicolas, et al.
(författare)
-
On the Reification of Global Constraints
- 2012. - 8
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- We introduce a simple idea for deriving reified global constraints in a systematic way. It is based on the observation that most global constraints can be reformulated as a conjunction of pure functional dependency constraints together with a constraint that can be easily reified. We first show how the core constraints of the Global Constraint Catalogue can be reified and we then identify several reification categories that apply to at least 82% of the constraints in the Global Constraint Catalogue.
|
|
| 17. |
- Beldiceanu, Nicolas, et al.
(författare)
-
On the reification of global constraints
- 2013
-
Ingår i: Constraints. - : Springer Science and Business Media LLC. - 1383-7133 .- 1572-9354. ; 18:1, s. 1-6
-
Tidskriftsartikel (refereegranskat)
|
|
| 18. |
- Beldiceanu, Nicolas, et al.
(författare)
-
On the Reification of Global Constraints (Abstract)
- 2015
-
Ingår i: Principles and practice of constraint programming, CP 2015. - : SPRINGER-VERLAG BERLIN. - 9783319232195 - 9783319232188 ; , s. 733-733
-
Konferensbidrag (refereegranskat)
|
|
| 19. |
|
|
| 20. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Propagating regular counting constraints
- 2014
-
Ingår i: Proc. 28th AAAI Conference on Artificial Intelligence. - Palo Alto, CA : AAAI Press. - 9781577356806 ; , s. 2616-2622
-
Konferensbidrag (refereegranskat)
|
|
| 21. |
- Beldiceanu, Nicolas, et al.
(författare)
-
The tree constraint
- 2005
-
Ingår i: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: Second International Conference, CPAIOR 2005, Proceedings. - 3540261524 ; , s. 64-78
-
Konferensbidrag (refereegranskat)
|
|
| 22. |
|
|
| 23. |
|
|
| 24. |
- Björdal, Gustav, et al.
(författare)
-
Declarative local-search neighbourhoods in MiniZinc
- 2018
-
Ingår i: PROCEEDINGS OF THE 2018 IEEE 30TH INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE (ICTAI). - : IEEE Computer Society. - 9781538674499 ; , s. 98-105
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 25. |
- Björdal, Gustav, 1991-, et al.
(författare)
-
Exploring declarative local-search neighbourhoods with constraint programming
- 2019
-
Ingår i: Principles and Practice of Constraint Programming. - Switzerland : Springer. - 9783030300470 - 9783030300487 ; , s. 37-53
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 26. |
- Björdal, Gustav, 1991-
(författare)
-
From Declarative Models to Local Search
- 2021
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- A solver is a general-purpose software for solving optimisation problems. It takes as input a description of a problem, called a model, and uses a collection of algorithms, called its solving technology, to ideally produce an optimal solution as output. Most solvers have a modelling language that cannot be processed by other solvers. This means that there is a risk of making an early commitment to a solver and its technology when writing a model. To address this risk, and to increase the accessibility of solvers, there has been a push for technology-independent modelling languages, a notable one being MiniZinc.A model written in MiniZinc is transformed by the MiniZinc toolchain in order to suit a targeted solver and its technology. However, for a solver to process a MiniZinc model, it also requires what is called a backend for MiniZinc. A backend translates the transformed MiniZinc model into the solver’s own modelling language and synthesises any components not in a MiniZinc model that the solver (or its technology) requires.The solving technology called constraint-based local search (CBLS) is based on the popular algorithm design methodology called local search, which often quickly produces near-optimal solutions, even to large problems. So, with the advent of CBLS solvers, there is a need for CBLS backends to modelling languages like MiniZinc.This thesis contributes to three research topics. First, it shows for the first time how to create a CBLS backend for a technology-independent modelling language, namely MiniZinc, and it shows that CBLS via MiniZinc can be competitive for solving optimisation problems. Second, it extends MiniZinc with concepts from local search, and shows that these concepts can be used even by other technologies towards designing new types of solvers. Third, it extends the utilisation of another technology, namely constraint programming, inside local-search solvers and backends.These contributions make local search accessible to all users of modelling languages like MiniZinc, and allow some optimisation problems to be solved more efficiently via such languages.
|
|
| 27. |
- Björdal, Gustav, 1991-, et al.
(författare)
-
Generating compound moves in local search by hybridisation with complete search
- 2019
-
Ingår i: Integration of Constraint Programming, Artificial Intelligence, and Operations Research. - Cham : Springer. - 9783030192129 ; , s. 95-111
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 28. |
- Björdal, Gustav, 1991-, et al.
(författare)
-
Solving Satisfaction Problems using Large-Neighbourhood Search
- 2020
-
Ingår i: Principles and Practice of Constraint Programming. - Cham : Springer International Publishing. - 9783030584740 - 9783030584757 ; , s. 55-71
-
Konferensbidrag (refereegranskat)abstract
- Large-neighbourhood search (LNS) improves an initial solution, hence it is not directly applicable to satisfaction problems. In order to use LNS in a constraint programming (CP) framework to solve satisfaction problems, we usually soften some hard-to-satisfy constraints by replacing them with penalty-function constraints. LNS is then used to reduce their penalty to zero, thus satisfying the original problem. However, this can give poor performance as the penalties rarely cause propagation and therefore do not drive each CP search, and by extension the LNS search, towards satisfying the replaced constraints until very late. Our key observation is that entirely replacing a constraint is often overkill, as the propagator for the replaced constraint could have performed some propagation without causing backtracking. We propose the notion of a non-failing propagator, which is subsumed just before causing a backtrack. We show that, by only making a few changes to an existing CP solver, any propagator can be made non-failing without modifying its code. Experimental evaluation shows that non-failing propagators, when used in conjunction with penalties, can greatly improve LNS performance compared to just having penalties. This allows us to leverage the power of the many sophisticated propagators that already exist in CP solvers, in order to use LNS for solving hard satisfaction problems and for finding initial solutions to hard-to-satisfy optimisation problems.
|
|
| 29. |
- Dekker, Jip J., et al.
(författare)
-
Auto-tabling for subproblem presolving in MiniZinc
- 2017
-
Ingår i: Constraints. - : Springer Science and Business Media LLC. - 1383-7133 .- 1572-9354. ; 22:4, s. 512-529
-
Tidskriftsartikel (refereegranskat)abstract
- A well-known and powerful constraint model reformulation is to compute the solutions to a model part, say a custom constraint predicate, and tabulate them within an extensional constraint that replaces that model part. Despite the possibility of achieving higher solving performance, this tabling reformulation is often not tried, because it is tedious to perform; further, if successful, it obfuscates the original model. In order to encourage modellers to try tabling, we extend the MiniZinc toolchain to perform the automatic tabling of suitably annotated predicate definitions, without requiring any changes to solvers, thereby eliminating both the tedium and the obfuscation. Our experiments show that automated tabling yields the same tables as manual tabling, and that tabling is beneficial for solvers of several solving technologies.
|
|
| 30. |
|
|
| 31. |
|
|
| 32. |
- Flener, Pierre, et al.
(författare)
-
A Complete Characterisation of the Classification Tree Problem
- 2008
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Finding a classification tree over a given set of elements that is compatible with a given family of classification trees over subsets of that set is a common problem in many application areas, such as the historical analysis of languages, the theory of relational databases, and phylogenetic supertree construction. We present a constraint programming approach to this problem. First, we introduce a natural and compact graph representation of a family of classification trees. Second, we provide a complete filtering algorithm for the classification tree problem, based on this normal form.
|
|
| 33. |
|
|
| 34. |
- Flener, Pierre
(författare)
-
Achievements and prospects of program synthesis
- 2002
-
Ingår i: Computational Logic: Logic Programming and Beyond;Computational Logic: Logic Programming and Beyond; Essays in Honour of Robert A. Kowalski. - : Springer-Verlag. ; , s. 310-346
-
Bokkapitel (refereegranskat)
|
|
| 35. |
|
|
| 36. |
|
|
| 37. |
|
|
| 38. |
|
|
| 39. |
- Flener, Pierre, et al.
(författare)
-
An introduction to inductive programming
- 2008
-
Ingår i: Artificial Intelligence Review. - : Springer Science and Business Media LLC. - 0269-2821 .- 1573-7462. ; 29:1, s. 45-62
-
Tidskriftsartikel (refereegranskat)
|
|
| 40. |
|
|
| 41. |
|
|
| 42. |
|
|
| 43. |
|
|
| 44. |
|
|
| 45. |
- Flener, Pierre, et al.
(författare)
-
Constraint Programming in Sweden
- 2009
-
Ingår i: IEEE Intelligent Systems. - : IEEE Press. - 1541-1672. ; 24:2, s. 87-89
-
Forskningsöversikt (övrigt vetenskapligt/konstnärligt)
|
|
| 46. |
|
|
| 47. |
|
|
| 48. |
- Flener, Pierre, et al.
(författare)
-
Efficient structural symmetry breaking for constraint satisfaction problems
- 2007. - 1
-
Ingår i: Proceedings of the International Symmetry Conference, Edinburgh, UK. - : Department of Information Technology, Uppsala University.
-
Konferensbidrag (refereegranskat)abstract
- Symmetry breaking for constraint satisfaction problems (CSPs) has attracted considerable attention in recent years. Various general schemes have been proposed to eliminate symmetries. In general, these schemes may take exponential space or time to eliminate all the symmetries. We identify several classes of CSPs that encompass many practical problems and for which symmetry breaking for various forms of value and variable interchangeability is tractable using dedicated search procedures or symmetry-breaking constraints that allow nogoods and their symmetrically equivalent solutions to be stored and checked efficiently.
|
|
| 49. |
|
|
| 50. |
- Flener, Pierre, et al.
(författare)
-
Financial portfolio optimisation
- 2004
-
Ingår i: 10th International Conference on Principles and Practice of Constraint Programming. ; , s. 227-241
-
Konferensbidrag (refereegranskat)
|
|
