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 heterogeneity, 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 and scalable distributed/parallel algorithms that can be effectively deployed on a computational grid. The objective is twofold. On one hand, we aim at effectively solving hard 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 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.

Publications:

• Link-Heterogeneous Work Stealing. Trong-Tuan Vu; Bilel Derbel. 14th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing CCGrid, May 2014, Chicago, United States.
• Adaptive Dynamic Load Balancing in Heterogenous Multiple GPUs-CPUs Distributed Setting: Case Study of B&B Tree Search. Trong-Tuan Vu, Bilel Derbel, Nouredine Melab. 7th Learning and Intelligent OptimizatioN Conference (LION'13). LNCS. Jan 2013. Catania, IT.
• Overlay Centric Load Balancing: Applications to UTS and B&B. Trong-Tuan Vu, Bilel Derbel, Asim Ali, Ahcène Bendjoudi, Nouredine Melab. 14th IEEE International Conference on Cluster Computing (CLUSTER'12). IEEE. Sep 2012. Beijing, China.
• A Large-Scale Pure P2P approach for the B&B algorithm. Mathieu Djamai, Bilel Derbel & Nouredine Melab. Selected for the final round of the The Fourth IEEE International Scalable Computing Challenge (CCGRID/SCALE 2011)
• Distributed B&B: A Pure Peer-to-Peer Approach. Mathieu Djamai, Bilel Derbel & Nouredine Melab. LSPP Workshop on Large-Scale Parallel Processing (in conjunction with IPDPS 2011).