| 1. |
- 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.
|
|
| 2. |
- 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.
|
|
| 3. |
- 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.
|
|
| 4. |
- Guns, Tias, et al.
(författare)
-
MiningZinc : A declarative framework for constraint-based mining
- 2017
-
Ingår i: Artificial Intelligence. - Amsterdam, Netherlands : Elsevier. - 0004-3702 .- 1872-7921. ; 244, s. 6-29
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce MiningZinc, a declarative framework for constraint-based data mining. MiningZinc consists of two key components: a language component and an execution mechanism.First, the MiningZinc language allows for high-level and natural modeling of mining problems, so that MiningZinc models are similar to the mathematical definitions used in the literature. It is inspired by the Zinc family of languages and systems and supports user-defined constraints and functions.Secondly, the MiningZinc execution mechanism specifies how to compute solutions for the models. It is solver independent and supports both standard constraint solvers and specialized data mining systems. The high-level problem specification is first translated into a normalized constraint language (FlatZinc). Rewrite rules are then used to add redundant constraints or solve subproblems using specialized data mining algorithms or generic constraint programming solvers. Given a model, different execution strategies are automatically extracted that correspond to different sequences of algorithms to run. Optimized data mining algorithms, specialized processing routines and generic solvers can all be automatically combined.Thus, the MiningZinc language allows one to model constraint-based itemset mining problems in a solver independent way, and its execution mechanism can automatically chain different algorithms and solvers. This leads to a unique combination of declarative modeling with high-performance solving.
|
|
| 5. |
- Guns, Tias, et al.
(författare)
-
MiningZinc : A Modeling Language for Constraint-based Mining
- 2013
-
Ingår i: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. - : AAAI Press. - 9781577356332 ; , s. 1365-1372
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- We introduce MiningZinc, a general framework for constraint-based pattern mining, one of the most popular tasks in data mining. MiningZinc consists of two key components: a language component and a toolchain component.The language allows for high-level and natural modeling of mining problems, such that MiningZinc models closely resemble definitions found in the data mining literature. It is inspired by the Zincfamily of languages and systems and supports user-defined constraints and optimization criteria.The toolchain allows for finding solutions to the models. It ensures the solver independence of the language and supports both standard constraint solvers and specialized data mining systems. Automatic model transformations enable the efficient use of different solvers and systems.The combination of both components allows one to rapidly model constraint-based mining problems and execute these with a wide variety of methods. We demonstrate this experimentally for a number of well-known solvers and data mining tasks.
|
|
| 6. |
- Guns, Tias, et al.
(författare)
-
The MiningZinc Framework for Constraint-Based Itemset Mining
- 2013
-
Ingår i: 2013 IEEE 13th International Conference on Data Mining Workshops (ICDMW). - : IEEE. - 9780769551098 ; , s. 1081-1084
-
Konferensbidrag (refereegranskat)abstract
- We present Mining Zinc, a novel system for constraint-based pattern mining. It provides a declarative approach to data mining, where a user specifies a problem in terms of constraints and the system employs advanced techniques to efficiently find solutions. Declarative programming and modeling are common in artificial intelligence and in database systems, but not so much in data mining; by building on ideas from these communities, Mining Zinc advances the state-of-the-art of declarative data mining significantly. Key components of the Mining Zinc system are (1) a high-level and natural language for formalizing constraint-based itemset mining problems in models, and (2) an infrastructure for executing these models, which supports both specialized mining algorithms as well as generic constraint solving systems. A use case demonstrates the generality of the language, as well as its flexibility towards adding and modifying constraints and data, and the use of different solution methods.
|
|
| 7. |
- Ingmar, Linnea, et al.
(författare)
-
Modelling Diversity of Solutions
- 2020
-
Ingår i: Thirty-fourth AAAI Conference on Artificial Intelligence, the thirty-second innovative applications of artificial intelligence conference and the tenth AAAI symposium on educational advances in artificial intelligence. - : ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE. ; , s. 1528-1535
-
Konferensbidrag (refereegranskat)abstract
- For many combinatorial problems, finding a single solution is not enough. This is clearly the case for multi-objective optimization problems, as they have no single "best solution" and, thus, it is useful to find a representation of the non-dominated solutions (the Pareto frontier). However, it also applies to single objective optimization problems, where one may be interested in finding several (close to) optimal solutions that illustrate some form of diversity. The same applies to satisfaction problems. This is because models usually idealize the problem in some way, and a diverse pool of solutions may provide a better choice with respect to considerations that are omitted or simplified in the model. This paper describes a general framework for finding k diverse solutions to a combinatorial problem (be it satisfaction, single-objective or multi-objective), various approaches to solve problems in the framework, their implementations, and an experimental evaluation of their practicality.
|
|
| 8. |
- Reischuk, Raphael M., et al.
(författare)
-
Maintaining State in Propagation Solvers
- 2009
-
Ingår i: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING. - Berlin, Heidelberg : Springer. - 9783642042430 ; , s. 692-706
-
Konferensbidrag (refereegranskat)abstract
- Constraint propagation solvers interleave propagation, removing impossible values from variable domains, with search. The solver state is modified during propagation. But search requires the solver to return to a previous state. Hence a, propagation solver must determine how to maintain state during propagation and forward and backward search. This paper sets out the possible ways in which a propagation solver call choose to maintain state, and the restrictions that such choices place on the resulting system. Experiments illustrate the result of various choices for the three principle state components of a solver: variables, propagators, and dependencies between them. This paper also provides the first realistic comparison of trailing versus copying for state restoration.
|
|
| 9. |
- Schulte, Christian, et al.
(författare)
-
Perfect Derived Propagators
- 2008
-
Ingår i: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING. - Berlin, Heidelberg : Springer Berlin Heidelberg. ; , s. 571-575
-
Konferensbidrag (refereegranskat)abstract
- When implementing a propagator for a constraint, one must decide about variants: When implementing min , should one also implement max ? Should one implement linear equations both with and without coefficients? Constraint variants are ubiquitous: implementing them requires considerable effort, but yields better performance. This paper shows how to use variable views to derive perfect propagator variants: derived propagators inherit essential properties such as correctness and domain and bounds completeness.
|
|
| 10. |
- Schulte, Christian, et al.
(författare)
-
View-based propagator derivation
- 2013
-
Ingår i: Constraints. - : Springer. - 1383-7133 .- 1572-9354. ; 18:1, s. 75-107
-
Tidskriftsartikel (refereegranskat)abstract
- When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max Should one implement linear constraints both with unit and non-unit coefficients Constraint variants are ubiquitous: implementing them requires considerable (if not prohibitive) effort and decreases maintainability, but will deliver better performance than resorting to constraint decomposition. This paper shows how to use views to derive propagator variants, combining the efficiency of dedicated propagator implementations with the simplicity and effortlessness of decomposition. A model for views and derived propagators is introduced. Derived propagators are proved to be perfect in that they inherit essential properties such as correctness and domain and bounds consistency. Techniques for systematically deriving propagators such as transformation, generalization, specialization, and type conversion are developed. The paper introduces an implementation architecture for views that is independent of the underlying constraint programming system. A detailed evaluation of views implemented in Gecode shows that derived propagators are efficient and that views often incur no overhead. Views have proven essential for implementing Gecode, substantially reducing the amount of code that needs to be written and maintained.
|
|
