## En bref

This pages relates my work on *methods* usually used to solve combinatorial
optimization methods. Sometimes, the research is in the context of a specific parallelizations of
a problem

This pages relates my work on *methods* usually used to solve combinatorial
optimization methods. Sometimes, the research is in the context of a specific parallelizations of
a problem

I have worked on Branch and bound for different problems. The first was the QAP, that use the classical Gilmore and Lawler bound. The branching strategy was proposed by Thierry Mautor.

To perform the different experimental results of Bob, I have implemented a simulation of Branch and Bound, that can be foud in the Bob++ framework.

I have also study a Branch and Price method to solve a Vehicle routing prolem (VRP). This code has been ported to Bob, a simple VRP has been also implemented in Bob++.

Thierry Mautor, has worked for its Phd an algorithm to break the generation of symmetrical confguration. Many instances of many problems have solutions that are symmetric. In the 2D-cutting stock problem, the symmetry was break using a closed list like the A* algorithms. We propose different heuristics that avoid the generation of symmetrical solutions. In the Q3AP, the 3 dimensional quadratic assignment problem, there also exist symmetric solution.

At each time we propose the approach is "pruning of the enumeration tree" as explained in the survey proposed by F. Margo

The resolution of the 2D-cutting stock problem uses a particular Branch and Bound algorithm. A lower bound is used, an upper bound is given at the beginning of the search and update during the search, But the branching strategy is very particular.

It is not really a "branch", but a "combine" operation. We can consider the resolution of the constraint 2D CSP, like a Dynamic programming procedure, with an evaluation function, which is an A* algorithm.

Recent research have proposed very tight lower bound for many problem. In some cases, the quality of the bound permits to solve larger problem, since is reduce the size of the search tree.

Having the best lower bound to solve a problem using a branch and bound, is not necessarly the best choice. It depends on the number of nodes that are cut in comparison against the size of the tree when a worse lower bound is choosen.

A big aspect of my research is to design "reusable" software for this kind of methods. Have a look on my software page.

**CuHL97**:V Cung , M Hifi , B LeCun ,*"Constrained Two-Dimensional Cutting Stock Problems - A Best-First Branch-and-Bound Algorithm"*, PRISM, 1997, Num:20**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**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,**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,**Lecu07**:B LeCun ,*"Logiciels libres pour le développement de Branch and Bound séquentiels ou parallèles"*, Joint conference Roadef-Francoro 2007, Grenoble, France, Feb, 2007,**GaLe09**:F Galea , B LeCun ,*"Gestion des symétries dans une résolution exacte de l'affectation quadratique à trois dimensions"*, Roadef 2009, Nancy, France, Feb, 2009, Abstract slide

The dynamic programming method is for me one of the most efficient method to solve an optimization problem. The method is often a based to obtain a polynomial or pseudo-polynomial algorithm to solve a problem.

I use it to compute a column in a Branch and Price to solve a CTW-VRP. In order to speed-up the search, a lower bound is used to cut branches earlier than in the classical DP scheme. This method ressembles to an A* algorithm.

But I teach several times Dymnamic Programming method

**CuHL97**:V Cung , M Hifi , B LeCun ,*"Constrained Two-Dimensional Cutting Stock Problems - A Best-First Branch-and-Bound Algorithm"*, PRISM, 1997, Num:20**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**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

In the context of the OSEO-ISI Pajero Project, I work with Tarek Menouer on the parallelization of Constraint programming solvers. We study different way to parallelize Constriant Programming solvers by using the OR-Tools on top of our Bobpp framework.

The team who develops OR-Tools is very dynamic, the library is regularly extended with new algorithms to improve the portion of Constraint Programming. OR-Tools has been used in parallel, however, the parallelization is based on the principle of portfolio of local search. Parallelizing OR-Tools on top of the Bobpp framework must be studied without modiying OR-Tools.

The notion of node is critical to parallelize a tree-search based algorithm. To migrate a search from a core to another one, we need to represent it in an object; for example, all data about the history of the path and the changing data during the exploration of the search-tree. The initial design of OR-Tools makes the library sequential, so this notion of node could be clearly identified. However, the OR-Tools library provides mechanisms called monitor used to control research. Indeed, it is possible to save the search branches and to stop or replay a branch.

The aim is to parallelize a search using multiple instances of the solver running on different computing cores. The Bobpp framework is used as the runtime support in order to perform the load balancing between the different solver instances. Our parallelization runs on manycores using (POSIX threads). Recently we have modified Bobpp to be able to run the OR-Tools parallelization on top of the hybrid Pthread/MPI parallel environment.

We obtain good performances with this parallization, only if we take care on the deep of a node.

Oftently, users request that solvers responds the same solution from one run to another. We have addressed this problem in the context, where the sequential CP solver used in the parallelisation is deterministic by simply introduce a total order between the solutions that may be found in sequential. So we can force the parallel solver to respond the smallest solution even if the scheduling, the number of cores used change.

We have began to study the resolution of problem using a portfolio of OR-Tools solvers using different strategies.

**MLV12**:T Menouer , B LeCun , P Vander-Swalmen ,*"Solving Combinatorial Problems on HPC with bobpp"*, WolfHPC, in SuperComputing 2012, Salt Lake City, USA, Novembre, 2012,**MLV13a**:T Menouer , B LeCun , P Vander-Swalmen ,*"Parallélisation d'un solveur de contraintes avec le framework parallèle BOBPP"*, Compas'2013, Grenoble, France, Janvier, 2013,**MLV13b**:T Menouer , B LeCun , P Vander-Swalmen ,*"Parallélisation de solveur de contrainte OR-Tools"*, Roadef 2013, Troyes, France, Februar, 2013,**MLV13c**:T Menouer , B LeCun , P Vander-Swalmen ,*"Partitioning Methods to Parallelize Constraint Programming Solver using the Parallel Framework Bobpp"*, International Conference on Computer Science, Applied Mathematics and Applications, Warsaw, Poland, Editor:Studies in Computational Intelligence of Springer-Verlag, May, 2013, , Access to the publication**ML13a**:T Menouer , B LeCun ,*"Anticipated Dynamic Load Balancing Strategy to parallelize Constraint Programming search"*, PCO'13, workshop of IPDPS'13, Boston, USA, Editor:IEEE, may, 2013, , Access to the publication**ML13b**:T Menouer , B LeCun ,*"A Parallelization Mixing OR-Tools/Gecode Solvers on top of the Bobpp Framework"*, 3PGCIC13 (International Conference on P2P, Parallel, Grid, Cloud and Internet Computing), Compiegne, France, Editor:IEEE, oct, 2013, , Access to the publication**ML14a**:T Menouer , B LeCun ,*"Portfolio Adaptatif pour la Parallélisation d'un solveur de Programmation Par Contraintes"*, Roadef 2014, Bordeaux, France, februar, 2014, , Access to the publication**ML14b**:T Menouer , B LeCun ,*"Deterministic Partitioning Strategy to Parallelize the Constraint Programming Search Space"*, 22nd High Performance Computing Symposium (HPC 2014), Editor:ACM/SIGM, April, 2014, , Access to the publication**ML14c**:T Menouer , B LeCun ,*"Partitionnement Déterministe pour Résoudre les Problèmes de Programmation Par Contraintes en utilisant le Framework Parallèle Bobpp."*, Compas'2014, Neuchatel, France, April, 2014, , Access to the publication