RÉGIN , Jean-Charles

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...

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...

In this paper, we introduce a new multi-objective optimization problem derived from a real-world application: the package server location problem. A number of package servers are to be located at nodes of a network. Demand for these package servers is located at each node, and a subset of nodes are to be chosen to locate one or more package...

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]....

International audience

One of the main problems for a realistic journey planning in public transit is the need to give the user multiple qualitative choices. Usually, public transit journeys involve 4 main criteria: the departure time, the arrival time, the number of transfers and the walking distance. The problem of computing Pareto sets with these criteria is...

International audience

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...

The bin packing problem is one of the core problems of cloud computing management. It corresponds to the problem of assigning virtual machines to servers. However, cloud computing also imposes a huge variety of constraints on this problem and most of them can not be expressed a priori. Constraint Programming (CP) has been proved efficient for...

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...

M. Sellmann showed that CP-based Lagrangian relaxation gave good results but the interactions between the two techniques were quite dicult to understand. There are two main reasons for this: the best multipliers do not lead to the best ltering and each ltering disrupts the Lagrangian multiplier problem (LMP) to be solved. As the resolution of...

Several models based on constraint programming have been proposed to solve the traveling salesman problem (TSP). The most efficient ones, such as the weighted circuit constraint (WCC), mainly rely on the Lagrangian relaxation of the TSP, based on the search for spanning tree or more precisely "1-tree". The weakness of these approaches is that...

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...

We address the problem of verifying a constraint by a set of solutions S. This problem is present in almost all systems aiming at learning or acquiring constraints or constraint parameters. We propose an original approach based on MDDs. Indeed, the set of solutions can be represented by the MDD denoted by M DDS. Checking whether S satisfies a...

International audience

International audience

We propose improved algorithms for defining the most common operations on Multi-Valued Decision Diagrams (MDDs): creation, reduction, complement , intersection, union, difference, symmetric difference, complement of union and complement of intersection. Then, we show that with these algorithms and thanks to the recent development of an...

In this paper we introduce a new cardinality constraint: ORDEREDDISTRIBUTE. 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...

In this paper we introduce a new cardinality constraint: ORDEREDDISTRIBUTE. 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 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...

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 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...

Nous présentons le Goal Directed Connection Scan Algorithm (GDCSA), qui améliore le Connection Scan Algorithm en guidant la recherche d'itinéraire pour les transports en commun multicritères. Nous montrons que le GDCSA diminue assez le temps de réponse pour permettre une utilisation interactive du calcul d'itinéraire sur des réseaux de...

Constraint toolkits generally propose a sum constraint where a global objective variable should be equal to a sum of local objective variables, on which bound-consistency is achieved. To solve optimization problems this propagation is poor. Therefore, ad-hoc techniques are designed for pruning the global objective variable by taking account of...