Hemera:SC:COPs

Large scale computing for combinatorial optimization problems (COPs)

Leaders: Bilel Derbel (DOLPHIN), Nouredine Melab (DOLPHIN)

Nowadays, more and more computation resources that are usually aggregated into large scale computational grids at different levels of hierarchy (e.g., multi-core, multi- processor, multi-cluster and multi-grid) are available to the scientific community in order to tackle hard real-life combinatorial optimization problems (COP for short), e.g., in high-energy physics, bioinformatics, space and earth observation, nanotechnology, etc. However, having such a huge amount of computational resources at hand, it is not straightforward to solve large COPs instances in an efficient way. In particular, in a fully distributed grid environment, the communication latencies, the component hetero- geneity, the volatility of resources, to mention a few, make it a challenging task to solve hard COP instances.

The goal of this challenge is to tackle hard COPs and design efficient, scalable and fault-tolerant distributed/parallel algorithms that can be effectively deployed on a compu- tational grid. The objective is twofold. On one hand, we aim at finding optimal solutions to previously unsolved COPs. On the other hand, we aim at studying COP-specific al- gorithmic issues in the context of large scale grids. More precisely, our roadmap is as follows:

• Firstly, we will focus on exact combinatorial algorithms in order to provide optimal (COP) solutions. New distributed/parallel Branch&Bound-based algorithms will be proposed and tailored to fit large scale grid constraints. The scalability of the proposed approach will be measured by its ability to be executed on an increasing number of processors without performance degradation, i.e., speed-up, load, message congestion.
• To gain in scalability, our approach will be fully distributed and will not rely on any central server. For that purpose, we will adopt a peer-to-peer approach. The challenge here is to define how to map the resources into a logical overlay so that they can efficiently coordinate their actions in a fully decentralized way. We will formally prove that our peer-to-peer approach is correct, that is, the optimal COP solution is outputted within a finite time. The proposed approach will be proved to be efficient both in a static environment where the grid resources are fully intended to solve a given COP or in a dynamic environment where grid resources can fail, join or leave at any time.
• We will conduct extensive experiments on the Grid’5000 testbed. The goal is to prove that our fully distributed approach can effectively handle hundreds of thousands of computation resources while being efficient and fault-tolerant.
• From an application point of view, the focus will be on permutation-like problems. The goal is to solve unsolved well known COP instances, e.g., Golomb instances, flow-shop/scheduling-like instances.