Catálogo de publicaciones - libros

Time granularity constraint reasoning is likely to have a relevant role in emerging applications like GIS, time management in the Web and Personal Information Management applications for mobile systems. This paper reports recent advances in the development of a system for solving temporal constraint satisfaction problems where distance constraints are specified in terms of arbitrary time granularities.

Finding equilibria is a hard computational problem which is central to game theory and whose applications range from decision-making to the analysis of multi-agent systems. Despite considerable recent interest and significant recent improvements, the problem remains essentially open in the case of -person games. We investigate the use of interval-based constraint solving techniques to compute equilibria. We report on experiments made using several encodings of randomly-generated games into continuous CSP, and draw conclusions regarding both the scalability of interval methods for game-theoretic applications and the impact of the symbolic representation of polynomials and of the choice of the propagation technique on the speed of resolution.

Covering arrays have been studied for their applications to drug screening and software and hardware testing. In this paper, we model the problem as a constraint program. Our proposed models exploit non-binary (global) constraints, redundant modelling, channelling constraints, and symmetry breaking constraints. Our initial experiments show that with our best integrated model, we are able to either prove optimality of existing bounds or find new optimal values for arrays of moderate size. Local search on a SAT-encoding of the model is able to find improved bounds on larger problems.

Super solutions provide a framework for finding robust solutions to Constraint Satisfaction Problems [5,3]. We present a novel application of super solutions to combinatorial auctions in which a bid may be disqualified or withdrawn after the winners are announced. We examine the effectiveness of super solutions in different auction scenarios that simulate economically motivated bidding patterns. We also analyze the drawbacks of this approach and motivate an extension to the framework that permits a more flexible and realistic approach for determining robust solutions.

Overload checking, forbidden regions, edge finding, and not-first/not-last detection are well-known propagation rules to prune the start times of activities which have to be processed without any interruption and overlapping on an exclusively available resource, i.e. machine. These rules are extendible by two other rules which take the number of activities into account which are at most executable after or before another activity. To our knowledge, these rules are based on approximations of the (minimal) earliest completion times and the (maximal) latest start times of sets of activities. In this paper, the precise definitions of these time values as well as an efficient procedure for their calculations are given. Based on the resulting time values the rules are re-formulated and applied to a well-known job shop scheduling benchmark.