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.
In this paper, we consider a multi-robot deployment problem involving a set of robots which must realize observation tasks at different locations and navigate through a shared network of waypoints. To solve this probl...
详细信息
ISBN:
(纸本)9783030300487
In this paper, we consider a multi-robot deployment problem involving a set of robots which must realize observation tasks at different locations and navigate through a shared network of waypoints. To solve this problem, we develop a two-level approach which alternates between (a) quickly obtaining high-level schedules based on a coarse grain cp model which approximates navigation tasks as setup times between observations, and (b) generating more accurate schedules based on a fine grain cp model which takes into account all resource usage conflicts during traversals of the shared network. the low-level layer also contains an explanation module able to generate constraints holding on high-level decision variables. these constraints (or cuts) account for interferences found in the low-level solutions and which the high-level scheduler should take into account to minimize the makespan. the proposed variants of the cut generation strategy are incomplete, the aim being to obtain good quality solutions in a short time, and they differ in the way they allow to diversify search. Experiments show the efficiency of this approach and the complementarity of the cut generation schemes proposed.
Cost based filtering is a novel approach that combines techniques from Operations Research and constraintprogramming to filter from decision variable domains values that, do not lead to better solutions [7]. Stochast...
详细信息
ISBN:
(纸本)9783540859574
Cost based filtering is a novel approach that combines techniques from Operations Research and constraintprogramming to filter from decision variable domains values that, do not lead to better solutions [7]. Stochastic: constraintprogramming is a. framework for modeling combinatorial optimization problems that, involve uncertainty [19]. In this work;we show how to perform cost;based filtering for certain classes of stochastic constraint, programs. Our approach is based oil a set of known inequalities borrowed from Stochastic programming - a branch of OR. concerned with modeling and solving problems involving. uncertainty. We discuss bound generation and cost-based domain filtering procedures for a well-known problem in the Stochastic. programming literature, the static stochastic knapsack problem. We also apply our technique to a stochastic sequencing problem. Our results clearly show the value of the proposed approach over;I pure scenario-based Stochastic constraintprogramming formulation both in terms of explored nodes and run times.
the stretch constraint occurs in many rostering problems that arise in the industrial and public service sectors. In this paper we present an efficient algorithm for domain consistency propagation of the stretch const...
详细信息
ISBN:
(纸本)3540232419
the stretch constraint occurs in many rostering problems that arise in the industrial and public service sectors. In this paper we present an efficient algorithm for domain consistency propagation of the stretch constraint. Using benchmark and random instances, we show that this stronger consistency sometimes enables our propagator to solve more difficult problems than a previously proposed propagation algorithm for the stretch constraint. We also discuss variations of the stretch constraintthat seem simple and useful, but turn out to be intractable to fully propagate.
In interactive decision-making settings, such as product configuration, users are stating preferences, or foreground constraints, over a set of possible solutions, as defined by background constraints. When the foregr...
详细信息
ISBN:
(纸本)9783642042430
In interactive decision-making settings, such as product configuration, users are stating preferences, or foreground constraints, over a set of possible solutions, as defined by background constraints. When the foreground constraints introduce inconsistencies withthe background constraints, we wish to find explanations that help the user converge to a solution. In order to provide satisfactory explanations, it call be useful to know one or several subsets of conflicting constraints;Such a subset is called a conflict. When computing such conflicts is intractable in an interactive context, we call choose to compile the problem so as to allow faster response times. In this paper we propose a new representation, which implicitly encompasses all conflicts possibly introduced by a user's choices. We claim that it call help in Situations where extra information about conflicts is needed, such as when explanations of inconsistency are required.
Packing 2D objects in a limited space is an ubiquitous problem with many academic and industrial variants. In any case, solving this problem requires the ability to determine where a first object can be placed so that...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Packing 2D objects in a limited space is an ubiquitous problem with many academic and industrial variants. In any case, solving this problem requires the ability to determine where a first object can be placed so that it does not intersect a second, previously placed, object. this subproblem is called the non-overlapping constraint. the complexity of this non-overlapping constraint depends on the type of objects considered. It is simple in the case of rectangles. It has also been studied in the case of polygons. this paper proposes a numerical approach for the wide class of objects described by non-linear inequalities. Our goal here is to calculate the non-overlapping constraint, that is, to describe the set of all positions and orientations that can be assigned to the first object so that intersection withthe second one is empty. this is done using a dedicated branch & prune approach. We first show that the non-overlapping constraint can be cast into a Minkowski sum, even if we take into account orientation. We derive from this an inner contractor, that is, an operator that removes from the current domain a subset of positions and orientations that necessarily violate the non-overlapping constraint. this inner contractor is then embedded in a sweeping loop, a pruning technique that was only used with discrete domains so far. We finally come up with a branch & prune algorithm that outperforms Rsolver, a generic state-of-the-art solver for continuous quantified constraints.
this paper introduces a geometrical constraint kernel for handling the location in space and time of polymorphic kappa-dimensional objects subject to various geometrical and time constraints. the constraint kernel is ...
详细信息
ISBN:
(纸本)9783540749691
this paper introduces a geometrical constraint kernel for handling the location in space and time of polymorphic kappa-dimensional objects subject to various geometrical and time constraints. the constraint kernel is generic in the sense that one of its parameters is a set of constraints on subsets of the objects. these constraints are handled globally by the kernel. We first illustrate how to model several placement problems withthe constraint kernel. We then explain how new constraints can be introduced and plugged into the kernel. Based on these interfaces, we develop a generic k-dimensional lexicographic sweep algorithm for filtering the attributes of an object (i.e., its shape and the coordinates of its origin as well as its start, duration and end in time) according to all constraints where the object occurs. Experiments involving up to hundreds of thousands of objects and 1 million integer variables are provided in 2, 3 and 4 dimensions, both for simple shapes (i.e., rectangles, parallelepipeds) and for more complex shapes.
We define Realtime Online solving of Quantified constraint Satisfaction Problems (QCSPs) as a, model for realtime online CSP solving. We use a combination of propagation, lookahead and heuristics and show how all thre...
详细信息
ISBN:
(纸本)9783642042430
We define Realtime Online solving of Quantified constraint Satisfaction Problems (QCSPs) as a, model for realtime online CSP solving. We use a combination of propagation, lookahead and heuristics and show how all three improve performance. For adversarial opponents we show that we can achieve promising results through good lookahead and heuristics and that a version of alpha beta pruning performs strongly. For random opponents, we show that we can frequently achieve solutions even on problems which lack a winning strategy and that. we can improve our success rate by using Existential Quantified Generalised Arc Consistency;a, lower level of consistency than SQGAC, to maximise pruning without removing solutions. We also consider the power of the universal opponent and show that through good heuristic selection we can generate a significantly stronger player than a static heuristic provides.
暂无评论