this paper presents a constraintprogramming approach to solve a specific scheduling problem arising in a company specialized in drug evaluation and pharmacology research. the aim is to build employee timetables cover...
详细信息
In this paper, we introduce a new framework for managing several kinds of renewable resources, including disjunctive resources, cumulative resources, and resources with setup times. In this framework, we use a list sc...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
In this paper, we introduce a new framework for managing several kinds of renewable resources, including disjunctive resources, cumulative resources, and resources with setup times. In this framework, we use a list scheduling approach in which a priority order between activities must be determined to solve resource usage conflicts. In this context, we define a new differentiable constraint-based local search invariant which transforms a priority order into a full schedule and which incrementally maintains this schedule in case of change in the order. On top of that, we use multiple neighborhoods and search strategies, and we get new best upper bounds on several scheduling benchmarks.
Answer set programming (ASP) is a well-established declarative paradigm. One of the successes of ASP is the availability of efficient systems. State-of-the-art systems are based on the ground+solve approach. In some a...
详细信息
Answer set programming (ASP) is a well-established declarative paradigm. One of the successes of ASP is the availability of efficient systems. State-of-the-art systems are based on the ground+solve approach. In some applications, this approach is infeasible because the grounding of one or a few constraints is expensive. In this paper, we systematically compare alternative strategies to avoid the instantiation of problematic constraints, which are based on custom extensions of the solver. Results on real and synthetic benchmarks highlight some strengths and weaknesses of the different strategies.
We propose a new method for solving Valued constraint Satisfaction Problems based both on backtracking techniques-branch and bound- and the notion of tree-decomposition of valued constraint networks. this mixed method...
详细信息
ISBN:
(纸本)3540202021
We propose a new method for solving Valued constraint Satisfaction Problems based both on backtracking techniques-branch and bound- and the notion of tree-decomposition of valued constraint networks. this mixed method aims to benefit from the practical efficiency of enumerative algorithms while providing a warranty of a bounded time complexity. Indeed the time complexity of our method is O(d(w+)+ (1)) with w(+) an approximation of the tree-width of the constraint network and d the maximum size of domains. Such a complexity is obtained by exploiting optimal bounds on the sub-problems defined from the tree-decomposition. these bounds associated to some partial assignments are called "structural valued goods". Recording and exploiting these goods may allow our method to save some time and space with respect to ones required by classical dynamic programming methods. Finally, this method is a natural extension of the BTD algorithm [1] proposed in the classical CSP framework.
LODE is a logic-based web tool for Italian deaf children. It aims at stimulating global reasoning on e-stories written in a verbal language. Presently, we are focusing on temporal reasoning, that is, LODE stimulates c...
详细信息
ISBN:
(纸本)9783540749691
LODE is a logic-based web tool for Italian deaf children. It aims at stimulating global reasoning on e-stories written in a verbal language. Presently, we are focusing on temporal reasoning, that is, LODE stimulates children to reason with global temporal relations between events possibly distant in a story. this is done through apt exercises and withthe support of a constraintprogramming system. Children can also reinvent the e-story by rearranging its events along a new temporal order;it is the task of the constraint system to determine the consistency of the temporally reorganised story and provide children with feedback. To the best of our knowledge, LODE is the first e-learning tool for Italian deaf children that aims at stimulating global reasoning on whole e-stories.
constraint satisfaction has been applied with great success in closed-world scenarios, where all options and constraints are known from the beginning and fixed. Withthe internet, many of the traditional CSP applicati...
详细信息
ISBN:
(纸本)3540202021
constraint satisfaction has been applied with great success in closed-world scenarios, where all options and constraints are known from the beginning and fixed. Withthe internet, many of the traditional CSP applications in resource allocation, scheduling and planning pose themselves in open-world settings, where options and constraints must be gathered from different agents in a network. We define open constraint optimization as a model of such tasks. Under the assumption that options are discovered in decreasing order of preference, it becomes possible to guarantee optimality even when domains and constraints are not completely known. We propose several algorithms for solving open constraint optimization problems by incrementally gathering options through the network. We report empirical results on their performance on random problems, and analyze how to achieve optimality with a minimal number of queries to the information sources.
We introduce a constraint system LC that handles arithmetic constraints over reals within the linear concurrent constraintprogramming (Icc) framework. this approach provides us with a general, extensible foundation f...
详细信息
ISBN:
(纸本)3540652248
We introduce a constraint system LC that handles arithmetic constraints over reals within the linear concurrent constraintprogramming (Icc) framework. this approach provides us with a general, extensible foundation for linear programming algorithm design that comes with a (linear) logical semantics. In particular, it allows us to build a 'glass-box' version of the (constraint solver) simplex algorithm by defining (monotone) cc ask and tell agents over a higher-level constraint system as Icc(LC) programs. We illustrate at the same time the use of the lccframework as a non-trivial concurrent algorithm specification tool.
We study from a formal perspective the consistency and propagation of constraints involving multiset variables. that is, variables whose values are multisets. these help us model problems more naturally and can, for e...
详细信息
ISBN:
(纸本)3540202021
We study from a formal perspective the consistency and propagation of constraints involving multiset variables. that is, variables whose values are multisets. these help us model problems more naturally and can, for example, prevent introducing unnecessary symmetry into a model. We identify a number of different representations for multiset variables and compare them. We then propose a definition of local consistency for constraints involving multiset, set and integer variables. this definition is a generalization of the notion of bounds consistency for integer variables. We show how this local consistency property can be enforced by means of some simple inference rules which tighten bounds on the variables. We also study a number of global constraints on set and multiset variables. Surprisingly, unlike finite domain variables, the decomposition of global constraints over set or multiset variables often does not hinder constraint propagation.
the generalization of the constraint satisfaction problem with universal quantifiers is a challenging PSPACE-complete problem, which is interesting theoretically and also relevant to solving other PSPACE problems aris...
详细信息
ISBN:
(纸本)3540292381
the generalization of the constraint satisfaction problem with universal quantifiers is a challenging PSPACE-complete problem, which is interesting theoretically and also relevant to solving other PSPACE problems arising in AI, such as reasoning with uncertainty, and multiplayer games. I define two new levels of consistency for QCSP, and give an algorithm to enforce consistency for one of these definitions. the algorithm is embedded in backtracking search, and tested empirically. the aims of this work are to increase the facilities available for modelling and to increase the power of constraint propagation for QCSPs. the work is motivated by examples from adversarial games.
暂无评论