MALAPERT , Arnaud

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

This paper considers the scheduling of job families on parallel machines with time constraints on machine qualifications. In this problem, each job belongs to a family and a family can only be executed on a subset of qualified machines. In addition, machines can lose their qualifications during the schedule. Indeed, if no job of a family is...

Constraint programming is a paradigm for solving combinatorial problems. Yet solving complex problems may be a lengthy process. Embarrassingly Parallel Search (EPS) is "a simple and efficient method for solving constraint programming problems in parallel". While EPS is a very generic method, its implementations are strongly dependent on the...

We present a constraint programming formulation for the elevator trip origin-destination matrix estimation problem, and propose different approaches to solve the problem. An elevator trip consists of successive stops in one direction of travel with passengers inside the elevator. It can be defined as a directed network, where the nodes...

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 present a constraint programming formulation for the elevator trip origin-destination matrix estimation problem, and propose different approaches to solve the problem. An elevator trip consists of successive stops in one direction of travel with passengers inside the elevator. It can be defined as a directed network, where the nodes...

This paper studies the scheduling of jobs of different families on parallel machines with qualification constraints. Originating from semiconductor manufacturing, this constraint imposes a time threshold between the execution of two jobs of the same family. Otherwise, the machine becomes disqualified for this family. The goal is to minimize...

A finite language X over an alphabet S is complete if any word in S^* is a factor of a word in X^*. A word which is not a factor of X^* is said uncompletable. Among them, some are minimal as all their proper factors belong to Fact(X^*). The problem is to find bounds on the length of the shortest minimal uncompletable words depending on k, the...

This paper presents a framework taking advantage of both the flexibility of constraint programming and the efficiency of operations research algorithms for solving scheduling problems under various objectives and constraints. Built upon a constraint programming engine, the framework allows the use of scheduling global constraints, and it...

We introduce an Embarrassingly Parallel Search (EPS) method for solving constraint problems in parallel, and we show that this method matches or even outperforms state-of-the-art algorithms on a number of problems using various computing infrastructures. EPS is a simple method in which a master decomposes the problem into many disjoint...

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

This paper presents a framework taking advantage of both the flexibility of constraint programming and the efficiency of operations research algorithms for solving scheduling problems under various objectives and constraints. Built upon a constraint programming engine, the framework allows the use of scheduling global constraints, and it...

We propose an adaptation of the Embarrassingly Parallel Search (EPS) method for data centers. EPS is a simple but efficient method for parallel solving of CSPs. EPS decomposes the problem in many distinct subproblems which are then solved independently by workers. EPS performed well on multi-cores machines (40), but some issues arise when using...

A finite language X over an alphabet Σ is complete if any word in Σ* is a factor of a word in X*. A word which is not a factor of X* is said uncompletable. Among them, some are minimal as all their proper factors belong to Fact(X*). The problem is to find bounds on the length of the shortest minimal uncompletable words depending on k, the...

We propose the Embarrassingly Parallel Search, a simple and efficient method for solving constraint programming problems in parallel. We split the initial problem into a huge number of independent subproblems and solve them with available workers (i.e., cores of machines). The decomposition into subproblems is computed by selecting a subset of...

Nous introduisons une nouvelle stratégie de recherche pour énumérer toutes les solutions d'un problème de satisfaction de contraintes. L'idée principale de cette stratégie consiste à énumérer des solutions génériques à partir desquelles toutes les solutions peuvent être efficacement calculées. Les solutions génériques contiennent des valeurs...

In this article, we present the flight radius problem on the condensed network. This problem consists of locating in the network what routes represent business opportunities that are attractive regarding time or cost criteria, and passing through a specific flight. We introduce a regret function to model the regret compared to the optimal value...

This work is a study toward a global constraint minimizing the flowtime of a single machine scheduling problem. Classical methods for filtering algorithms use a lower bound coming from the solution of a relaxation. Notably, there are several polynomial relaxations to minimize the flowtime on a single machine. A general scheme for the global...

In 2011, Kovács and Beck defined the completion global constraint for minimizing the weighted flowtime for a single resource. This constraint is part of the cost-based domain filtering approach and as such, aims at removing values from the variables domains that cannot lead to a solution with a better cost than the best one found so far. The...