the proceedings contain 61 papers. the special focus in this conference is on principles and practice of constraintprogramming. the topics include: Neuron constraints to model complex real-world problems;A constraint...
ISBN:
(纸本)9783642237850
the proceedings contain 61 papers. the special focus in this conference is on principles and practice of constraintprogramming. the topics include: Neuron constraints to model complex real-world problems;A constraint based approach to cyclic RcpSP;an efficient light solver for querying the semantic web;on guaranteeing polynomially bounded search tree size;a framework for decision-based consistencies;Hierarchically nested convex VCSP;tractable triangles;on minimal weighted clones;Solving MAXSAT by solving a sequence of simpler SAT instances;operations research and constraintprogramming at google;filtering algorithms for discrete cumulative problems with overloads of resource;Synthesis of search algorithms from high-level cp models;revisiting the tree constraint;half reification and flattening;the parameterized complexity of local consistency;symmetry breaking in numeric constraint problems;on minimal constraint networks;structural tractability of constraint optimization;models and strategies for variants of the job shop scheduling problem;MaxRPC algorithms based on bitwise operations;Solving problems withcp: Four common pitfalls to avoid;Grid-based SAT solving with iterative partitioning and clause learning;large neighborhood search for dial-a-ride problems;On deciding MUS membership with QBF;On the relative efficiency of DPLL and OBDDs with axiom and join;Min CSP on four elements: Moving beyond submodularity;algorithm selection and scheduling;incorporating variance in impact-based search;a quadratic edge-finding filtering algorithm for cumulative resource constraints;A CSP solver focusing on FAC variables;constraint reasoning and kernel clustering for pattern decomposition with scaling;a constraint seeker: Finding and ranking global constraints from examples;solving qualitative constraints involving landmarks;search combinators.
the proceedings contain 59 papers. the topics discussed include: orchestrating satisfiability engines;operations research and constraintprogramming at Google;a constraint seeker: finding and ranking global constraint...
ISBN:
(纸本)9783642237850
the proceedings contain 59 papers. the topics discussed include: orchestrating satisfiability engines;operations research and constraintprogramming at Google;a constraint seeker: finding and ranking global constraints from examples;bin repacking scheduling in virtualized datacenters;optimal carpet cutting;a hybrid approach for solving real-world nurse rostering problems;constraintprogramming for controller synthesis;neuron constraints to model complex real-world problems;an efficient light solver for querying the semantic web;on guaranteeing polynomially bounded search tree size;a framework for decision-based consistencies;tractable triangles;on minimal weighted clones;filtering algorithms for discrete cumulative problems with overloads of resource;revisiting the tree constraint;half reification and flattening;the parameterized complexity of local consistency;and symmetry breaking in numeric constraint problems.
constraintprogramming is a family of techniques for solving combinatorial problems, where the problem is modelled as a set of decision variables (typically with finite domains) and a set of constraints that express r...
详细信息
constraintprogramming is a family of techniques for solving combinatorial problems, where the problem is modelled as a set of decision variables (typically with finite domains) and a set of constraints that express relations among the decision variables. One key concept in constraintprogramming is propagation: reasoning on a constraint or set of constraints to derive new facts, typically to remove values from the domains of decision variables. Specialized propagation algorithms (propagators) exist for many classes of constraints. the concept of support is pervasive in the design of propagators. Traditionally, when a domain value ceases to have support, it may be removed because it takes part in no solutions. Arc-consistency algorithms such as AC2001 [in: Proceedings 17thinternational Joint conference on Artificial Intelligence (IJCAI 2001), 2001, pp. 309-315] make use of support in the form of a single domain value. GAC algorithms such as GAC-Schema [in: Proceedings 15thinternational Joint conference on Artificial Intelligence (IJCAI 97), 1997, pp. 398-404] use a tuple of values to support each literal. We generalize these notions of support in two ways. First, we allow a set of tuples to act as support. Second, the supported object is generalized from a set of literals (GAC-Schema) to an entire constraint or any part of it. We design a methodology for developing correct propagators using generalized support. A constraint is expressed as a family of support properties, which may be proven correct against the formal semantics of the constraint. We show how to derive correct propagators from the constructive proofs of the support properties. the framework is carefully designed to allow efficient algorithms to be produced. Derived algorithms may make use of dynamic literal triggers or watched literals [in: Proc. 12thinternationalconference on the principles and practice of constraintprogramming (cp 2006), 2006, pp. 182-197] for efficiency. Finally, three case st
the connection between constraint languages and clone theory has been a fruitful line of research on the complexity of constraint satisfaction problems. In a recent result, Cohen et al. [SIAM J. Comput., 42 (2013), pp...
详细信息
the connection between constraint languages and clone theory has been a fruitful line of research on the complexity of constraint satisfaction problems. In a recent result, Cohen et al. [SIAM J. Comput., 42 (2013), pp. 915-1939] have characterized a Galois connection between valued constraint languages and so-called weighted clones. In this paper, we study the structure of weighted clones. We extend the results of Creed and. Zivny from [Proceedings of the 17th international conference on principles and practice of constraint programming, 2011, pp. 210-224] on types of weightings necessarily contained in every nontrivial weighted clone. this result has immediate computational complexity consequences as it provides necessary conditions for tractability of weighted clones and thus valued constraint languages. We demonstrate that some of the necessary conditions are also sufficient for tractability, while others are provably not.
We introduce new cp models for the many-to-many stable matching problem. We use the notion of rotation to give a novel encoding that is linear in the input size of the problem. We give extra filtering rules to maintai...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
We introduce new cp models for the many-to-many stable matching problem. We use the notion of rotation to give a novel encoding that is linear in the input size of the problem. We give extra filtering rules to maintain arc consistency in quadratic time. Our experimental study on hard instances of sex-equal and balanced stable matching shows the efficiency of one of our propositions as compared withthe state-of-the-art constraintprogramming approach.
this book constitutes the refereed proceedings of the 17th international conference on principles and practice of constraint programming, cp 2011, held in Perugia, Italy, September 12-16, 2011. the 51 revised full pap...
详细信息
ISBN:
(数字)9783642237867
ISBN:
(纸本)9783642237850
this book constitutes the refereed proceedings of the 17th international conference on principles and practice of constraint programming, cp 2011, held in Perugia, Italy, September 12-16, 2011.
the 51 revised full papers and 7 short papers presented together withthree invited talks were carefully reviewed and selected from 159 submissions. the papers are organized in topical sections on algorithms, environments, languages, models and systems, applications such as decision making, resource allocation and agreement technologies.
Domains in Continuous constraintprogramming (cp) are generally represented with intervals whose n-ary Cartesian product (box) approximates the solution space. this paper proposes a new representation for continuous v...
详细信息
the Operations Research and Optimization team at Google develops both general purpose optimization tools and solutions for internal optimization problems. We will describe the tools – most of which are available at h...
详细信息
Given a sequence of variables X = 〈x 0, x 1, …, xn − 1 〉, we consider the IncreasingSum constraint, which imposes ∀ i ∈ [0, n − 2] xi ≤ xi + 1, and Σxi∈X xi = S. We propose an Θ(n) bound-consistency algorit...
详细信息
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 wi...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
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.
暂无评论