Many real life optimization problems contain both hard and soft constraints, as well as qualitative conditional preferences. However, there is no single formalism to specify all three kinds of information. We therefore propose a framework, based on both CP-nets and soft constraints, that handles both hard and soft constraints as well as conditional preferences efficiently and uniformly. We study the complexity of testing the consistency of preference statements, and show how soft constraints can faithfully approximate the semantics of conditional preference statements whilst improving the computational complexity

We identify a new and important global (or non-binary) constraint. This constraint ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. This constraint is useful for a number of different applications including breaking symmetry and fuzzy constraint satisfaction. We propose and implement an efficient linear time algorithm for enforcing generalised arc consistency on such a multiset ordering constraint. Experimental results on several problem domains show considerable promise.

Vincent Aleven Intelligent tutoring systems (ITS) are highly effective in supporting student learning, but are difficult to build. The Cognitive Tutor Authoring Tools (CTAT) project started over 6 years ago with the goals of making it easier for experienced programmers, and possible for non-programmers to create an ITS. CTAT supports tutor building through programming by demonstration, an approach that has been successful in a range of application areas, but that has been applied to only a very limited degree to ITS authoring. Using CTAT, an author creates a tutor by demonstrating correct and incorrect problem solving behaviors, rather than by writing code. The resulting tutors, called exampletracing tutors, evaluate student behavior by flexibly comparing it against the demonstrated problem-solving examples.

In version 2.0, IBM ILOG CP Optimizer has been extended by the introduction of scheduling support based on the concept of optional interval variables. This paper formally describes the new modeling language features available to the users of CP Optimizer for resource-based scheduling. We show that the new language is flexible enough to model problems never before addressed by CP scheduling engines, as well as naturally describing classical scheduling problems found in the literature. This modeling power is based on a small number of general concepts such as intervals, sequences and functions. This makes the modeling language simple, clear and easy to learn, while maintaining the high-level structural aspects of the scheduling model.

Commonsense reasoning, in particular qualitative spatial and temporal reasoning (QSTR), provides flexible and intuitive methods for reasoning about vague and uncertain information including spatial orientation, topology and proximity.  Despite a number of theoretical advances in QSTR, there are relatively few applications that employ these methods.  The central problem is a significant lack of application level standards and validation methods for supporting developers in adapting and integrating QSTR with their domain specific qualitative spatial and temporal models.  To address this we present a significantly novel methodology for QSTR application validation, inspired by research in software engineering.  In this paper we focus on unit testing, and adapt the software engineering strategy of defining boundary cases.  We present two critical boundary concepts, a methodology for isolating the units under testing from other parts of the model, and methods to assist the designer in integrating our critical boundary unit testing approach with a broader validation plan.

Planning problems deal with finding a sequence of actions that transfer the initial state of the world into a desired state. Frequently such problems are solved by dedicated algorithms but there exist planners based on translating the planning problem into a different formalism such as constraint satisfaction or Boolean satisfiability and using a general solver for this formalism. The paper describes how to enhance existing constraint models of planning problems by using techniques such as symmetry breaking (dominance rules), singleton consistency, and lifting.

We introduce a new tractable temporal constraint language, which strictly contains the Ord-Horn language of Buerkert and Nebel and the class of AND/OR precedence constraints. The algorithm we present for this language decides whether a given set of constraints is consistent in time that is quadratic in the input size. We also prove that (unlike Ord-Horn) this language cannot be solved by Datalog or by establishing local consistency.

Symmetries in discrete constraint satisfaction problems have been explored and exploited in the last years, but symmetries in continuous constraint problems have not received the same attention. Here we focus on permutations of the variables consisting of one single cycle. We propose a procedure that takes advantage of these symmetries by interacting with a continuous constraint solver without interfering with it. A key concept in this procedure are the classes of symmetric boxes formed by bisecting a n-dimensional cube at the same point in all dimensions at the same time. We analyze these classes and quantify them as a function of the cube dimensionality. Moreover, we propose a simple algorithm to generate the representatives of all these classes for any number of variables at very high rates. A problem example from the chemical field and the cyclic n-roots problem are used to show the performance of the approach in practice.

In this paper a new dynamic subsumption technique for Boolean CNF formulae is proposed. It exploits simple and sufficient conditions to detect during conflict analysis, clauses from the original formula that can be reduced by subsumption. During the learnt clause derivation, and at each step of the resolution process, we simply check for backward subsumption between the current resolvent and clauses from the original formula and encoded in the implication graph. Our approach give rise to a strong and dynamic simplification technique that exploits learning to eliminate literals from the original clauses. Experimental results show that the integration of our dynamic subsumption approach within the state-of-the-art SAT solvers Minisat and Rsat achieves interesting improvements particularly on crafted instances.

We discuss multi-task online learning when a decision maker has to deal simultaneously with M tasks. The tasks are related, which is modeled by imposing that the M-tuple of actions taken by the decision maker needs to satisfy certain constraints. We give natural examples of such restrictions and then discuss a general class of tractable constraints, for which we introduce computationally efficient ways of selecting actions, essentially by reducing to an on-line shortest path problem. We briefly discuss "tracking" and "bandit" versions of the problem and extend the model in various ways, including non-additive global losses and uncountably infinite sets of tasks.