We introduce the SomeDifferent constraint as a generalization of AllDifferent. SomeDifferent requires that values assigned to some pairs of variables will be different. It has many practical applications. For example,...
详细信息
ISBN:
(纸本)3540462678
We introduce the SomeDifferent constraint as a generalization of AllDifferent. SomeDifferent requires that values assigned to some pairs of variables will be different. It has many practical applications. For example, in workforce management, it may enforce the requirement that the same worker is not assigned to two jobs which are overlapping in time. Propagation of the constraint for hyper-arc consistency is NP hard. We present a propagation algorithm with worst case time complexity O(n(3)ss(n)) where n is the number of variables and ss approximate to 3.5 (ignoring a trivial dependence on the representation of the domains). We also elaborate on several heuristics which greatly reduce the algorithm's running time in practice. We provide experimental results, obtained on a real-world workforce management problem and on synthetic data, which demonstrate the feasibility of our approach.
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.
the SEQUENCE constraint is useful in modelling car sequencing, rostering, scheduling and related problems. We introduce half a dozen new encodings of the SEQUENCE constraint, some of which do not hinder propagation. W...
详细信息
ISBN:
(纸本)9783540749691
the SEQUENCE constraint is useful in modelling car sequencing, rostering, scheduling and related problems. We introduce half a dozen new encodings of the SEQUENCE constraint, some of which do not hinder propagation. We prove that, down a branch of a search tree, domain consistency can be enforced on the SEQUENCE constraint in just O(n(2) log n) time. this improves upon the previous bound of O(n(3)) for each call down the tree. We also consider a generalization of the SEQUENCE constraint - the Multiple SEQUENCE constraint. Our experiments suggest that, on very large and tight problems, domain consistency algorithms are best. However, on smaller or looser problems, much simpler encodings are better, even though these encodings hinder propagation. When there are multiple SEQUENCE constraints, a more expensive propagator shows promise.
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.
the Boolean constraint Propagation (BCP) is a well-known helpful technique implemented in most state-of-the-art efficient satisfiability solvers. We propose in this paper a new use of the BCP to deduce sub-clauses fro...
详细信息
ISBN:
(纸本)3540292381
the Boolean constraint Propagation (BCP) is a well-known helpful technique implemented in most state-of-the-art efficient satisfiability solvers. We propose in this paper a new use of the BCP to deduce sub-clauses from the associated implication graph. Our aim is to reduce the length of clauses thanks to the subsumption rule. We show how such extension can be grafted to modem SAT solvers and we provide some experimental results of the sub-clauses deduction as a pretreatment process.
Several combinatorial problems, such as car sequencing and rostering, feature sequence constraints, restricting the number of occurrences of certain values in every subsequence of a given length. We present three new ...
详细信息
Several combinatorial problems, such as car sequencing and rostering, feature sequence constraints, restricting the number of occurrences of certain values in every subsequence of a given length. We present three new filtering algorithms for the sequence constraint, including the first that establishes domain consistency in polynomial time. the filtering algorithms have complementary strengths: One borrows ideas from dynamic programming;another reformulates it as a regular constraint;the last is customized. the last two algorithms establish domain consistency, and the customized one does so in polynomial time. We provide experimental results that demonstrate the practical usefulness of each. We also show that the customized algorithm applies naturally to a generalized version of the sequence constraintthat allows subsequences of varied lengths. the significant computational advantage of using a single generalized sequence constraint over a semantically equivalent collection of among or sequence constraints is demonstrated empirically.
Various encodings have been proposed to convert constraint Satisfaction Problems (CSP) into Boolean Satisfiability problems (SAT). Some of them use a logical variable for each element in each domain: among these very ...
详细信息
ISBN:
(纸本)9783540749691
Various encodings have been proposed to convert constraint Satisfaction Problems (CSP) into Boolean Satisfiability problems (SAT). Some of them use a logical variable for each element in each domain: among these very successful are the direct and the support encodings. Other methods, such as the log-encoding, use a logarithmic number of logical variables to encode domains. However, they lack the propagation power of the direct and support encodings, so many SAT solvers perform poorly on log-encoded CSPs. In this paper, we propose a new encoding, called log-support, that combines the log and support encodings. It has a logarithmic number of variables, and uses support clauses to improve propagation. We also extend the encoding using a Gray code. We provide experimental results on Job-Shop scheduling and randomly-generated problems.
constraint satisfaction and propositional satisfiability problems are often solved using backtracking search. Previous studies have shown that a technique called randomization and restarts can dramatically improve, th...
详细信息
ISBN:
(纸本)9783540749691
constraint satisfaction and propositional satisfiability problems are often solved using backtracking search. Previous studies have shown that a technique called randomization and restarts can dramatically improve, the performance of a, backtracking algorithm on some instances. We consider the commonly occurring scenario where one is to solve an ensemble of instances using a backtracking algorithm and wish to learn a good restart strategy for the ensemble. In contrast to much previous work, our focus is on universal strategies. We contribute to the theoretical understanding of universal strategies and demonstrate both analytically and empirically the pitfalls of non-universal strategies. We also propose a simple approach for learning good universal restart strategies and demonstrate the effectiveness and robustness of our approach through an extensive empirical evaluation on a real-world testbed.
We propose two new asynchronous algorithms for solving Distributed constraint Satisfaction Problems (DisCSPs). the first algorithm, AFC-ng, is a nogood-based version of Asynchronous Forward Checking (AFC). the second ...
详细信息
ISBN:
(纸本)9783642042430
We propose two new asynchronous algorithms for solving Distributed constraint Satisfaction Problems (DisCSPs). the first algorithm, AFC-ng, is a nogood-based version of Asynchronous Forward Checking (AFC). the second algorithm, Asynchronous Inter-Level Forward-Checking (AILFC), is based oil the AFC-ng algorithm and is performed oil a pseudo-tree ordering of the constraint graph. AFC-ng and AILFC only need polynomial space. We compare the performance of these algorithms with other DisCSP algorithms on random DisCSPs in two kinds of communication environments: Fast communication and slow communication. Our experiment,, show that AFC-ng improves oil AFC and that AILFC Outperforms all compared algorithms in communication load.
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.
暂无评论