Search

The IEEE Workshop on Parallel / Distributed Combinatorics and Optimization aims at providing a forum for scientific researchers and engineers on recent advances in the field of parallel or distributed computing for difficult combinatorial optimization problems, like 0–1 multidimensional knapsack problems, cutting stock problems, scheduling problems, large scale linear programming problems, nonlinear optimization problems and global optimization problems. Emphasis is placed on new techniques for the solution of these difficult problems like cooperative methods for integer programming problems. Techniques based on metaheuristics and nature-inspired paradigms are considered. Aspects related to Combinatorial Scientific Computing (CSC) are considered. In particular, we solicit submissions of original manuscripts on sparse matrix computations, graph algorithm and original parallel or distributed algorithms. The use of new approaches in parallel and distributed computing like GPU, MIC, FPGA, volunteer computing are considered. Application to cloud computing, planning, logistics, manufacturing, finance, telecommunications and computational biology are considered.

Engineering students often find difficulties in understanding electrical diagrams, specially those from Design and Mechanical Engineering. A tool that can automatically generate the ladder diagram out of the wiring diagram would be extremely useful for them in their studies. Unfortunately, such a tool does not exist yet. We present in this paper a novel CAD tool that offers this functionality. The tool, called CADDI (standing for CAD for Electrical Diagrams) is designed to help students better understanding wiring and ladder diagrams. In CADDI, the user can either draw the ladder diagram using its graphical interface, or code the wiring diagram using a novel simple programming language, and it will automatically generate its ladder diagram. The mentioned new language was especially designed for this purpose by the students of Automata Theory and Formal Languages subject, from Computer Science Engineering degree of the University of Cadiz. In order to make CADDI accessible to all students, it was implemented as a web page. The tool has become a great assistance for students, who regularly use it during their studies.

A key issue when using distributed computing environments is finding a planning strategy to execute tasks in order to use the computational resources efficiently. This article presents the application of Virtual Savant to solve the heterogeneous computing scheduling problem, a widely-studied problem with several real-world applications. Virtual Savant is a novel method that uses machine learning techniques to automatically generate programs that can be executed in parallel to solve a given problem. Experimental analysis is performed on a set of problem instances generated following methodologies from the related literature. Results show that Virtual Savant is able to outperform MinMin, a well-known heuristic for the studied problem, by up to 15% while showing good scalability properties when increasing the number of computing resources and the dimension of the problem instances.

Over the last ten years, there has been a significant change in computing. After reaching the physical limits in integrated circuit technology, Moore's law (predicting an exponential growth of computing capacity over the years) has been maintained thanks to the replication of computing components (i.e., parallelization). Current computers now incorporate multiple processors, which are themselves multi-core, and come with technologies to increase the parallel capabilities of processors, like the Intel hyper-threading technology that implements two logical processors per core. This is the architecture present not only in today's servers or workstations, but also in portable and mobile devices as laptops, tablets, or mobile phones. It is accepted that this trend towards more and more parallel architectures will be maintained in the coming years.

We propose a new accurate and fast memetic parallel optimization algorithm for the independent tasks scheduling problem. The new technique combines the Virtual Savant (VS) with a parallel genetic algorithm (called PA-CGA). VS is an optimization framework based on machine learning that learns from a reference set of (pseudo-)optimal solutions how to solve the problem, providing accurate results in extremely low run times. We propose in this work the use of VS to generate a highly accurate initial population for the PA-CGA. Results show how initializing the population with VS (we test two versions of VS, differing on its training process) significantly increases the accuracy of the PA-CGA, compared to two other population initialization techniques: random and using a state-of-the-art heuristic.

This article addresses a virtual machine (VM) allocation problem that appears in a novel business model for cloud computing. In this model, a cloud service broker owns a number of cloud reserved instances that outsources to its customers as cheap as on-demand VMs. The objective of the broker is to efficiently manage its reserved resources to maximize its revenue. We enhance the previous definition of the problem by considering more realistic parameters: geographical localization of resources and users, different types of applications, and data transfer costs. We propose a set of heuristics to solve the optimization problem of maximizing the cloud provider profit while offering appropriate Quality-of-Service to the users. The experimental analysis is performed over different scenarios using real data from cloud providers.

This paper presents a new parallel multi-objective cooperative coevolutionary variant of the Speed-constrained Multi-objective Particle Swarm Optimization (SMPSO) algorithm. SMPSO adopts a strategy for limiting the velocity of the particles that prevents them from having erratic movements. This characteristic provides the algorithm with a high degree of reliability. The proposed approach, called CCSMPSO, is based on a new design and implementation of SMPSO in a cooperative coevolutionary (CC) framework. In such an architecture, the population is split into several subpopulations, which are in turn in charge of optimizing a subset of the global solution by using the original multi-objective algorithm. We compare our work with two different state-of-the-art multi-objective CC metaheuristics, namely CCNSGA-II and CCSPEA2, as well as the original SMPSO in order to demonstrate its effectiveness. Our experiments indicate that our proposed solution, CCSMPSO, offers significant computational speedups, a higher convergence speed and better and comparable results in terms of solution quality, when compared to the other two CC algorithms and SMPSO, respectively. Three different criteria are used for making the comparisons, namely the quality of the resulting approximation sets, average computational time and the convergence speed to the Pareto front.

The energy consumption of large data centers has been increasing for the last decades and currently is a major concern for economic and environmental reasons. Accurate scheduling of the data center operation and use of renewable energy sources present themselves as promising solutions for this problem. In this paper we study the problem of scheduling workflows of tasks in distributed heterogeneous data centers which are partially powered by renewable energy sources. This problem takes into account quality of service, infrastructure usage, and power consumption of machines and cooling devices. We propose a mathematical model for accurate scheduling solutions.

Distributed parallel computing platforms contribute for a large part to some of the most powerful computers. Such architectures are typically based on accelerators (General Purpose computing on Graphics Processing Units, Many Integrated Cores e.g. Xeon Phi co-processors) and/or a large number of interconnected computing nodes. Obviously, they raise new challenges, typically in terms of scalability, robustness, adaptability and security. At the advent of the quest for Ultra scale Computing Systems, this paper addresses the issue of fault tolerance toward Byzantine failures over's such platforms. Indeed, the inherent unpredictable nature of these errors render their detection, not speaking of their correction, hard or even impossible to perform at large-scale. At this level, Algorithm-Based Fault Tolerance (ABFT) techniques where the fault tolerance scheme is tailored to the algorithm performed, seems the most promising approaches to deal with such failures. In this context, Evolutionary Algorithms (EAs), especially panmictic global parallel EAs, exhibit a remarkable resilience against byzantine failures modeled as cheating faults as demonstrated either empirically or theoretically in previous studies. In this paper, we extend this analysis to the case of distributed EAs based on the cellular model leading to distributed Cellular Evolutionary Algorithms (dCEAs). Our empirical study over a set or reference optimization problem confirm the ABFT nature of dCEAs. To our knowledge, this is the first study of dCEAs under the perspective of cheating issues and crash faults in a domain of distributed computations, thus opening new insights and perspectives for the design of competitive ultra-scale system based on evolutionary programming models.

International audience; Green Light Optimal Speed Advisory (GLOSA) systems provide drivers with speed advices that allow them to pass traffic lights during green interval. In this article we compare performance of single- and multi-segment GLOSA approaches. In a single-segment GLOSA traffic signals are considered independently, i.e. the system provides vehicles with the optimal speed for the segment ahead of the nearest traffic signals. In a multi-segment GLOSA several signals in a sequence on a vehicle's route are taken into account, that is, vehicles receive speed advices for a set of segments ahead of the vehicle. Traveling time and fuel efficiency are used as performance measures. We demonstrate that as long as traffic conditions allow drivers selecting a wide range of speed (e.g. during free-flow) a multi-segment GLOSA results in much better performance when compared with a single-segment approach.

International audience; Mobile ad hoc networks are infrastructure less communication networks that are spontaneously created by a number of mobile devices. Due to the highly fluctuating topology of such networks, finding the optimal configuration of communication protocols is a complex and crucial task. Additionally, different objectives must be usually considered. Small changes in the values of the parameters directly affects the performance of the protocol, promoting one objective while reducing another. Therefore, multi-objective optimisation is needed for fine tuning the protocol. In this work, we propose a novel parallel multi-objective local search that optimises an energy efficient broadcasting algorithm in terms of coverage, energy used, broadcasting time, and network resources. The proposed method looks for appropriate values for a set of 5 variables that markedly influence the behavior of the protocol to provide accurate tradeoff configurations in a reasonable short execution time. The new proposed algorithm is validated versus two efficient multi-objective evolutionary algorithms from the state of the art, offering comparable quality results in much shorter times.

This paper proposes a decentralized and self-organized agent system for dynamically load-balancing tasks arriving in the form of Bags-of-Tasks (BoTs) in large-scale decentralized systems. the approach is inspired by the emergent behavior of the sand pile model, a cellular automaton behaving at the edge of chaos. Depending on the state of the cellular automaton, rather different responses may occur when a new task is assigned to a resource. It may change nothing or generate avalanches that reconfigure the state of the system. the proportion between the abundance of avalanches and their sizes shows a power-law relation, a scale-invariant behavior that does not need to be tuned. That means that large - catastrophic - avalanches are very rare but small ones occur very often. Such a smart and emergent behavior fits well with the idea of non-clairvoyant scheduling, where tasks are load balanced into computing resources trying to maximize the performance but without assuming any knowledge on the tasks features. in order to study the viability of the approach, we have conducted an empirical experimentation which shows that the sand pile is able to find near-optimal schedules by reacting differently to different conditions of workloads and architectures.

The use of small-world graphs as a topology structure for the population of Evolutionary Algorithms (EAs) has been recently proposed in the literature. The motivation is clear: the high clustering coefficient and low characteristic path length of such networks makes them suitable for fast local information dissemination, while at the same time preventing it from quickly spreading on the whole population, as it happens in panmictic populations. However, even though several papers addressed this issue so far, only a few of them are able to provide competitive results with other panmictic and/or decentralized population EAs with similar configurations. Therefore, we perform ax study in this work, both theoretically and empirically, on the most appropriate mechanisms to generate SW topologies for Genetic Algorithms (a family of EA). The algorithms are analyzed in terms of efficiency and efficacy, and the best studied variant is validated versus other GAs using well known centralized and decentralized population structures, outperforming them.

This article introduces asynchronous implementations of selected synchronous cooperative co-evolutionary multi-objective evolutionary algorithms (CCMOEAs). The CCMOEAs chosen are based on the following state-of-the-art multi-objective evolutionary algorithms (MOEAs): Non-dominated Sorting Genetic Algorithm II (NSGA-II), Strength Pareto Evolutionary Algorithm 2 (SPEA2) and Multi-objective Cellular Genetic Algorithm (MOCell). The cooperative co-evolutionary variants presented in this article differ from the standard MOEAs architecture in that the population is split into islands, each of them optimizing only a sub-vector of the global solution vector, using the original multi-objective algorithm. Each island evaluates complete solutions through cooperation, i.e., using a subset of the other islands current partial solutions. We propose to study the performance of the asynchronous CCMOEAs with respect to their synchronous versions and base MOEAs on well kown test problems, i.e. ZDT and DTLZ. The obtained results are analyzed in terms of both the quality of the Pareto front approximations and computational speedups achieved on a multicore machine.

In mobile ad hoc networks (or MANETs) devices usually rely on batteries, so the lifetime of these networks highly depends on the energy consumption of the devices composing them. In this paper, we improve the performance of the adaptive enhanced distance based broadcasting algorithm, AEDB, as well as we optimize it using a hybrid multi-objective algorithm, CellDE. The optimization is done by maximizing the coverage achieved by the broadcast process while minimizing at the same time both, the energy consumption and the broadcast time. CellDE provides a wide range of different solutions for the configuration of AEDB, outperforming all of them the performance of the protocol using the original configuration.

Cellular genetic algorithms (cGAs) are a kind of genetic algorithms (GAs) with decentralized population in which interactions among individuals are restricted to close ones. The use of decentralized populations in GAs allows to keep the population diversity for longer, usually resulting in a better exploration of the search space and, therefore in a better performance of the algorithm. However, the use of decentralized populations supposes the need of several new parameters that have a major impact on the behavior of the algorithm. In the case of cGAs, these parameters are the population and neighborhood shapes. Hence, we propose in this work two new adaptive techniques that allow removing the neighborhood to use from the algorithm's configuration. As a result, one of the new adaptive cGAs outperform the compared cGAs with fixed neighborhoods in the continuous and combinatorial domains.

We study the problem of efficiently allocating incoming independent tasks onto the resources of a Grid system. Typically, it is assumed that the estimated time to compute each task on every machine is known. We are making the same assumption in this work, but we allow the existence of inaccuracies in these values. Our schedule will be robust versus such inaccuracies, ensuring that even when the estimated time to compute all the tasks is increased by a given percentage, the makespan of the schedule (i.e., the time when the last machine finishes its tasks) will not grow behind that percentage. We propose a new multi-objective definition of the problem, optimizing at the same time the makespan of the schedule and its robustness. Four well-known multi-objective evolutionary algorithms are used to find competitive results to the new problem. Finally, a new population initialization method for scheduling problems is proposed, leading to more efficient and accurate algorithms.

In modern parallel and distributed systems, inter-processor communications are a crucial factor of performance. The time for exchanging data is usually larger than that for computing elementary operations. Consequently, these communications slow down the execution of the application scheduled on the computing platform. Accounting for these communications is essential for attaining efficient hardware and software utilization. Moreover, energy dissipation due to the transfer of data between processing elements has become a major concern. Therefore, in this paper we develop an energy-aware static algorithm, which intrinsically optimizes the energy consumption due to the transfer of data in a distributed system. This is achieved by properly allocating and scheduling the tasks that constitute the applications on the processing elements, minimizing inter-processor communications. The proposed algorithm is a new Cellular Genetic Algorithm based on task clustering techniques. That is, the genetic operators work considering groups of tasks instead of applying them directly on the tasks. Simulation results showed that this algorithm is very compelling in terms of application completion time, inter-processor communication and energy communication dissipation.

We propose a new parallel asynchronous cellular genetic algorithm for multi-core processors. The algorithm is applied to the scheduling of independent tasks in a grid. Finding such optimal schedules is in general an NP-hard problem, to which evolutionary algorithms can find near-optimal solutions. We analyze the parallelism of the algorithm, as well as different recombination and new local search operators. The proposed algorithm improves previous schedules on benchmark problems. The parallelism of this algorithm suits it to bigger problem instances.

VANETs are ad hoc networks in which devices are vehicles moving at high speeds. This kind of network is getting more and more importance since it has many practical and important applications, like multimedia file sharing (e.g., maps, music, news, weather), or dissemination of alarm messages (e.g., accidents, traffic jams, bad road conditions). One important problem faced in ad hoc networks is network partitioning, causing the formation of isolated clusters, and preventing devices in different clusters from communicating. Usually, devices composing the ad hoc network are provided with other communication interfaces rather than Wi-Fi and/or Bluetooth that allow them to connect to remote devices, such as GPRS/HSDPA. Additionally, there exists some network infrastructure in cities or roads that could be used by VANETs (e.g. hotspots). By taking advantage of these technologies and infrastructures, devices could be able to form a hybrid network, establishing remote links between them (called bypass links) in order to improve the network connectivity by joining, for example, separate clusters. In this work, we face the problem of optimizing the number and location of these remote connections for maximizing the QoS of the network. We use an efficient genetic algorithm with structured population, called cellular genetic algorithm (cGA), to optimize this hard problem. The evaluation of the quality of the network connectivity is made using small world properties. Our goal is to find highly accurate solutions (that could be used as reference values for future works) and then analyze the influence of the quality of the solutions in the real behavior of the network. This is achieved by using the JANE simulator to disseminate a message in the network using two broadcasting protocols having different features.

This work proposes a new parallel asynchronous cellular genetic algorithm model for multi-core processors. The algorithm has been used for solving the DNA fragment assembly problem with the aim of finding highly accurate solutions in short computation times. This NP-Complete problem lies in reconstructing a DNA chain from multiple fragments that have previously been sequenced in a laboratory. The considered problem is a critical step in any genomic project, since the resulting chains are the basis for the entire work. Therefore, the quality of these chains is a major aspect for the correct development of the project. The proposed algorithm is able to find highly accurate results much faster than the other algorithms in the literature. Additionally, since it is parallel, it could be scalable to much larger problem instances, for which the methods typically used usually encounter difficulties. Finally, several new local search methods have been designed, and their influence on the performance of the algorithm has been analyzed.

The DNA fragment assembly problem is to re construct a DNA chain from multiple fragments that have previously been sequenced in a laboratory. This is a critical step in any genomic project, since the resulting chains are the basis of all the work. Therefore, the quality of these chains is a prime importance to the correct development of the project. The methods typically applied to this problem usually encounter difficulties on large instances, so more efficient techniques are necessary. In this context, this work proposes a new method combining a general purpose metaheuristic (an advanced cellular genetic algorithm which automatically regulates the intensity of the search) with a local search method specifically designed for this problem (PALS). This local search method (recently published) finds very accurate solutions in very short times. As a result, our proposal is a very accurate and efficient hybrid technique clearly outperforming the other existing ones.

In This work we study cellular evolutionary algorithms, a kind of decentralized heuristics, and the importance of the induced exploration/exploitation balance on different problems. It is shown that, by choosing synchronous or asynchronous update policies, the selection pressure, and thus the exploration/exploitation tradeoff, can be influenced directly, without using additional ad hoc parameters. Synchronous algorithms of different neighborhood-to-topology ratio, and asynchronous update policies are applied to a set of benchmark problems. Our conclusions show that the update methods of the asynchronous versions, as well as the ratio of the decentralized algorithm, have a marked influence on its convergence and on its accuracy.