News

Problèmes d'Optimisation

En bref

I have worked, and I continue to work on different Optimization Problems. Most of them are Combinatorial optimization problems. In most of cases, the aim of my work is to obtain an exact solver of the problem. Then, I study the lower bound, branching strategy and symmetry mangement. Almost all problem have been implemented on top of Bob or Bob++. Recently (2010, I have started the study of Crew Scheduling problem using Mathematical Programming and local search, and some problems that deals with Energy optimization.

Bin packing with fragmentable items

Joined Work with Thierry Mautor, Franck Quessette, Marc-Antoin Weisser

In this work, we consider a variant of the Bin packing or Cutting Stock Problem dealing with fragmentable items. Given a fixed number of bins, the objective is to put all the required items into the bins by splitting them in a minimum number of fragments. This problem is useful for modeling splittable resource allocation.

Publications or Communications

Optimisation dans le Vehicle2Grid

In this work, we tackle the energy optimization problem in a Vehicle-to-grid (V2G) context. The main idea of V2G is to use electrical vehicles' batteries to temporarily store energy. Our goal is to decide, for each vehicle connected to the smart-grid, if its battery is going to be loaded or unloaded to contribute to the electrical production. As a consequence, a production curve smoothing is feasible and enable a reduction in the use of our very polluting thermal power plants (in terms of CO²).

Some previous works have studied the economical viability of such a project by assuming time average over long periods of time. Moreover this approach is supported by the fact that a vehicle stays unused on average 96% of the time.

We will consider electric vehicles to be the property of a car rental society (or an institution) called the aggregator. In this context, we try to optimize the production curve's smoothing by modeling the problem with a mathematical program considering each vehicle individually. This allows us not only to determine precisely load/unload policies to apply to each vehicle but also to observe the effects of different number of electric vehicles per inhabitant ratio over the optimization.

Publications or Communications

Problème d'Habillage

Le problème d'affectation de personnel (en anglais Crew Scheduling Problem raccourci en csp) est un des problèmes les plus difficiles à résoudre pour les exploitants de réseaux de transport en commun. Bien évidemment, ce problème est d'une importance stratégique. Nous nous intéressons ici à la résolution de problèmes réels dans les domaines du transport ferré et routier (train, tramway, bus). Ceux-ci divergent des problèmes académiques par le nombre élevé de contraintes difficiles à introduire dans une méthode classique de résolution. De même, la taille des instances que nous souhaitons résoudre est plus important que celles habituellement étudiées par la communauté universitaire. Comme point de départ de nos travaux, nous avons choisi d'étudier l'apport en terme de qualité de solution et de rapidité de résolution d'une méta-heuristique. Pour accélérer et/ou améliorer ce traitement, il a semblé intéressant d'utiliser la puissance de calcul aujourd'hui disponible, à savoir les processeurs multi-coeurs. Nous avons donc choisi d'appliquer une méta-heuristique, ici un vns (Variable Neighborhood Search), dans un cadre parallèle pour attaquer les problèmes de csp que nous souhaitons résoudre. Ces travaux sont réalisés dans le cadre du projet ANR intitulé HORUS (Horaires Optimisés dans les Réseaux de transports Urbains et interurbainS).

Publications or Communications

Problème d'affectation quadratique à 3 dimensions

the alt

For the ANR Choc project, I have worked on the 3D dimensional Quadratic assignement problem. this problem is an extension of the QAP. We have develop with Francois Galea, an exact Q3AP solveur on top of Bobpp. The lower bound used is a dual formulation of a RLT1 relaxation of the Q3AP. We have also develop two specific branching strategy in order to avoid the construction of symmetrical configurations. This exact solver also use a heuristic that generate feasible solution based on the evaluation of each node.

For the first time, problem of size 16 has been solved, on 8 cores machines.

An EJOR article written with Francois Galea and Peter Hahn is in revision.

Publications or Communications

Problème d'affectation quadratique

Le problème d'affectation Quadratique est un des problèmes mythiques de l'equipe Opale. Il est sur que c'est celui qui a donné et continue à donner le plus de travail aux membres. Actuellement c'est le principal exemple dont nous nous servons pour Bob++. Ma contribution sur ce problème est pour l'instant très minime, j'ai essayé de travailler sur ce problème pour optimiser le calcul de bornes inférieures telles celles proposées par Peter Hahn.

I have used the our QAP solver to test several aspects of Bob and Bob++.

Publications or Communications

  • LeRo06:B LeCun , C Roucairol , "On the Lower bounds of the Quadratic Assignment Problem", European Chapter on Combinatorial Optimization : ECCO 2006, Porto, Portugal, May, 2006,
  • CuLR05:V Cung , B LeCun , C Roucairol , "Optimisation combinatoire parallèle", In Book:Optimisation combinatoire: applications, Publisher:V. Th Paschos, Editor:Hermès Science, 2005, Chap. 6 , isbn:2-7462-1179-3
  • CuLe01:V Cung , B LeCun , "Evaluating the impact of metacomputing on Combinatorial Optimization", EURO2001, Rotterdam Netherlands, Jul, 2001, Invited Semi-planary session
  • GaLe07:F Galea , B LeCun , "Bob++ : a Framework for Exact Combinatorial Optimization Methods on Parallel Machines", PGCO'2007 as part of the 2007 International Conference High Performance Computing & Simulation (HPCS'07) and in conjunction with The 21st European Conference on Modeling and Simulation (ECMS 2007), Prague, Czech Republic, Jun, 2007, pp:779--785,
  • Le96b:M Benaichouche , V Cung , S Dowaji , B LeCun , T Mautor , C Roucairol , "Building a Parallel Branch and Bound Library", In Book:SCOOP : Solving Combinatorial Optimization problems On Parallel architectures, Publisher:A.~Ferreira and P.M.~Pardalos, Editor:LNCS State-of-the-Art Survey, Springer-Verlag, 1996, Chap. , isbn:354061043X
  • Le96c:B LeCun , M Benaichouche , V Cung , S Dowaji , C Roucairol , "The Outcome of a Know-How: Parallel Branch and Bound Library", IFORS, International Federation of OR Societies, Vancouver, Canada, , 1996

2D Guillotin Cutting stock (2000)

Joined Work with Van-Dat Cung and Mhand Hifi

In this work, we develop a new version of a previous algorithm for solving exactly some variants of (un)weighted constrained two-dimensional cutting stock problems. We introduce one-dimensional bounded knapsacks in order to obtain an improved initial lower bound for limiting initially the size of the search space, an improved upper bound at each internal node and a symmetry detection for neglecting some useless duplicate patterns. A new efficient data structure of the set representing the best subproblems is used to implement the algorithms over the BOB library. The performance of our algorithms is evaluated on some problem instances of the literature and on other randomly generated hard problem instances (a total of 27 problem instances).

Dans ce travail, nous concevons une nouvelle version d'un algorithme précédent pour résoudre de manière exacte des problèmes de découpe en 2-dimensions contraints avec ou sans pondération. Nous introduisons des sacs à dos unidimensionnels contraints afin d'obtenir une meilleure borne inférieure initiale pour limiter la taille de l'espace de recherche, une meilleure borne supérieure pour chaque n  ud interne et une détection de symétries pour supprimer des configurations identiques. Une nouvelle structure de données efficace pour gérer les meilleurs sous-problèmes a été employée pour l'implémentation des algorithmes sur la bibliothèque BOB. La performance de nos algorithmes est évaluée sur 27 instances de problèmes extraites pour certaines de la littérature et d'autres difficiles, engendrées aléatoirement.

Rapport de Recherche Prism  97/020

Publications or Communications

  • CuHL00:V Cung , M Hifi , B LeCun , "Constrained Two-Dimensional Cutting Stock Problems - A Best-First Branch-and-Bound Algorithm", Internationl Transactions in Operational Research (ITOR), Editor:Wiley-Blackwell, 2000, pp:185-210, Vol:7, Num:3
  • CuHL97:V Cung , M Hifi , B LeCun , "Constrained Two-Dimensional Cutting Stock Problems - A Best-First Branch-and-Bound Algorithm", PRISM, 1997, Num:20

Vehicule Routing problem (1998-1999)

The aim of this work was to study a column generation based exact method to solve Vehicule Problem with capacity and time window constraints. The specifications of our problem are the following:

  • Several kinds of vehicles with different speed, fixed cost, time cost and distance cost would be used
  • the waiting time has to be taken int account in the objective function i.e. Penality is added when the vehicule wait the open time of the time window.
exemple de VRPexemple de VRP

As shown in the litterature, the crucial point in a column generation algorithm is the constraint shortest path algorithm used to find a column that must be added to the mathematical program at each simplex iteration. Usually, dynamic programming algorithm is used to solve this problem.

First we propose to use A* algorithms that could be seen as a dynamic programming algorithm where lower and upper bounds on path could be added to prune earlier dominated paths.

Second as usual dynamic programming formulation of this problem, the complexity of te A* algorithm, depends on the size of the time window i.e. The number of time units in the time window, and also on the number of edges between customers. We propose some new rules that allow us to reduce the graph.

We introduce the notion of intervals. The customers time windows are discretized in intervals. One interval on a customer i is defined by a period of time t where each partial path that arrives at i on time t in T are equivalent. The interval set on each customer, could also be used to proposed very efficient time window reducing rules, and as time unit in the A* algorithm.

We show on real problems that the number of intervals is really smaller than the number of time units associated to each customer. Then the entire algorithm is really more efficient.

This work has been done in the context of a research project for the French mail post company, "La Poste".

Publications or Communications

  • LeMR00a:B LeCun , T Mautor , C Roucairol , "Algorithme exact pour le problème de tournées de véhicules avec flotte hétérogène", Roadef 2000, Nantes, France, Jan, 2000,
  • LeMR00b:B LeCun , T Mautor , C Roucairol , "Constrained Shortest Path for a Vehicle Routing problem", Route2000, Rolighed Denmark, Aug, 2000, Invited conference
  • LeRo98:B LeCun , C Roucairol , "Exact resolution of a Vehicule Routing Problem", OR 40, International Conference of the UK OR Society, Lancaster, UK, aug, 1998,