the proceedings contain 62 papers. the topics discussed include: constraint-based schedulers, do they really work?;challenges for constraint reasoning and optimization in computational sustainability;observations on s...
ISBN:
(纸本)3642042430
the proceedings contain 62 papers. the topics discussed include: constraint-based schedulers, do they really work?;challenges for constraint reasoning and optimization in computational sustainability;observations on symmetry breaking;generating optimal stowage plans for container vessel bays;real-time Tabu search for video tracking association;pin assignment using stochastic local search constraintprogramming;modelling equidistant frequency permutation arrays: an application of constraints to mathematics;scheduling the CB1000 nanoproteomic analysis system with Python, Tailor, and Minion;solving nurse rostering problems using soft global constraints;online selection of quorum systems for RAMBO reconfiguration;a hybrid constraint model for the routing and wavelength assignment problem;memorisation for constraint-based local search;on the structure of industrial SAT instances;a gender-based genetic algorithm for the automatic configuration of algorithms;and filtering numerical CSPs using well-constrained subsystems.
Max Restricted Path Consistency (maxRPC) is a local consistency for binary constraints that can achieve considerably stronger pruning than arc consistency. However, existing maxRPC algorithms suffer from overheads and...
详细信息
ISBN:
(纸本)9783642153952
Max Restricted Path Consistency (maxRPC) is a local consistency for binary constraints that can achieve considerably stronger pruning than arc consistency. However, existing maxRPC algorithms suffer from overheads and redundancies as they can repeatedly perform many constraint checks without triggering any value deletions. In this paper we propose techniques that can boost the performance of maxRPC algorithms. these include the combined use of two data structures to avoid many redundant constraint checks, and heuristics for the efficient ordering and execution of certain operations. Based on these, we propose two closely related maxRPC algorithms. the first one has optimal O(end(3)) time complexity, displays good performance when used stand-alone, but is expensive to apply during search. the second one has O(en(2)d(4)) time complexity, but a restricted version with O(ertd(4)) complexity can be very efficient when used during search. Both algorithms have O(ed) space complexity when used stand-alone. However, the first algorithm has O(end) space complexity when used during search, while the second retains the O(ed) complexity. Experimental results demonstrate that the resulting methods constantly outperform previous algorithms for maxRPC, often by large margins, and constitute a more than viable alternative to arc consistency.
the constraint Simplification Rules (CSR) subset of CHR and the flat subset of LCC, where agent nesting is restricted, are very close syntactically and semantically. the first contribution of this paper is to provide ...
详细信息
When numerical CSPs are used to solve systems of n equations with n variables, the preconditioned interval Newton operator plays two key roles: First it allows handling the n equations as a global constraint, hence ac...
详细信息
ISBN:
(纸本)3540859578
When numerical CSPs are used to solve systems of n equations with n variables, the preconditioned interval Newton operator plays two key roles: First it allows handling the n equations as a global constraint, hence achieving a powerful contraction. Second it can prove rigorously the existence of solutions. However, none of these advantages can be used for under-constrained systems of equations, which have manifolds of solutions. A new framework is proposed in this paper to extend the advantages of the preconditioned interval Newton to under-constrained systems of equations. this is achieved simply by allowing domains of the NCSP to be parallelepipeds, which generalize the boxes usually used as domains.
A recurring problem in data centres is that the constantly changing workload is not proportionally distributed over the available servers. Some resources may lay idle while others are pushed to the limits of their cap...
详细信息
ISBN:
(纸本)9783642153952
A recurring problem in data centres is that the constantly changing workload is not proportionally distributed over the available servers. Some resources may lay idle while others are pushed to the limits of their capacity. Tins in turn leads to decreased response times on the overloaded servers, a situation that the data centre provider wants to prevent. To solve this problem, an administrator may move (reallocate) applications or even entire virtual servers around in order to spread the load. Since there is a cost associated with moving applications (in the form of down time during the move, for example), we are interested in solutions with minimal changes. this paper describes a hybrid approach to solving such resource reallocation problems in data centres, where two technologies have to work closely together to solve this problem in an efficient manner. the first technology is a Business Rules Management System (BRMS), which is used to identify which systems are considered to be overloaded on a systematic basis. Data centres use complex rules to track the behaviour of the servers over time, in order to properly identify overloads. Representing these tracking conditions is what the BRMS is good for. It defines the relationships (business constraints) over time between different applications, processes and required resources that are specific to the data centre. As such, it also allows a high degree of customisation. Having identified which servers require reallocation of their processes, the BRMS then automatically creates an optimisation model solved with a constraintprogramming (CP) approach. A CP solver finds a feasible or the optimal solution to this CSP, which is used to provide recommendations on which workload should be moved and whereto. Notice that our use of a hybrid approach is a requirement, not a feature: employing only rules we would not be able to compute an optimal solution;using only CP we would not be able to specify the complex identification
this paper studies how to verify the conformity of a program with its specification and proposes a novel constraint-programming framework for bounded program verification (CPBPV). the CPBPV framework uses constraint s...
详细信息
ISBN:
(纸本)3540859578
this paper studies how to verify the conformity of a program with its specification and proposes a novel constraint-programming framework for bounded program verification (CPBPV). the CPBPV framework uses constraint stores to represent boththe specification and the program and explores execution paths of bounded length nondeterministically. the CPBPV framework detects non-conformities and provides counter examples when a path of bounded lengththat refutes some properties exists. the input program is partially correct under the boundness restrictions, if each constraint store so produced implies the post-condition. CPBPV does not explore spurious execution paths, as it incrementally prunes execution paths early by detecting that the constraint store is not consistent. CPBPV uses the rich language of constraintprogramming to express the constraint store. Finally, CPBPV is parameterized with a list of solvers which are tried in sequence, starting withthe least expensive and less general. Experimental results often produce orders of magnitude improvements over earlier approaches, running times being often independent of the size of the variable domains. Moreover, CPBPV was able to detect subtle errors in some programs for which other frameworks based on bounded model checking have failed.
the proceedings contain 23 papers. the topics discussed include: graph queries through datalog optimizations;precise complexity analysis for efficient datalog queries;semantics-preserving translations between linear c...
ISBN:
(纸本)9781450301329
the proceedings contain 23 papers. the topics discussed include: graph queries through datalog optimizations;precise complexity analysis for efficient datalog queries;semantics-preserving translations between linear concurrent constraintprogramming and constraint handling rules;a declarative approach to robust weighted max-sat;equational axiomatization of call-by-name delimited control;functional derivation of a virtual machine for delimited continuations;HSS: a compiler for cascading style sheets;declarative modeling of finite mathematics;generic record combinators with static type checking;two notions of sub-behavior for session-based client/server systems;relating nominal and higher-order abstract syntax specifications;declarative workflows to efficiently manage flexible and advanced business processes;and typed and unambiguous pattern matching on strings using regular expressions.
the constraint Satisfaction Problem (CSP) framework allows users to define problems in a declarative way, quite independently from the solving process. However, when the problem is over-constrained, the answer "n...
详细信息
ISBN:
(纸本)3540859578
the constraint Satisfaction Problem (CSP) framework allows users to define problems in a declarative way, quite independently from the solving process. However, when the problem is over-constrained, the answer "no solution" is generally unsatisfactory. A Max-CSP P-m = < V, D, C > is a triple defining a constraint problem whose solutions maximize the number of satisfied constraints. In this paper, we focus on numerical CSPs, which are defined on real variables represented as floating point intervals and which constraints are numerical relations defined in intension. Solving such a problem (i.e., exactly characterizing its solution set) is generally undecidable and thus consists in providing approximations. We propose a Branch and Bound algorithm that provides under and over approximations of a solution set that maximize the maximum number m(P) of satisfied constraints. the technique is applied on three numeric applications and provides promising results.
A table constraint is explicitly represented as its set of solutions or non-solutions. this ad hoc (or extensional) representation may require space exponential to the arity of the constraint, making enforcing GAC exp...
详细信息
A table constraint is explicitly represented as its set of solutions or non-solutions. this ad hoc (or extensional) representation may require space exponential to the arity of the constraint, making enforcing GAC expensive. In this paper, we address the space and time inefficiencies simultaneously by presenting the mddc constraint. mddc is a global constraintthat represents its (non-)solutions with a multi-valued decision diagram (MDD). the MDD-based representation has the advantage that it can be exponentially smaller than a table. the associated GAC algorithm (called mddc) has time complexity linear to the size of the MDD, and achieves full incrementality in constant time. In addition, we show how to convert a positive or negative table constraint into an mddc constraint in time linear to the size of the table. Our experiments on structured problems, car sequencing and still-life, show that mddc is also a fast GAC algorithm for some global constraints such as sequence and regular. We also show that mddc is faster than the state-of-the-art generic GAC algorithms in Gent et al. (2007), Lecoutre and Szymanek (2006), Lhomme and R,gin (2005) for table constraint.
A table constraint is explicitly represented as its set of solutions or non-solutions. this ad hoc (or extensional) representation may require space exponential to the arity of the constraint, making enforcing GAC exp...
详细信息
A table constraint is explicitly represented as its set of solutions or non-solutions. this ad hoc (or extensional) representation may require space exponential to the arity of the constraint, making enforcing GAC expensive. In this paper, we address the space and time inefficiencies simultaneously by presenting the mddc constraint. mddc is a global constraintthat represents its (non-)solutions with a multi-valued decision diagram (MDD). the MDD-based representation has the advantage that it can be exponentially smaller than a table. the associated GAC algorithm (called mddc) has time complexity linear to the size of the MDD, and achieves full incrementality in constant time. In addition, we show how to convert a positive or negative table constraint into an mddc constraint in time linear to the size of the table. Our experiments on structured problems, car sequencing and still-life, show that mddc is also a fast GAC algorithm for some global constraints such as sequence and regular. We also show that mddc is faster than the state-of-the-art generic GAC algorithms in Gent et al. (2007), Lecoutre and Szymanek (2006), Lhomme and R,gin (2005) for table constraint.
暂无评论