Loading...
Please wait, while we are loading the content...
Similar Documents
BOB : a Unified Platform for Implementing Branch-and-Bound like Algorithms
| Content Provider | Semantic Scholar |
|---|---|
| Author | Cun, Bertrand Le Roucairol, Catherine |
| Copyright Year | 1995 |
| Abstract | In this report, we propose the library BOB for an easy development of the Branch-and-Bound applications (min/maximization). This library has the double goal of allowing on the one hand the Combinatorial Optimization community to implement their applications without worrying about the architecture of the machines and beneeting the advantages provided by parallelism. On the other hand, BOB ooers to the community of Parallelism a set of benchmark composed by the eecient algorithms of Combinatorial Optimization for its parallelization methods and/or tools. To achieve this double goal, the BOB library is founded on the notion of global priority queue which makes the parallelization methods independent from the applications, and vice-versa. We describe for this global priority queue diierent implementation models (asynchronous, synchronous, client/server, ...) according to the type of used machine (serial, parallel with shared or distributed memory). is provided to achieve the global priority queue. We also emphasis on the conception of BOB and its main components (user functions, kernel functions and monitor), in particular the management of the global upper/lower bound in parallel environment. Finally, we show with an example how easy to develop Branch-and-Bound applications with this library. BOB : une Plate-forme Unii ee de D eveloppement pour les Algorithmes de type Branch-and-Bound z R esum e : Nous proposons, dans ce rapport, une biblioth eque d'aide au d eveloppement d'applications de type Branch-and-Bound BOB (min/maximisation). Cette biblioth eque a le double objectif d'une part, de permettre a la communaut e de l'Optimisation Com-binatoire d'impl ementer ses applications sans se soucier de l'architecture des machines et de prooter des avantages du parall elisme; et d'autre part, d'oorir a la communaut e de Parall elisme un banc d'essai, compos e d'algorithmes performants de l'Optimisation Combinatoire, pour ses m ethodes et/ou outils de parall elisation. Pour r ealiser ce double objectif, la biblioth eque BOB est fond ee sur la notion de le de priorit e globale qui permet de rendre transparentes les m ethodes de parall elisation vis a vis des applications, et vice-versa. Nous d ecrirons pour cette le de priorit e globale, dii erents mod eles d'impl ementation (asynchrone, synchrone, client/serveur, ...) suivant le type de machine utilis ee (s equentiel, parall ele a m emoire partag ee ou a m emoire distribu ee). Un ensemble de structures de donn ees s equentielles et concurrentes (D-Heap, Skew-Heap, Implicite-Heap, Funnel-Tree, Splay-Trees, ...) est propos e pour la r … |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.prism.uvsq.fr/~vdc/RAPPORTS/bob_RR95.16.ps.Z |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
