RÉGIN , Jean-Charles

Most of the current algorithms dedicated to the resolution of over-constrained problems, as PFC-MRDAC, are based on the search for a support for each value of each variable taken independently. The structure of soft constraints is only used to speed-up such a search, but not to globally deduce the existence or the absence of support. These...

Le but de ce document n'est pas de faire une synthèse des travaux récents en PPC, mais de mettre en évidence mes contributions dans ce domaine. Je ne parlerai donc pas de nombreux aspects de la PPC comme la détection et l'élimination des symétries ou les méthodes de recherche car je n'ai publié aucun article sur ces sujets. Je ne parlerai pas...

Constraint Programming (CP) is a general technique for solving combinatorial optimization problems. Real world problems are quite complex and solving them requires to divide work into different parts. Mainly, there are: the abstraction of interesting and relevant sub-parts, the definition of benchmarks and design of a global model and the...

In this paper we introduce a new cardinality constraint: Ordered Distribute. Given a set of variables, this constraint limits for each value v the number of times v or any value greater than v is taken. It extends the global cardinality constraint, that constrains only the number of times a value v is taken by a set of variables and does not...

We introduce GAC-4R, MDD-4, and MDD-4R three new algorithms for maintaining arc consistency for table and MDD constraints. GAC-4R improves the well-known GAC-4 algorithm by managing the internal data structures in a different way. Instead of maintaining the internal data structures only by studying the consequences of deletions, we propose to...

Plusieurs modèles basés sur la programmation par contraintes ont été proposés pour résoudre le problème du voyageur de commerce (TSP). Les plus efficaces, telle que la weighted circuit constraint (WCC), s'appuient prin-cipalement sur la relaxation lagrangienne du TSP, basée sur la recherche d'arbres recouvrants ou plus précisément de...

The TSP is the problem of finding a single cycle going through all the vertices of a graph suchthat the sum of the costs of the edges it contains is minimal. It has many applications andhas been motivated by concrete problems, such as school bus routes, logistics, routing, etc. Itis solved in CP with the WCC [2] and the k-cutset constraint [4]....

This papers extends in three ways our previous work about efficient operations on Multi-valued Decision Diagrams (MDD) for building Constraint Programming models. First, we improve the existing methods for transforming a set of tuples, Global Cut Seeds or sequences of tuples into MDDs. Then, we present in-place algorithms for adding and...

Multi-valued Decision Diagrams (MDDs) have been extensively studied in the last ten years. Recently, efficient algorithms implementing operators such as reduction, union, intersection , difference, etc., have been designed. They directly deal with the graph structure of the MDD and a time reduction of several orders of magnitude in comparison...

We consider the resolution by constraint programming of large problems, i.e. involving millions of constraints, which mainly imply arithmetic constraints, like shortest path problems or other related problems. We show that a simple constraint programming model is not competitive with dedicated algorithms (or dedicated constraints). This mainly...

We consider the resolution by constraint programming of large problems, i.e. involving millions of constraints, which mainly imply arithmetic constraints, like shortest path problems or other related problems. We show that a simple constraint programming model is not competitive with dedicated algorithms (or dedicated constraints). This mainly...