Parallel Metaheuristics

Training by El-Ghazali Talbi

Acireale, Sicily, 21–25 July 2018

A Unified View of Metaheuristics

Training by El-Ghazali Talbi

Acireale, Sicily, 21–25 July 2018

Heterogeneous Cluster Computing for Many-Task Exact Optimisation

Training by Jan Gmys

Ljubljana, 13 December 2017

Branch-and-Bound (B&B) is a frequently used tree-search exploratory method for the exact resolution of combinatorial optimisation problems (COPs). However, in practice, only small problem instances can be solved on a sequential computer, as B&B often generates a huge amount of subproblems to be evaluated. Aiming at the resolution of large COPs, we revisit the design and implementation of massively parallel B&B on top of large heterogeneous clusters, integrating multi-core CPUs, many-core processors and GPUs. For the efficient storage and management of subproblems an original data structure (IVM) dedicated to permutation problems is used. Because of the highly irregular and unpredictable shape of the B&B tree, dynamic load balancing between parallel exploration processes is a critical component of parallel B&B. Based on a compact encoding of the search space in the form of intervals, work stealing strategies for multi-core and GPU are proposed, as well as hierarchical approaches for load balancing in distributed memory multi-CPU/multi-GPU systems. Three permutation problems, the Flowshop Scheduling Problem (FSP), the Quadratic Assignment Problem (QAP) and the n-Queens puzzle are used as test-cases.

Training materials

Managing the Grid’5000

Training by Nouredine Melab and El-Ghazali Talbi

Ljubljana, 10 January 2017

Nouredine Melab and El-Ghazali Talbi presented to JSI members of "Slovenian initiative for national grid” their knowledge and experiences on efficiently managing the Grid’5000 infrastructure across many cities and even outside boarders. An initial discussion about expanding Grid’5000 to Slovenia was also discussed.

Different Approaches and Methods for Multi-Objective Optimisation

Training by Boris Naujoks

Ljubljana, 10–11 November 2016

Boris Naujoks trained JSI stuff on different approaches and methods for multi-objective optimisation. The training was given in an informal way where the approaches and methods were discussed based on their applicability to real-world optimisation tasks. This provided a strong connection to such kinds of problems and directly made the attendees familiar with different ways to approach such problems. In addition, real-world problems were selected that could be considered for developing and testing surrogate-assisted optimisation techniques. As a result, the trainig ended up in discussing different ways to integrate both, multi-objective optimisation and surrogate models in evolutionary algorithms.

A Gentle Introduction to Kriging

Training by Martin Zaefferer

Gummersbach, 17 June 2016

When faced with expensive to evaluate optimization problems, one frequent approach is to replace the optimized objective function by a surrogate model. One popular choice of surrogate model is Kriging. Kriging understands observations as realizations of a Gaussian process. The popularity of Kriging is due to the fact that it not only produces accurate predictions, but also provides an estimate of the prediction uncertainty. This feature is used to balance exploration and exploitation in surrogate assisted optimization.

In this training, we introduce the modeling technique. We start by motivating Kriging with a simple, linear modeling problem that is solved by a classic regression approach. Then, Kriging is introduced and used to model a more complex problem. Finally, the uncertainty estimate of the model is presented and it is briefly explained how this is employed in optimization algorithms.

The training is based on R code to show that Kriging can very easily be implemented. 

Training materials

  • All employed source code is included within the slides.

Grid’5000 Experimental Testbed

Training by Nouredine Melab and Jan Gmys

Bled, 20 May 2016

Grid’5000 is a French nation-wide experimental testbed dedicated to research and education related to parallel and/or distributed computing. This tutorial provides a fast handling of the Grid’5000 infrastructure through a lecture (1h) and a practical lab (2 to 3 hours).

The lecture starts with the presentation of the motivations, the objectives and architecture of the testbed. Then, the experimentation methodology is presented together with the associated software services and tools. The different steps of the methodology, including resource reservation, experiment deployment and system reconfiguration, monitoring, etc., are detailed and illustrated with some practical examples. Finally, some early significant experiments using Grid’5000 are reported.

The practical lab covers the major steps for conducting an experiment on the testbed using different tools: SSH, OAR, Monica, Kadeploy, etc. The lab starts with the connection procedure to Grid’5000. This step is then followed by interactive and passive resource reservation and supervision. An OpenMP program is used as a use case to illustrate the deployment of a parallel application. The lab is ended with the procedure illustrating the system reconfiguration for a special application deployment.

Training materials

Coming events