Methodes de résolution

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

Séparation et évaluation


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

Symmetries managment

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

Branch and Bound extension

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.

Choosing a Lower bound

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.

Software design

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

Publications or Communications

Programmation Dynamique

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

Publications or Communications

  • 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

Programmation par Contraintes

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.

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

Deterministic parallel search

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.

Portfolio parallelization

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

Publications or Communications