Software

The core of my research activities is focused on the design, implementation and analysis of algorithmic approaches for the efficient and effective solving of optimization problems. In addition, within the context of my Ph.D supervising we have an increasing activity in software development driven by our goal of making our algorithmic contributions openly available to the optimization community. On the one hand, this leads us to develop some homemade prototype codes: Permutation Branch-and-Bound (pBB), Python library for Surrogate-based Optimization (pySBO) and Productivity- and Performance-aware Parallel Distributed Depth-First Search (P3D-DFS). On the other hand, we started in 2020 to develop the more ambitious Python-based Parallel and distributed Evolving Objects (PyParadisEO) software framework within the context the PyParadisEO project supported by Inria (see Section "Granted projects"). The four software tools are detailed in the following:

• PyParadisEO is a Python version of ParadisEO, a C++-based open-source (CeCILL licence) whitebox framework dedicated to the reusable design of metaheuristics. ParadisEO allows the design and implementation of single-solution (Hill-Climbing, Tabu Search, Simulated annealing, Iterative Local Search - ILS, etc.) and population-based (Genetic algorithms, Particle Swarm Optimization (PSO), etc.) metaheuristics for single- and multi-objective, continuous, discrete and mixed optimization. The major parallel models (parallel evaluation of a population/neighborhood, island model, etc.) are also provided in the framework. ParadisEO has been launched within the framework of the Ph.D thesis of S. Cahon I have co-supervised (with E-G. Talbi). This framework has been popular (58.000+ downloads, 135.000+ visitors from 145 countries, 250+ users, 1000+ citations of related papers). However, C++ ParadisEO has lost ground to other frameworks developed in Python, which are more accessible especially to non experts in programming and metaheuristics. Supported by Inria, the goal of the PyParadisEO project is to migrate ParadisEO to Python in order to: (1) facilitate its use and gain in competitiveness, and (2) improve its interoperability with other solvers, simulators and ML tools (which is particularly important for our research program). After two years of development, we have a preliminary documented online version including single-objective metaheuristics. Our objective, if we get manpower, is to extend it to include multi/many-objective optimization, parallelism, decomposition and cooperation with ML.

• pySBO is a Python open-source (CeCILL licence) software aiming at facilitating the implementation of parallel surrogate-based optimization algorithms. pySBO provides re-usable components (surrogate models, evolution controls, infill criteria, evolutionary operators) as well as the foundations to allow their inter-changeability. Actual implementations of sequential and parallel surrogate-based optimization algorithms are supplied as ready-to-use tools to handle expensive single- and multi-objective problems. An illustrated documentation is available on-line through the below dedicated Web site. pySBO has mainly been developed by G. Briffoteaux during his Ph.D thesis I jointly supervised with D. Tuyttens, with a weak contribution from Monash University, Australia.

• pBB is an open-source (CeCILL licence) supplying various parallel implementations of the Branch-and-Bound (B&B) algorithm for permutation problems. B&B proceeds by implicit enumeration of the search space by parallel exploration of a highly irregular search tree. pBB contains implementations for single-core, multi-core, GPU and heterogeneous distributed platforms. Thanks to its hierarchical work-stealing mechanism, required to deal with the strong irregularity of the search tree, pBB is highly scalable. Scalability with up to 90% parallel efficiency on several hundreds of GPUs has been demonstrated on the Jean Zay supercomputer located at IDRIS, Paris. pBB has mainly been developed by J. Gmys during his Ph.D thesis, jointly supervised with D. Tuyttens, and extended to petascale B&B during his post-doc position under the same supervising.

  • P3D-DFS is a set of generic parallel Branch-and-Bound (B&B) skeletons written in Chapel for CPU-based systems, from multicore nodes to distributed clusters. The project investigates the Partitioned Global Address Space (PGAS) programming model as an alternative to MPI+X for implementing scalable parallel optimization algorithms, while promoting extensibility and accessibility for the community. The parallelization follows the parallel tree exploration model: multiple CPU threads explore disjoint subspaces of the B&B search tree concurrently. Each thread manages its own local work pool in Depth-First Search (DFS) order, while dynamic load balancing is achieved through work stealing to cope with irregular search trees. These mechanisms, together with the generic nature of the implementation, rely on the high-level and highly parallel distBag data structure, also referred to as distBag_DFS or DistBag_DFS. This data structure has also been integrated into the Chapel ecosystem as the DistributedBag package module. P3D-DFS was mainly developed by G. Helbecque during his Ph.D. thesis, which I co-supervised with P. Bouvry at the University of Luxembourg.