Skip to Main content Skip to Navigation
Theses

Cooperative approaches for some classes of nonconvex optimization problems : parallel / distributed algorithms and applications

Abstract : In this thesis, we are interested in developing new cooperative approaches for solving some classes of nonconvex problems which play a very important role to model real-world problems. To design the schemes of our approaches, we combine several algorithms which we call the component (participant) algorithms. The combination is mainly based on DC (Difference of Convex Functions) and DCA (DC Algorithm) with metaheuristics. To develop our solution methods, we use the paradigm of parallel and distributed programming. Therefore, each process deals with an algorithm and communicates with the others by calling the functions of the MPI (Message Passing Interface) library which is a communication protocol in parallel and distributed programming. Besides the introduction and conclusion, this thesis is composed of four chapters. Chapter 1 concerns the theoretical and algorithmic tools serving as a methodological basis for the following chapters. Chapter 2 is about the mixed binary linear programs. To solve these problems, we propose a cooperative approach between DCA and VNS (Variable Neighborhood Search). Since the scheme is constituted by two algorithms, we use the point to point communication between the processes. As an application, we adapt our scheme to solve the capacitated facility location problem. Concerning chapter 3, we study the class of binary quadratic problems. Regarding the solution methods, we develop a cooperation between DCA-like which is a new version of DCA and two other metaheuristics: GA (Genetic Algorithm) and MBO (Migrating Birds Optimization). The exchange of information between the processes is expressed by using collective communication's function. More precisely, we call a function which allows broadcasting information of a process to all the others at the same time. This cooperative approach is adapted to the quadratic assignment problem. In chapter 4, we solve the MSSC (Minimum-Sum-of-Squares Clustering) using two cooperative approaches. The first combines DCA, VNS, and TS (Tabu Search). As for the second, it combines the MBO with the other three algorithms cited before. In these two approaches, we use a function of communication that allows a process to access the memories of the others and save the information there without blocking the work of the receiving processes.
Document type :
Theses
File URL :
http://docnum.univ-lorraine.fr/ulprive/DDOC_T_2020_0039_SAMIR.pdf
Complete list of metadatas

https://hal.univ-lorraine.fr/tel-02929605
Contributor : Thèses Ul <>
Submitted on : Thursday, September 3, 2020 - 3:38:56 PM
Last modification on : Friday, September 4, 2020 - 3:15:39 AM

Identifiers

  • HAL Id : tel-02929605, version 1

Collections

Citation

Sara Samir. Cooperative approaches for some classes of nonconvex optimization problems : parallel / distributed algorithms and applications. Computer Science [cs]. Université de Lorraine, 2020. English. ⟨NNT : 2020LORR0039⟩. ⟨tel-02929605⟩

Share

Metrics

Record views

19