Thierry Petit

IJCAI Conference 2016 Conference Paper

Optimizing Molecular Cloning of Multiple Plasmids

• Thierry Petit
• Lolita Petit

In biology, the construction of plasmids is a routine technique, yet under-optimal, expensive and time-consuming. In this paper, we model the Plasmid Cloning Problem in constraint programing, in order to optimize the construction of plasmids. Our technique uses a new propagator for the AtMostNVector constraint. This constraint allows the design of strategies for constructing multiple plasmids at the same time. Our approach recommends the smallest number of different cloning steps, while selecting the most efficient steps. It provides optimal strategies for real instances in gene therapy for retinal blinding diseases.

IJCAI Conference 2015 Conference Paper

Finding Diverse Solutions of High Quality to Constraint Optimization Problems

• Thierry Petit
• Andrew C. Trapp

A number of effective techniques for constraintbased optimization can be used to generate either diverse or high-quality solutions independently, but no framework is devoted to accomplish both simultaneously. In this paper, we tackle this issue with a generic paradigm that can be implemented in most existing solvers. We show that our technique can be specialized to produce diverse solutions of high quality in the context of over-constrained problems. Furthermore, our paradigm allows us to consider diversity from a different point of view, based on generic concepts expressed by global constraints.

ECAI Conference 2014 Conference Paper

Self-decomposable Global Constraints

• Jean-Guillaume Fages
• Xavier Lorca
• Thierry Petit

Scalability becomes more and more critical to decision support technologies. In order to address this issue in Constraint Programming, we introduce the family of self-decomposable constraints. These constraints can be satisfied by applying their own filtering algorithms on variable subsets only. We introduce a generic framework which dynamically decompose propagation, by filtering over variable subsets. Our experiments over the CUMULATIVE constraint illustrate the practical relevance of self-decomposition.

IJCAI Conference 2013 Conference Paper

Three Generalizations of the FOCUS Constraint

• Nina Narodytska
• Thierry Petit
• Mohamed Siala
• Toby Walsh

The FOCUS constraint expresses the notion that solutions are concentrated. In practice, this constraint suffers from the rigidity of its semantics. To tackle this issue, we propose three generalizations of the FOCUS constraint. We provide for each one a complete filtering algorithm as well as discussing decompositions.

ECAI Conference 2012 Conference Paper

An O(nlog n) Bound Consistency Algorithm for the Conjunction of an alldifferent and an Inequality between a Sum of Variables and a Constant, and its Generalization

• Nicolas Beldiceanu
• Mats Carlsson
• Thierry Petit
• Jean-Charles Régin

This paper gives an O( nlog  n) bound-consistency filtering algorithm for the conjunction alldifferent( V0, V1, … ,Vn− 1) ∧ f( V0) ⌖ f( V1) ⌖ … ⌖ f( Vn− 1) ≤ cst, ( V0, V1, … ,Vn− 1, cst∈ +) , where (, ⌖) is a commutative group, f is a unary function, and both ⌖ and f are monotone increasing. This complexity is equal to the complexity of the bound-consistency algorithm of the alldifferent constraint.

ECAI Conference 2012 Conference Paper

Intermediary Local Consistencies

• Thierry Petit

We propose a new definition for characterizing levels of consistency. A perspective is to provide new tools for classifying filtering algorithms, including incomplete algorithms based on the semantics of constraints.

IJCAI Conference 2011 Conference Paper

A Generalized Arc-Consistency Algorithm for a Class of Counting Constraints

• Thierry Petit
• Nicolas Beldiceanu
• Xavier Lorca

This paper introduces the Seqbin meta-constraint with a polytime algorithm achieving generalized arc-consistency. Seqbin can be used for encoding counting constraints such as Change, Smooth, or InncreasingNValue. For all of them the time and space complexity is linear in the sum of domain sizes, which improves or equals the best known results of the literature.

IJCAI Conference 2009 Conference Paper

• Christian Bessiere
• Thierry Petit
• Bruno Zanuttini

We study under what conditions bound consistency (BC) and arc consistency (AC), two forms of propagation used in constraint solvers, are equivalent to each other. We show that they prune exactly the same values when the propagated constraint is connected row convex / closed under median and its complement is row convex. This characterization is exact for binary constraints. Since row convexity depends on the order of the values in the domains, we give polynomial algorithms for computing orders under which BC and AC are equivalent, if any.

IJCAI Conference 2007 Conference Paper

• Christian Bessiere
• Remi Coletta
• Thierry Petit

Finding a constraint network that will be efficiently solved by a constraint solver requires a strong expertise in Constraint Programming. Hence, there is an increasing interest in automatic reformulation. This paper presents a general framework for learning implied global constraints in a constraint network assumed to be provided by a non-expert user. The learned global constraints can then be added to the network to improve the solving process. We apply our technique to global cardinality constraints. Experiments show the significance of the approach.