News

Logiciels

Introduction

One aspect of my research concerns the design of softwares to write solvers for optimization problems. These works began with Bob for Branch and Bound in the 1994, Bob have been extended with A*, IDA*, Divide and Conquer, and Dynamic programming. I have continue now with Bob++ where Divide and conquer, Branch and Bound are proposed as programming interface but also, a possibility of simulation, and Varaible neighborhood Search (VNS).

I have also written several sofwares that are for my private use at this time. Maybe, one time i will put them on the Web.

Softwares

Bob++

The goal of the Bob++ libray is to offer the base algorithms to write easily Branch and Bound algorithms, but also Divide and Conquer, Dynamic programming, and A* algorithms in parallel and in sequential. The library uses the doxygen language to present a documentation and the API of the Bob++ Libraries (surname bobo)).

At this time the development server of Bobpp is down (due to hardware problem). We are examining a new solution which will be more global to the laboratory.

Glop

Francois Galea has implemented a light library interface to test different linear solvers. This Library is used in Bob++ to solve the linear program on each node of Branch and Bound solving a Mixed integer program. I have written the C++ binding of glop called ppglop.

Glock

Christophe Louat has implemented a generic cut library on top of glop. This Library is also used in Bob++ to accelerate the resolution of Mixed Integer Programs.

Bob

The Bob Library is the ancestor of the Bob++ library. It was written in C and is not really maintained at this time. You could find a description of the Bob Library in the 95/16 PRiSM Report. One of the many versions of the libray could be downloaded. This version of the libray is 8 years old, then it is not sure that it could compiled on the actual linux system if i have time i will check it ! Bob1.0 only focus on Branch and Bound, a second version (2.0) includes the A* algorihms. Now i focus on the Bob++ library design in C++.

Frameworks d'optimisation : historique

When one works on parallelization of a specific methods, you should attempt to produce a unified framework to implement such methods in parallel or in sequential. The goal is then to simplify the life of the developpers.

For Branch and Bound, I begin very early to write such framework, during my master thesis (1991). I have to test several priority queue on shared memory machines (Sequent Balance, BBNT2000) used for Branch and Bound to solve several problems. Then when i begin my Phd (1992), I continue to extends the what we can call a framework.

In 1994, I realize that I have a Parallel Branch and Bound Framework to publish : Bob is born. I present the framework in several conferences. In the same time, PICO and PPBB was also born. I was not the only one to think about a design where an interface of problem programming is proposed.

As we were several phd Students to study the parallelizations of Tree Search algorithms in different context. It was natural to design the Framework to propose a Top interface and a Bottom interface. The top interface permits to develop the Problem's specific part. Although, the bottom interface was to develop parallelization for several contexts. The following Problems has been ported:

  • Simulation of Branch and Bound (B. LeCun)
  • Simple TSP using the QAP formulation (B. LeCun)
  • 15-Puzzle, using both A* and IDA*, A* and IDA* was implemented in Bob
  • QAP, with the gilmore and lawler bound and the symmetry test proposed by Thierry Mautor (B. LeCun,T. Mautor)
  • 2D Guillotin Cutting Stock (V-D. Cung,B. LeCun, M. Hifi)
  • QAP with RLT_1 relaxation (V.-D. Cung)
  • TSP (H. Trienekens)
  • SDP lower bound to solve various problems (V.-D. Cung, F. Roupin)
There were also several parallelisations proposed on top of various parallel libraries :
  • Posix Thread
  • PVM and then MPI master slaves strategies and distributed with load balancing strategies
  • Interface on top of PPBB.
  • Load balancing on top of an old version of PM2
  • Ported on top of Athapascan the old version of kaapi
  • Ported on top of Charm++
Then, by the end of 90's, I began to implement the Bob++ framework. Now many frameworks such as Bob or Bob++ exist :

Misc

I have written several sofwares that are only for my private use at this time. Maybe, one time i will put them on the Web.

Conception

The design of such tool is difficult to publish. I try several time, but it is considered more like ingeneering than research. But I think that designing software change the understanding of the methods.

Bob++ is design to handle a specific programming model of applications. In short terms, Bob++ is designed to search a specific node in the search space that is dynamically generated. The search is controlled by a Goal which manages if a generated node is suitable to be explorated later or not.

Then Bob++ like many of the other tools (COIN, ZRAM, PPBB, PICO ...) is a framework, where the developper's code does not really call the Bob++ function or methods, but the developper code is called by Bob++. The developper code must defined

  • Type for a node
  • Function to initialize the search : create and insert the root nodes.
  • Function to generate child node from a specific node.

Then the Framework is design like a hierarchy of several classes that have specific behaviour according to a specific methods.

Bob++ specificity is maily to be able several parallelizations and use several communication libraries.

Recently we have added an algorithm to perform simulation and also a VNS. The simulation Algorithm is integrated in the framework, since the VNS will be integrated soon.