Xtext is a framework for the development of languages, which also generates all the typical and recurrent artifacts for a fully-fledged IDE on top of Eclipse. the validation (e.g., checking the correctness of programs...
详细信息
Many existing global constraints can be encoded as a conjunction of among constraints. An among constraint holds if the number of the variables in its scope whose value belongs to a prespecified set, which we call its...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
Many existing global constraints can be encoded as a conjunction of among constraints. An among constraint holds if the number of the variables in its scope whose value belongs to a prespecified set, which we call its range, is within some given bounds. It is known that domain filtering algorithms can benefit from reasoning about the interaction of among constraints so that values can be filtered out taking into consideration several among constraints simultaneously. the present paper embarks into a systematic investigation on the circumstances under which it is possible to obtain efficient and complete domain filtering algorithms for conjunctions of among constraints. We start by observing that restrictions on boththe scope and the range of the among constraints are necessary to obtain meaningful results. then, we derive a domain flow-based filtering algorithm and present several applications. In particular, it is shown that the algorithm unifies and generalizes several previous existing results.
We revisit the Interactive CSP framework (ICSP) and propose a, new: somewhat more general model, which we call Cost-Driven Interactive CSP (CICSP). First, we extend the value acquisition by a more general concept of c...
详细信息
ISBN:
(纸本)9783642042430
We revisit the Interactive CSP framework (ICSP) and propose a, new: somewhat more general model, which we call Cost-Driven Interactive CSP (CICSP). First, we extend the value acquisition by a more general concept of constraint relaxation. Second, we loosen the basic assumption of ICSP that "value acquisition is expensive" by introducing external cost functions of the constraint relaxation and the constraint propagation effort. We also propose a general INTERACTIVE RELAXATION algorithm template that. is designated for CICSP. the effectiveness of this approach is illustrated oil a real-life scenario from the Functional Test Generation problem domain.
A conceptual clustering is a set of formal concepts (i.e., closed itemsets) that defines a partition of a set of transactions. Finding a conceptual clustering is an NP-complete problem for which constraintprogramming...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
A conceptual clustering is a set of formal concepts (i.e., closed itemsets) that defines a partition of a set of transactions. Finding a conceptual clustering is an NP-complete problem for which constraintprogramming (CP) and Integer Linear programming (ILP) approaches have been recently proposed. We introduce new CP models to solve this problem: a pure CP model that uses set constraints, and an hybrid model that uses a data mining tool to extract formal concepts in a preprocessing step and then uses CP to select a subset of formal concepts that defines a partition. We compare our new models with recent CP and ILP approaches on classical machine learning instances. We also introduce a new set of instances coming from a real application case, which aims at extracting setting concepts from an Enterprise Resource Planning (ERP) software. We consider two classic criteria to optimize, i.e., the frequency and the size. We show that these criteria lead to extreme solutions with either very few small formal concepts or many large formal concepts, and that compromise clusterings may be obtained by computing the Pareto front of non dominated clusterings.
Linear integer constraints are one of the most important constraints in combinatorial problems since they are commonly found in many practical applications. Typically, encoding linear constraints to SAT performs poorl...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Linear integer constraints are one of the most important constraints in combinatorial problems since they are commonly found in many practical applications. Typically, encoding linear constraints to SAT performs poorly in problems withthese constraints in comparison to constraintprogramming (CP) or mixed integer programming (MIP) solvers. But some problems contain a mix of combinatoric constraints and linear constraints, where encoding to SAT is highly effective. In this paper we define new approaches to encoding linear constraints into SAT, by extending encoding methods for pseudo-Boolean constraints. Experimental results show that these methods are not only better than the state-of-the-art SAT encodings, but also improve on MIP and CP solvers on appropriate problems. Combining the new encoding with lazy decomposition, which during runtime only encodes constraints that are important to the solving process that occurs, gives a robust approach to many highly combinatorial problems involving linear constraints.
Personalisation and context-awareness are fundamental concerns in Telephony. this paper introduces a rule-based system - 4CRULES - which enables context-sensitive call control by the means of feature configuration rul...
详细信息
ISBN:
(纸本)9783642153952
Personalisation and context-awareness are fundamental concerns in Telephony. this paper introduces a rule-based system - 4CRULES - which enables context-sensitive call control by the means of feature configuration rules. 4CRULES is interoperable with standard context services and compositional feature architectures. It has been designed to resolve feature interactions, manage conflicting preferences, and mitigate the uncertainty affecting context data. this is achieved through a constraint optimisation model that maximises adherence to user requirements and domain constraints. Experiments on a suite of instances confirm the practicality of the approach and highlight performance- and adherence-critical factors.
It has long been accepted that dynamic variable ordering heuristics outperform static orderings. But just how dynamic are dynamic variable ordering heuristics? this paper examines the behaviour of a number of heuristi...
详细信息
ISBN:
(纸本)3540652248
It has long been accepted that dynamic variable ordering heuristics outperform static orderings. But just how dynamic are dynamic variable ordering heuristics? this paper examines the behaviour of a number of heuristics: and attempts to measure the entropy of the search process at different depths in the search tree.
Table constraints play an important role within constraintprogramming. Recently, many schemes or algorithms have been proposed to propagate table constraints or/and to compress their representation. We show that simp...
详细信息
ISBN:
(纸本)9783540859574
Table constraints play an important role within constraintprogramming. Recently, many schemes or algorithms have been proposed to propagate table constraints or/and to compress their representation. We show that simple tabular reduction (STR), a technique proposed by J. Ullmann to dynamically maintain the tables of Supports, is very often the most efficient practical approach to enforce generalized arc consistency within MAC. We also describe an optimization of STR which allows limiting the number of operations related to validity checking or search of supports. Interestingly enough, this optimization makes STIR potentially r times faster where r is the arity of the constraint(s). the results of an extensive experimentation that we have conducted with respect to random and structured instances indicate that the optimized algorithm we propose is usually around twice as fast its the original STR and can be up to one order of magnitude faster than previous state-of-the-art algorithms on some series of instances.
this paper proposes the framework of branch-and-check with explanations (BCE), a branch-and-check method where combinatorial cuts are found by general-purpose conflict analysis, rather than by specialized separation a...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
this paper proposes the framework of branch-and-check with explanations (BCE), a branch-and-check method where combinatorial cuts are found by general-purpose conflict analysis, rather than by specialized separation algorithms. Specifically, the method features a master problem that ignores combinatorial constraints, and a feasibility sub-problem that uses propagation to check the feasibility of these constraints and performs conflict analysis to derive nogood cuts. the BCE method also leverages conflict-based branching rules and strengthens cuts in a post-processing step. Experimental results on the Vehicle Routing Problem with Time Windows show that BCE is a potential alternative to branch-and-cut. In particular, BCE dominates branch-and-cut, both in proving optimality and in finding high-quality solutions quickly.
Routing problems appear in many practical applications. In the context of constraintprogramming, circuit constraints have been successfully developed to handle problems like the well-known Traveling Salesman Problem ...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
Routing problems appear in many practical applications. In the context of constraintprogramming, circuit constraints have been successfully developed to handle problems like the well-known Traveling Salesman Problem or the Vehicle Routing Problem. these kind of constraints are linked to the search for a Hamiltonian circuit in a graph. In this paper we consider a more general multiple tour problem that consists in covering a part of the graph with a set of minimal cost circuits. We define a new global constraint WEIGHTEDSUBCIRCUITS that generalizes the WeightedCircuit constraint by releasing the need to obtain a Hamiltonian circuit. It enforces multiple disjoint circuits of bounded total cost to partially cover a weighted graph, the subsets of vertices to be covered being induced by external constraints. We show that enforcing Bounds Consistency for WeightedSubCircuits is NP-hard. We propose an incomplete but polynomial filtering method based on the search for a lower bound of a weighted Steiner circuit.
暂无评论