Arnaud Lallouet

AAAI Conference 2023 Conference Paper

Generalized Confidence Constraints

• Guillaume Perez
• Steve Malalel
• Gael Glorian
• Victor Jung
• Alexandre Papadopoulos
• Marie Pelleau
• Wijnand Suijlen
• Jean-Charles Régin

In robust optimization, finding a solution that solely respects the constraints is not enough. Usually, the uncertainty and unknown parameters of the model are represented by random variables. In such conditions, a good solution is a solution robust to most-likely assignments of these random variables. Recently, the Confidence constraint has been introduced by Mercier-Aubin et al. in order to enforce this type of robustness in constraint programming. Unfortunately, it is restricted to a conjunction of binary inequalities In this paper, we generalize the Confidence constraint to any constraint and propose an implementation based on Multi-valued Decision Diagrams (MDDs). The Confidence constraint is defined over a vector of random variables. For a given constraint C, and given a threshold, the Confidence constraint ensures that the probability for C to be satisfied by a sample of the random variables is greater than the threshold. We propose to use MDDs to represent the constraints on the random variables. MDDs are an efficient tool for representing combinatorial constraints, thanks to their exponential compression power. Here, both random and decision variables are stored in the MDD, and propagation rules are proposed for removing values of decision variables that cannot lead to robust solutions. Furthermore, for several constraints, we show that decision variables can be omitted from the MDD because lighter filtering algorithms are sufficient. This leads to gain an exponential factor in the MDD size. The experimental results obtained on a chemical deliveries problem in factories – where the chemicals consumption are uncertain – shows the efficiency of the proposed approach.

IJCAI Conference 2019 Conference Paper

Constraint Games for Stable and Optimal Allocation of Demands in SDN

• Anthony Palmieri
• Arnaud Lallouet
• Luc Pons

Software Defined Networking (or SDN) allows to apply a centralized control over a network of computers in order to provide better global throughput. One of the problem to solve is the multi-commodity flow routing where a set of demands (or commodities) have to be routed at minimum cost. In contrast with other versions of this problem, we consider here problems with congestion that change the cost of a link according to the capacity used. We propose here to study centralized routing with Constraint Programming and selfish routing with Constraint Games. Selfish routing reaches a Nash equilibrium and is important for the perceived quality of the solution since no user is able to improve his cost by changing only his own path. We present real and synthetic benchmarks with hundreds or thousands players and we show that for this problem the worst selfish routing is often close to the optimal centralized solution.

IJCAI Conference 2017 Conference Paper

Constraint Games revisited

• Anthony Palmieri
• Arnaud Lallouet

Constraint Games are a recent framework proposed to model and solve static games where Constraint Programming is used to express players preferences. In this paper, we rethink their solving technique in terms of constraint propagation by considering players preferences as global constraints. It yields not only a more elegant but also a more efficient framework. Our new complete solver is faster than previous state-of-the-art and is able to find all pure Nash equilibria for some problems with 200 players. We also show that performances can greatly be improved for graphical games, allowing some games with 2000 players to be solved.

IJCAI Conference 2011 Conference Paper

Constraint Programming on Infinite Data Streams

• Arnaud Lallouet
• Yat-Chiu Law
• Jimmy H. M. Lee
• Charles F. K. Siu

Classical constraint satisfaction problems (CSPs) are commonly defined on finite domains. In real life, constrained variables can evolve over time. A variable can actually take an infinite sequence of values over discrete time points. In this paper, we propose constraint programming on infinite data streams, which provides a natural way to model constrained time-varying problems. In our framework, variable domains are specified by ω -regular languages. We introduce special stream operators as basis to form stream expressions and constraints. Stream CSPs have infinite search space. We propose a search procedure that can recognize and avoid infinite search over duplicate search space. The solution set of a stream CSP can be represented by a Bü chi automaton allowing stream values to be non-periodic. Consistency notions are defined to reduce the search space early. We illustrate the feasibility of the framework by examples and experiments.

IJCAI Conference 2007 Conference Paper

• Marco Benedetti
• Arnaud Lallouet
• J
• eacute; r
• eacute; mie Vautard

The QCSP+ language we introduce extends the framework of Quantified Constraint Satisfaction Problems (QCSPs) by enabling us to neatly express restricted quantifications via a chain of nested CSPs to be interpreted as alternately conjuncted and disjuncted. Restricted quantifiers turn out to be a convenient solution to the crippling modeling issues we encounter in QCSP and - surprisingly - they help to reuse propagation technology and to prune the search space. Our QCSP+ solver - which also handles arithmetic and global constraints - exhibits state-of-the-art performances.

IJCAI Conference 2003 Conference Paper

Finite Domain Constraint Solver Learning

• Arnaud Lallouet
• Thi-Bich-Hanh Dao
• Andrei Legtchenko
• AbdelAli Ed-Dbali

In this paper, we present an abstract framework for learning a finite domain constraint solver modeled by a set of operators enforcing a consistency. The behavior of the consistency to be learned is taken as the set of examples on which the learning process is applied. The best possible expression of this operator in a given language is then searched. We instantiate this framework to the learning of bound-consistency in the indexical language of Gnu-Prolog.