Collaborating Authors

A Markovian Model for Dynamic and Constrained Resource Allocation Problems

AAAI Conferences

An autonomous agent, allocating stochastic resources to incoming tasks, faces increasingly complex situations when formulating its control policy. These situations are often constrained by limited resources of the agent, time limits, physical constraints or other agents. All these reasons explain why complexity and state space dimension increase exponentially in size of considered problem. Unfortunately, models that already exist either consider the sequential aspect of the environment, or its stochastic one or its constrained one. To the best of our knowledge, there is no model that take into account all these three aspects. For example, dynamic constraint satisfaction problems (DCSP) have been introduced by Dechter & Dechter (1988) to address dynamic and constrained problems. However, in DCSPs, there is typically no transition model, and thus no concept of sequence of controls. On the other hand, Fargier, Lang, & Schiex (1996) proposed mixed CSPs (MC-SPs), but this approach considers only the stochastic and the constrained aspects of the problem.

Constraints and preferences The interplay of preferences and algorithms

AAAI Conferences

As logic, constraint satisfaction faces the problem of inconsistency which itself naturally leads to the need of expressing preferences. Starting from (Rosenfeld, Hummel, & Zucker 1976), which defined fuzzy constraint networks, a variety of extended constraint frameworks have been proposed. Since 1995, several general axiomatic frameworks that try to cover all these proposals have been introduced. In this paper, we show how algorithms and axioms interacts on a specific class of algorithms: arc consistency enforcing algorithms. The generalization of arc consistency to the Valued CSP framework was recently made possible thanks to the addition of an additional axiom that captures the existence of difference between preferences.


AAAI Conferences

MINLP problems are hard constrained optimization problems, with nonlinear constraints and mixed discrete continuous variables. They can be solved using a Branch-and-Bound scheme combining several methods, such as linear programming, interval analysis, and cutting methods. Our goal is to integrate constraint programming techniques in this framework. Firstly, global constraints can be introduced to reformulate MINLP problems thus leading to clean models and more precise computations. Secondly, interval-based approximation techniques for nonlinear constraints can be improved by taking into account the integrality of variables early. These methods have been implemented in an interval solver and we present experimental results from a set of MINLP instances.


AAAI Conferences

If the Constraint Satisfaction framework has been extended to deal with Constraint Optimization problems, it appears that optimization is far more complex than satisfaction. One of the causes of the inefficiency of complete tree search methods, like Depth First Branch and Bound, lies in the poor quality of the lower bound on the global valuation of a partial assignment, even when using Forward Checking techniques. In this paper, we introduce the Russian Doll Search algorithm which replaces one search by n successive searches on nested subproblems (n being the number of problem variables), records the results of each search and uses them later, when solving larger subproblems, in order to improve the lower bound on the global valuation of any partial assignment. On small random problems and on large real scheduling problems, this algorithm yields surprisingly good results, which greatly improve as the problems get more constrained and the bandwidth of the used variable ordering diminishes. The Constraint Satisfaction framework (CSP) is now widely used to represent and solve numerous Artificial Intelligence problems (planning, scheduling, diagnosis, design...).

Embarrassingly Parallel Search in Constraint Programming

Journal of Artificial Intelligence Research

We introduce an Embarrassingly Parallel Search (EPS) method for solving constraint problems in parallel, and we show that this method matches or even outperforms state-of-the-art algorithms on a number of problems using various computing infrastructures. EPS is a simple method in which a master decomposes the problem into many disjoint subproblems which are then solved independently by workers. Our approach has three advantages: it is an efficient method; it involves almost no communication or synchronization between workers; and its implementation is made easy because the master and the workers rely on an underlying constraint solver, but does not require to modify it. This paper describes the method, and its applications to various constraint problems (satisfaction, enumeration, optimization). We show that our method can be adapted to different underlying solvers (Gecode, Choco2, OR-tools) on different computing infrastructures (multi-core, data centers, cloud computing).