Yves Deville

IJCAI Conference 2017 Conference Paper

Automatic Synthesis of Smart Table Constraints by Abstraction of Table Constraints

• Baudouin Le Charlier
• Minh Thanh Khong
• Christophe Lecoutre
• Yves Deville

The smart table constraint represents a powerful modeling tool that has been recently introduced. This constraint allows the user to represent compactly a number of well-known (global) constraints and more generally any arbitrarily structured constraints, especially when disjunction is at stake. In many problems, some constraints are given under the basic and simple form of tables explicitly listing the allowed combinations of values. In this paper, we propose an algorithm to convert automatically any (ordinary) table into a compact smart table. Its theoretical time complexity is shown to be quadratic in the size of the input table. Experimental results demonstrate its compression efficiency on many constraint cases while showing its reasonable execution time. It is then shown that using filtering algorithms on the resulting smart table is more efficient than using state of the art filtering algorithms on the initial table.

ICAPS Conference 2009 Conference Paper

Just-In-Time Scheduling with Constraint Programming

• Jean-Noël Monette
• Yves Deville
• Pascal Van Hentenryck

This paper considers Just-In-Time Job-Shop Scheduling, in which each activity has an earliness and a tardiness cost with respect to a due date. It proposes a constraint programming approach, which includes a novel filtering algorithm and dedicated heuristics. The filtering algorithm uses a machine relaxation to produce a lower bound that can be obtained by solving a Just-In-Time Pert problem. It also includes pruning rules which update the variable bounds and detect precedence constraints. The paper presents experimental results which demonstrate the effectiveness of the approach over a wide range of benchmarks.

AAMAS Conference 2002 Conference Paper

From AOSE Methodology to Agent Implementation

• Philippe Massonet
• Yves Deville
• C�dric Neve

AIJ Journal 1999 Journal Article

Constraint satisfaction over connected row-convex constraints

• Yves Deville
• Olivier Barette
• Pascal Van Hentenryck

This paper studies constraint satisfaction over connected row-convex (CRC) constraints. It shows that CRC constraints are closed under composition, intersection, and transposition, the basic operations of path-consistency algorithms. This establishes that path consistency over CRC constraints produces a minimal and decomposable network and is thus a polynomial-time decision procedure for CRC networks. This paper also presents a new path-consistency algorithm for CRC constraints running in time O(n 3 d 2) and space O(n 2 d), where n is the number of variables and d is the size of the largest domain, improving the traditional time and space complexity by orders of magnitude. The paper also shows how to construct CRC constraints by conjunction and disjunction of a set of basic CRC constraints, highlighting how CRC constraints generalize monotone constraints and presenting interesting subclasses of CRC constraints. Experimental results show that the algorithm behaves well in practice.

LOPSTR Conference 1998 Conference Paper

Logic Program Schemas, Constraints, and Semi-unification

• Eric Chasseur
• Yves Deville

Abstract Program schemas are known to be useful in different applications such as program synthesis, transformation, analysis, debugging, teaching. .. This paper tackles two complementary aspects of program schemas. We first propose a language for the description of program schemas. It is based on a subset of second-order logic, enhanced with constraints and specific features of program schemas. One of the basic operations on schemas is the semi-unification of a schema with a program. We then express the semi-unification process over schemas as rewriting and reduction rules, using CLP techniques, where constraints are used to guide the semi-unification process.

LOPSTR Conference 1996 Conference Paper

Logic Program Transformation through Generalization Schemata

• Pierre Flener
• Yves Deville

Abstract Both generalization techniques are very suitable for mechanical transformation: all operators of the generalized programs are operators of the initial programs. Given a divide-and-conquer program, a mere inspection of the properties of its solving, processing, and composition operators thus allows the detection of which kinds of generalization are possible, and to which optimizations they would lead. The eureka discoveries are compiled away, and the transformations can be completely automated.

LOPSTR Conference 1994 Conference Paper

Guiding Synthesis Proofs

• Vincent Lombart
• Geraint A. Wiggins
• Yves Deville

AIJ Journal 1992 Journal Article

A generic arc-consistency algorithm and its specializations

• Pascal Van Hentenryck
• Yves Deville
• Choh-Man Teng

Consistency techniques have been studied extensively in the past as a way of tackling constraint satisfaction problems (CSP). In particular, various arc-consistency algorithms have been proposed, originating from Waltz's filtering algorithm [27] and culminating in the optimal algorithm AC-4 of Mohr and Henderson [16]. AC-4 runs in O(ed 2) in the worst case, where e is the number of arcs (or constraints) and d is the size of the largest domain. Being applicable to the whole class of (binary) CSP, these algorithms do not take into account the semantics of constraints. In this paper, we present a new generic arc-consistency algorithm AC-5. This algorithm is parametrized on two specified procedures and can be instantiated to reduce to AC-3 and AC-4. More important, AC-5 can be instantiated to produce an O(ed) algorithm for a number of important classes of constraints: functional, anti-functional, monotonic, and their generalization to (functional, anti-functional, and monotonic) piecewise constraints. We also show that AC-5 has an important application in constraint logic programming over finite domains [24]. The kernel of the constraint solver for such a programming language is an arc-consistency algorithm for a set of basic constraints. We prove that AC-5, in conjunction with node consistency, provides a decision procedure for these constraints running in time O(ed).

LOPSTR Conference 1992 Conference Paper

Towards Stepwise, Schema-guided Synthesis of Logic Programms

• Pierre Flener
• Yves Deville

Abstract We present a general strategy for stepwise, sound and progressive synthesis of logic programs from specifications by examples and properties. We particularize this to schema-guided synthesis, and state a generic synthesis theorem. We justify some design choices for the development of a particular synthesis mechanism that is guided by a Divide-and-Conquer schema, is inductive and deductive, is interactive, and features a non-incremental presentation of examples. Some crucial steps of this mechanism are explained, and illustrated by a sample synthesis. We draw some conclusions on our results so far, state some related work, and outline future research directions.

IJCAI Conference 1991 Conference Paper

An Efficient Arc Consistency Algorithm for a Class of CSP Problems

• Yves Deville
• Pascal Van

Consistency Techniques have been studied extensively in the past as a way of tackling Constraint Satisfaction Problems (CSP). In particular various arc consistency algorithms have been proposed, originating from Waltz's filtering algorithm [20] and culminating in the optimal algorithm AC-4 of Mohr and Henderson [13]. AC-4 runs in 0(ed2 ) in the worst case where e is the number of arcs (or constraints) and d is the site of the largest domain. Being applicable to the whole class of (binary) CSP, these algorithms do not take into account the semantics of constraints. In this paper, we present a new generic arc consistency algorithm AC-5. The algorithm is parametrised on two specified procedures and can be instantiated to reduce to AC-3 and AC- 4. More important, AC-5 can be instantiated to produce an 0(ed) algorithm for two important classes of constraints: functional and monotonic constraints. We also show that AC-5 has an important application in Constraint Logic Programming over Finite Domains [18]. The kernel of the constraint-solver for such a programming language is an arc consistency algorithm for a set of basic constraints. We prove that AC-5, in conjunction with node consistency, provides a decision procedure for these constraints running in time 0(ed).